PaperlayerView exact revision on arXiv

Source-linked AI summary

Parallel and Distributed Methods for Nonconvex Optimization--Part II: Applications

Gesualdo Scutari, Francisco Facchinei, Lorenzo Lampariello, Peiran Song, Stefania Sardellitti

arXiv:1601.04059v1cs.ITcs.DC

TL;DR

The paper addresses nonconvex resource-allocation problems in communication networks, where existing approaches have limited formulation scope or convergence guarantees. It applies inner convex approximations to develop centralized and distributed algorithms with closed-form subproblem solutions. The proposed schemes support the two case studies, converge to d-stationary solutions, and compare favorably with state-of-the-art methods in reported experiments.

  • Problem

    The paper studies nonconvex rate-profile maximization and multicast multigroup beamforming problems whose existing methods do not cover the full formulations or prove convergence to d-stationary solutions.

  • Method

    The paper builds inner convex approximations into algorithms whose subproblems can be solved in closed form and distributed across base stations with limited signaling.

  • Results

    The proposed algorithms converge to d-stationary solutions and, in reported experiments, achieve better solution quality than SDR-based or competing methods while supporting distributed implementation.

  • Takeaways & Limitations

    The framework provides a flexible approach for resource-allocation formulations that include additional constraints or alternative objectives without affecting convergence guarantees.

Abstract

from arXiv · show

In Part I of this paper, we proposed and analyzed a novel algorithmic framework for the minimization of a nonconvex (smooth) objective function, subject to nonconvex constraints, based on inner convex approximations. This Part II is devoted to the application of the framework to some resource allocation problems in communication networks. In particular, we consider two non-trivial case-study applications, namely: (generalizations of) i) the rate profile maximization in MIMO interference broadcast networks; and the ii) the max-min fair multicast multigroup beamforming problem in a multi-cell environment. We develop a new class of algorithms enjoying the following distinctive features: i) they are \emph{distributed} across the base stations (with limited signaling) and lead to subproblems whose solutions are computable in closed form; and ii) differently from current relaxation-based schemes (e.g., semidefinite relaxation), they are proved to always converge to d-stationary solutions of the aforementioned class of nonconvex problems. Numerical results show that the proposed (distributed) schemes achieve larger worst-case rates (resp. signal-to-noise interference ratios) than state-of-the-art centralized ones while having comparable computational complexity.

I. INTRODUCTION

This paper applies an inner-convex-approximation framework to two nonconvex communication-network resource-allocation problems, targeting efficient algorithms with convergence guarantees. The resulting methods support distributed base-station computation and general problem formulations while converging to d-stationary solutions.

  • I. INTRODUCTION: The framework solves strongly convex inner approximations using a surrogate objective and upper convex approximants of the nonconvex constraints.The surrogate functions depend on the current iterate, and the unique subproblem solution defines the next update.
  • I. INTRODUCTION: The resulting algorithmic family allows choices of surrogate functions and step sizes that control iteration complexity, communication overhead, and convergence speed while guaranteeing convergence.The framework has also been applied to power control, MIMO relay optimization, dynamic spectrum management, and rate-allocation problems.
  • I. INTRODUCTION: Part II applies the Part I framework to rate profile maximization in MIMO interference broadcast networks and max-min fair multicast multigroup beamforming in multi-cell systems.These problems address interference management and multimedia broadcast applications in next-generation wireless networks.
  • I. INTRODUCTION: The proposed formulations can accommodate additional interference, null, power, and quality-of-service constraints, as well as alternative utilities such as weighted sum-rate and weighted geometric mean.This flexibility is presented as an improvement over rigid ad-hoc methods designed for narrower formulations.
  • I. INTRODUCTION: The rate-profile problem models a multi-cell interference broadcast channel with one multi-antenna base station per cell serving multiple users, subject to power and additional convex constraints.The model includes per-antenna limits, null constraints, and soft-shaping constraints, while rates account for intra-cell and inter-cell interference.
  • I. INTRODUCTION: Special instances of the rate-profile formulation are NP-hard, so the paper focuses on efficiently computing d-stationary solutions rather than guaranteed global optima.An equivalent smooth reformulation connects stationary solutions in the reformulated problem to d-stationary solutions of the original problem.

B. Related works

The section positions the general problem as underexplored and develops NOVA-based convexifications with convergence guarantees for centralized and distributed algorithms.

  • Problem P and its smooth formulation Ps remain unexplored in their full generality.
  • The paper proposes three alternative convexifications of Ps, yielding different convex subproblems and algorithms.The constructions build on the iNner cOnVex Approximation (NOVA) framework from Part I.
  • The framework targets rate-profile maximization and related resource-allocation problems in interference networks.The rate constraints are nonconvex because of the rate functions Rik(Q).
  • The centralized NOVA scheme solves strongly convex inner approximations iteratively and uses a diminishing step-size sequence.Each approximation depends on the current iterate and has a unique solution.
  • Every limit point is stationary for Ps and therefore d-stationary for P, while nonterminating runs avoid local minima and degenerate zero-service solutions.The convergence theorem requires γν→0 and Σν γν=+∞.
  • The centralized implementation cannot decompose across base stations because the rate constraints depend on all users’ covariance matrices.An alternative convex approximation introduces separability to enable distributed schemes.

D. Distributed implementation

The distributed implementation introduces slack variables that separate the convexified constraints, enabling base-station decomposition with closed-form updates and limited coordination.

  • Centralized computation is unsuitable when each base station lacks global information, motivating distributed algorithms with reduced inter-cell communication.
  • Slack variables decouple each user’s covariance matrix from the interference term and produce an equivalent formulation with separable constraints.The reformulation uses Yik to represent interference-related matrix quantities.
  • The distributed convex approximation has additively separable objectives and constraints, allowing decomposition across base stations.The resulting formulation is given by equation (11).
  • The per-cell subproblems for rates, covariance matrices, and slack variables have unique closed-form or waterfilling-like solutions under power-budget constraints.The rate update is closed form, while covariance updates use water-level selection satisfying the power constraint.
  • A distributed dual algorithm converges to the unique solution of the convexified problem when βn→0, βn>0, and Σn(βn)^2<∞.
  • Base stations update local covariance and slack variables independently, while rate and multiplier updates require a header or consensus-like coordination.The proposed figure reports minimum rate versus SNR and states that the proposed algorithm reaches better solutions than the state of the art.

E. Numerical results

Experiments compare the proposed centralized and distributed algorithms with established resource-allocation methods and assess their effectiveness in interference broadcast networks.

  • Centralized algorithm: The experiments compare Algorithm 1 with Max-Min WMMSE, WMMSE, SJBR, GSJBR, and Matlab’s active-set solver in a four-cell interference broadcast network.The simulated network has three randomly placed active mobile terminals per cell, with four antennas at each base station and mobile terminal.
  • Distributed algorithms: Figure 3 compares minimum rate versus iterations for centralized and distributed implementations using first-order and second-order methods.The left plot compares centralized with distributed first-order iterations, while the right plot compares centralized with distributed second-order iterations.
  • Centralized algorithm: Algorithm 1 provides better minimum-rate solutions than Max-Min WMMSE and also achieves better sum-rate in the reported comparison.The paper attributes this comparison partly to the stronger stationarity guarantee of Algorithm 1 for the original formulation.

III. MULTIGROUP MULTICAST BEAMFORMING

The paper studies general max-min fair multicast beamforming in multicell systems, formulates the nonconvex problem smoothly, and develops NOVA-based methods with d-stationarity guarantees.

  • A. System model: The system has multiple base stations, each serving a multicast group, with beamforming vectors constrained by channel, noise, and per-cell power models.The formulation supports instantaneous or long-term channel state information and can incorporate additional convex constraints such as per-antenna power limits.
  • A. System model: The general multicell max-min fair beamforming problem is nonconvex, while even a single-cell multiple-group instance is NP-hard.The paper therefore targets efficient computation of stationary or d-stationary solutions rather than global optimization.
  • A. System model: Introducing slack variables yields an equivalent smooth formulation whose feasible set is compact under the stated bounds.The reformulation enables the subsequent convexification and convergence analysis.
  • A. System model: Stationary solutions of the smooth formulation correspond exactly to d-stationary beamformers of the original problem.This equivalence is identified as a new result in the literature.
  • Contributions: The proposed centralized and first distributed algorithms converge to d-stationary solutions and numerically outperform SDR-G approaches with high probability at comparable computational complexity.The distributed method addresses the previously noted lack of a multicell MMF scheme with provable convergence.

C. Centralized solution method

The centralized solution method constructs strongly convex inner approximations of the multicast beamforming problem and iteratively updates their unique solutions with a diminishing step size.

  • Convexification: The method convexifies each nonconvex constraint using valid surrogate functions, including alternative bounds for bilinear and concave terms.Two examples are given: linearizing the concave component and using a difference-of-convex representation for the bilinear term.
  • Convexification: A proximal regularization makes each inner approximation strongly convex, ensuring a unique subproblem solution.The solution is denoted by ˆz(zν) and is used as the next algorithmic direction.
  • Algorithm: Algorithm 3 repeatedly computes the unique inner-approximation solution and updates zν by zν+1 = zν + γν(ˆz(zν) − zν).The initialization requires t0 > 0, and the step size satisfies γν ∈ (0, 1].
  • Convergence: With positive regularization parameters and suitable diminishing step sizes, every limit point is stationary for the smooth problem and d-stationary for the original problem.The theorem also guarantees tν > 0 and excludes degenerate stationary solutions with zero objective value.
  • Distributed implementation: The centralized subproblem does not decouple across base stations, whereas additive separability enables a distributed dual solution using closed-form local updates.Local beamforming and auxiliary-variable updates require only within-cell information; updating the shared variable and multipliers requires coordination.

E. Numerical Results

The numerical experiments evaluate centralized and distributed algorithms on multicast beamforming and related resource-allocation problems. The proposed methods approach the SDP bound closely, support distributed implementations, and apply beyond the two studied formulations.

  • Example 1: Centralized algorithm: The experiments compare NOVA1 and NOVA2 with SDR-G using 300 channel realizations and user-group sizes I=12, 24, 30, 50, 100.The setup uses one base station with 8 transmit antennas and two multicast groups.
  • Example 1: Centralized algorithm: The reported metric is the average normalized distance 1−tapprox/tSDP from the SDP upper bound, with tapprox set to each method’s achieved objective.The comparison includes SDR-G, NOVA, and the AS algorithm in Matlab.
  • Example 1: Centralized algorithm: When I=30, the NOVA methods are within 25% of the SDP upper bound.The paper reports that NOVA reaches an objective value much closer to the SDP bound than SDR-G.
  • Example 2: Distributed algorithms: The distributed schemes implement the same algorithmic update across cells while computing its inner solution through distributed first- or second-order methods.The figure comparison distinguishes centralized, distributed first-order, and distributed second-order variants.
  • Scope: The framework is also presented as applicable to additional communication problems and to areas including signal processing, smart grids, and machine learning.Examples include distributed weighted transmit-power minimization and weighted multicast capacity maximization.

APPENDIX

The appendix derives structural properties and closed-form updates for the convex subproblems used by the algorithm. Matrix solutions are shown to be diagonal, enabling decomposition into simpler subproblems and explicit expressions.

  • Closed-form subproblem structure: Each Qk subproblem decomposes across the indexed users, and its optimal matrix solution must be diagonal.The diagonal structure follows because the objective admits a lower bound attained when off-diagonal components vanish, while constraints depend only on diagonal entries.
  • Power-feasible construction: The diagonal entries can be selected to satisfy the power constraint, with Algorithm 4 converging in a finite number of steps.The construction arranges entries in decreasing order and iteratively removes indices according to the stopping condition.
  • Closed-form subproblem structure: Replacing the diagonal matrix with Diag(yik) and verifying the KKT system yields the closed-form expression in (16).The resulting expression provides the update for the corresponding convex optimization problem.
  • Derivative expressions: The appendix provides closed-form augmented Hessian and gradient expressions for the updating rules in (19).These expressions include the Hessian blocks and multiplier-dependent terms used in the updates.

D. Proof of Theorem 10

The proof establishes an equivalence between d-stationarity of a max-function formulation and regular stationarity of its epigraph reformulation. This equivalence transfers stationarity conclusions between the two problems.

  • Auxiliary positivity result: The proof also preserves positivity of the iterates tν when the initial value t0 is positive.The update expression shows t1>0, and the result follows for later iterations.
  • Problem formulation: The proof considers min x∈K F(x), where F(x)=max{f1(x),…,fI(x)} and each fi is differentiable with Lipschitz gradient.The feasible set K is closed and convex, and the functions are nonpositive.
  • Stationarity equivalence: The key proposition states that x⋆ is d-stationary for the max formulation if and only if an associated pair (x⋆,t⋆) is regularly stationary for the epigraph formulation.The proof uses the active-index set and subgradient representation of the maximum.
  • Forward implication: A d-stationary point yields KKT conditions for the epigraph problem by setting t⋆=F(x⋆) and using the active-function multipliers.This establishes regular stationarity of the corresponding epigraph point.
  • Reverse implication: Conversely, regular stationarity of the epigraph problem implies t̄=F(x̄), after which normalized active multipliers establish d-stationarity of x̄.The argument uses complementarity and the directional derivative characterization of the maximum.

F. Proof of Proposition 9

This passage introduces an intermediate quantity yik(w) used in the proof of Proposition 9. Its surrounding definition is not supplied here, so the section’s further derivation cannot be summarized.

  • Intermediate definition: The proof introduces the intermediate quantity yik(w) before deriving Proposition 9.The supplied passage does not state the definition or subsequent role of this quantity.

1) Preliminaries:

The preliminaries establish regularity and KKT conditions for the lifted formulation, linking its stationary points to d-stationary solutions of the original problem.

  • 1) Preliminaries:: The lifted problem's KKT system introduces multipliers for the user constraints and beamforming-related conditions.The conditions include complementarity relations involving η̄_ik and ρ̄_ik, alongside stationarity conditions.
  • 1) Preliminaries:: The active-user set I_a(w⋆) partitions users according to whether they are served by a base station.The complementary inactive case is characterized through the set I(w⋆) of users attaining U(w⋆).

2) Proof of Proposition 9:

The proof of Proposition 9 constructs KKT multipliers for the lifted problem from d-stationary points and derives d-stationarity of the original problem from regular stationary points.

  • 2) Proof of Proposition 9:: The proof separates the construction into active-user and inactive-user cases.The inactive-user case is identified as degenerate when U(w⋆)=0; the complementary case has U(w⋆)>0.
  • 2) Proof of Proposition 9:: For an active-user solution, the proof sets t̄=0, chooses feasible β̄, assigns w̄=w⋆, and constructs multipliers satisfying the KKT conditions.The construction uses α⋆ for λ̄ and sets η̄, ρ̄, and ζ̄ to zero.
  • 2) Proof of Proposition 9:: For an inactive-user solution, the proof sets t̄=U(w⋆), β̄=y(w⋆), and constructs η̄ from λ̄ and the user utilities.It sets ρ̄=0 and ζ̄=0 before verifying the KKT conditions by substitution.
  • 2) Proof of Proposition 9:: A regular stationary point of Problem (22) yields a d-stationary point of Problem (21), including the case where the active-user set is nonempty.The directional derivative argument concludes d-stationarity for every feasible direction.
Loading 1601.04059v1…