PaperlayerView exact revision on arXiv

Source-linked AI summary

Decomposition by Partial Linearization: Parallel Optimization of Multi-Agent Systems

Gesualdo Scutari, Francisco Facchinei, Peiran Song, Daniel P. Palomar, Jong-Shi Pang

arXiv:1302.0756v2cs.ITmath.OC

TL;DR

Distributed optimization of general nonconvex sum-utility problems is difficult because centralized methods are demanding and simultaneous convergent updates are scarce. The paper introduces a decomposition framework with parallel convexified best responses, inexact-update convergence, and dynamic pricing derived from problem structure. It applies the framework to wireless interference problems, where experiments report faster performance than ad-hoc state-of-the-art methods.

  • Problem

    Distributed solution methods are needed for generally nonconvex sum-utility problems because centralized optimization is too demanding and simultaneous convergent updates are scarce.

  • Method

    The paper develops an SCA-based decomposition in which users simultaneously solve suitably convexified best-response subproblems, possibly inexactly, with a dynamic pricing interpretation.

  • Results

    The framework yields convergent distributed Jacobi best-response algorithms and, in SISO/MIMO interference applications, experiments show faster performance than ad-hoc state-of-the-art methods.

  • Takeaways & Limitations

    The framework unifies gradient algorithms, block-coordinate descent schemes, and problem-derived pricing mechanisms within a distributed approach to nonconvex sum-utility optimization.

Abstract

from arXiv · show

We propose a novel decomposition framework for the distributed optimization of general nonconvex sum-utility functions arising naturally in the system design of wireless multiuser interfering systems. Our main contributions are: i) the development of the first class of (inexact) Jacobi best-response algorithms with provable convergence, where all the users simultaneously and iteratively solve a suitably convexified version of the original sum-utility optimization problem; ii) the derivation of a general dynamic pricing mechanism that provides a unified view of existing pricing schemes that are based, instead, on heuristics; and iii) a framework that can be easily particularized to well-known applications, giving rise to very efficient practical (Jacobi or Gauss-Seidel) algorithms that outperform existing adhoc methods proposed for very specific problems. Interestingly, our framework contains as special cases well-known gradient algorithms for nonconvex sum-utility problems, and many blockcoordinate descent schemes for convex functions.

I. INTRODUCTION

The paper addresses distributed optimization of nonconvex sum-utility problems in wireless multiuser systems, where centralized methods are demanding and simultaneous convergent updates are scarce. It proposes a decomposition framework that parallelizes convexified user subproblems, supports inexact updates, and unifies several existing methods and pricing mechanisms.

  • I. INTRODUCTION: Wireless multiuser systems are designed by optimizing a social function, typically a weighted sum of users’ objectives, under interference and limited signaling.The formulation includes peer-to-peer, ad-hoc, and cognitive radio systems; distributed optimization is difficult because centralized methods are often too demanding.
  • I. INTRODUCTION: The paper targets simultaneous distributed methods for general nonconvex sum-utility problems with provable convergence, addressing a gap left by scarce prior results.Existing gradient schemes can suffer from slow convergence, while parallel iterative methods had been developed for narrower settings.
  • I. INTRODUCTION: The proposed decomposition converges to stationary points while decomposing across users into parallel convex subproblems, including when those subproblems are solved inexactly.The framework covers a large class of nonconvex social problems, including functions of complex variables.
  • I. INTRODUCTION: The framework contains gradient algorithms for nonconvex sum-utility problems and many block-coordinate descent schemes for convex functions as special cases.This connects the proposed method to established algorithmic families rather than treating them as unrelated approaches.
  • I. INTRODUCTION: The method relaxes the requirement that SCA approximations be tight global upper bounds, which had been difficult to construct for general sum-utility functions.It also derives a dynamic pricing interpretation whose rule follows from problem characteristics rather than ad-hoc heuristics.
  • I. INTRODUCTION: The paper applies the framework to sum-rate maximization over SISO and MIMO interfering channels and reports faster performance than ad-hoc state-of-the-art methods.The problem class includes utility functions such as weighted sum-rate, harmonic mean of rates, and geometric mean of one plus the rates.

III. A NEW DECOMPOSITION TECHNIQUE

The decomposition preserves user-wise convexity where available and linearizes the remaining terms around the current iterate, producing strongly convex best-response problems. A simultaneous Jacobi update then uses these responses with step sizes and regularization chosen to support convergence.

  • A. What do conditional gradient methods miss?: Gradient methods solve parallel convex problems formed by linearizing the entire utility, whereas partial linearization retains available convex structure.This distinction motivates the expected efficiency advantage of the proposed decomposition over classical gradient-based schemes.
  • A. What do conditional gradient methods miss?: The method starts from SCA and seeks to exploit any convexity present in each user’s portion of the social function.The paper contrasts this with gradient methods, which linearize the whole utility function and therefore do not exploit potentially useful structure.
  • A. What do conditional gradient methods miss?: For each user, functions convex in that user’s variable are preserved, while the remaining functions are linearized around the current iterate.The retained-function index set is S_i, with C_i selecting the convex terms kept in the approximation.
  • A. What do conditional gradient methods miss?: The resulting approximation adds a proximal-like regularization term controlled by τ_i and a uniformly positive definite matrix H_i(x^n).This regularization can relax convergence conditions or enhance convergence speed.
  • A. What do conditional gradient methods miss?: Each user’s best response is the unique solution of a strongly convex problem, so the collection of responses defines a well-defined parallel update mapping.The proposed search direction is the difference between the best-response vector and the current iterate.

B. Properties of the best-response mapping bxC(y, τ)

The best-response mapping links fixed points to stationary solutions and provides descent directions for the nonconvex social problem, enabling convergent distributed Jacobi algorithms.

  • The mapping’s fixed points coincide with stationary solutions of the social problem, and at least one fixed point exists.
  • For any feasible current point, the best-response displacement is either a descent direction for the social function or zero at a fixed point.
  • Fixed points can also be characterized as Nash equilibria of a game whose objectives include a proper pricing mechanism.
  • Computing that Nash equilibrium directly is impractical because the required equilibrium prices are not known beforehand.
  • Algorithm 1 makes users solve decoupled strongly convex subproblems in parallel and update simultaneously, with exact or inexact variants covered by convergence results.
  • The algorithm’s parameters can trade off signaling, convergence speed, and computational effort, while convergence holds under the stated step-size and regularization conditions.

1) Constant step-size:

The framework supports constant and diminishing step sizes, flexible curvature choices, and several established algorithmic special cases, including gradient, pricing, Newton-like, and block-Jacobi methods.

  • Constant step-size: A conservative constant-step condition is γ/τ ≤ 2/L_∇U, leaving one of the step size and regularization parameters free.
  • Constant step-size: With γ = 1, H_i = I, and sufficiently large τ, the method becomes a proximal Jacobi best-response scheme.
  • Constant step-size: The resulting Jacobi algorithm is presented as a new convergent result under weaker conditions than classic best-response nonlinear Jacobi schemes.
  • Diminishing step-size: Diminishing step sizes guarantee convergence for any admissible H_i and τ satisfying c_τ > 0, and support inexact best-response computation.
  • Special cases: The framework also contains gradient-like, Newton-like, DC-programming, and block-Jacobi schemes as special cases.
  • Special cases: When each user’s component is convex in its own variable, the framework recovers pricing-based algorithms, with prices representing marginal effects on other users’ utilities.

B. Inexact Jacobi best-response schemes

The inexact Jacobi SCA algorithm lets users solve convexified subproblems simultaneously, with controlled approximation errors and step sizes ensuring convergence to stationary solutions.

  • B. Inexact Jacobi best-response schemes: Inexact Jacobi SCA allows each user to solve its convex subproblem only approximately at each iteration.The per-iteration accuracy is represented by εn_i; setting εn_i = 0 recovers the exact Jacobi algorithm.
  • B. Inexact Jacobi best-response schemes: The algorithm updates all users in parallel, then applies a step-size-weighted move from the current iterate toward the computed responses.The update is x^(n+1) = x^n + γn(z^n − x^n).
  • B. Inexact Jacobi best-response schemes: Convergence requires suitable conditions on the step-size and error sequences, including diminishing steps and summable error-weighted terms.The theorem’s conditions include γn → 0, summability of the step sizes, and a rate constraint on εn_i.
  • B. Inexact Jacobi best-response schemes: Under these conditions, the algorithm either terminates finitely at a stationary solution or every limit point of its iterate sequence is stationary.The result applies under the theorem’s assumptions, including the stated coercivity setting.
  • B. Inexact Jacobi best-response schemes: The method can be made robust to stochastic price-estimation errors caused by imperfect communication when using an appropriate diminishing step-size rule.Examples include random link failures, noisy estimates, and quantization; details are deferred to another reference.

C. (Inexact) Gauss-Seidel best-response schemes

The Gauss-Seidel implementation updates users sequentially by solving exact or inexact convex subproblems, and its convergence follows from interpreting it as an inexact Jacobi scheme.

  • C. (Inexact) Gauss-Seidel best-response schemes: Gauss-Seidel SCA updates users sequentially, with each user solving its convex subproblem in exact or inexact form.A round consists of consecutive updates for users i = 1, ..., I.
  • C. (Inexact) Gauss-Seidel best-response schemes: One Gauss-Seidel round corresponds to I consecutive Jacobi updates, with each user updating against the progressively updated strategies.The sequential implementation is therefore related directly to the paper’s parallel update framework.
  • C. (Inexact) Gauss-Seidel best-response schemes: Algorithm 3 can be interpreted as an inexact Jacobi scheme based on the best-response map.This interpretation lets the authors derive its convergence from the convergence result for Algorithm 2.
  • C. (Inexact) Gauss-Seidel best-response schemes: Under the setting of Theorem 4, the conclusions of Theorem 4 also hold for the sequence generated by Algorithm 3.Thus, the Gauss-Seidel implementation inherits the corresponding stationary-point convergence guarantee.

V. THE COMPLEX CASE

The framework extends to complex matrix variables for MIMO systems by replacing real differentiability and Hessians with R-differentiability, conjugate gradients, and augmented Hessians.

  • V. THE COMPLEX CASE: The complex extension targets sum-utility optimization problems whose users control complex matrices, enabling applications to MIMO multiuser systems.Each user’s strategy is a complex matrix Xi in a feasible set Xi.
  • V. THE COMPLEX CASE: The complex formulation retains the real-case assumptions after replacing differentiability with R-differentiability and requiring a Lipschitz conjugate gradient.The relevant Lipschitz constant is denoted LC_∇U.
  • V. THE COMPLEX CASE: The framework accommodates covariance-matrix constraints including null-space, soft-shaping, peak-power, and per-antenna restrictions.The admissible set may also include arbitrary convex closed constraint sets, and prior MIMO optimization problems appear as special cases.
  • V. THE COMPLEX CASE: Complex-valued SCA uses a second-order Taylor expansion and an augmented Hessian to construct convex approximations and characterize strong convexity.The augmented Hessian plays the role of the Hessian for real-valued functions of complex variables.
  • V. THE COMPLEX CASE: The resulting complex algorithms have the same formal structure as the real Algorithms 1–3, with a complex best-response map and correspondingly modified convergence constants.The approximation includes a quadratic regularization term; when Hi(X) = I, it becomes standard proximal regularization.

VI. EXTENSIONS AND RELATED WORKS

The SCA framework convexifies nonconvex interactions through partial linearization and permits broader nonlinear pricing functions without requiring global upper bounds or sequential centralized updates.

  • VI. EXTENSIONS AND RELATED WORKS: The key SCA step convexifies the nonconvex portion of the utility by partially linearizing the other users’ contribution.This produces a pricing term based on the interference-related component.
  • VI. EXTENSIONS AND RELATED WORKS: The linear pricing term can be replaced by a nonlinear scalar pricing function if it satisfies differentiability, Lipschitz, and continuity conditions.The paper lists properties P1–P4 for the generalized pricing function.
  • VI. EXTENSIONS AND RELATED WORKS: Unlike approaches requiring a global upper bound, the proposed conditions do not impose that restriction on the approximation function.The paper notes that global upper bounds can be elusive for sum-utility problems without special structure.
  • VI. EXTENSIONS AND RELATED WORKS: The proposed approximations remain decomposable across users, whereas some upper-bound constructions do not and may require centralized implementation.This preserves the distributed structure of the resulting convex subproblems.
  • VI. EXTENSIONS AND RELATED WORKS: The resulting algorithms avoid the generally sequential nature of related SCA schemes and enlarge the class of large-scale nonconvex problems addressed by the framework.The comparison is stated relative to the related methods discussed in the paper.

VII. APPLICATIONS AND NUMERICAL RESULTS

The paper specializes its decomposition framework to SISO and MIMO sum-rate maximization, yielding distributed pricing and D.C.-based algorithms compared with state-of-the-art methods. The proposed SJBR scheme reaches the same sum-rate while generally converging faster and requiring less computational effort.

  • Decomposition #1—Pricing Algorithms: The pricing decomposition uses strongly concave per-user subproblems whose best responses can be computed through waterfilling-like expressions and local multipliers.Users update simultaneously using an exact Jacobi scheme with a diminishing step-size satisfying the paper’s convergence rules.
  • Decomposition #1—Pricing Algorithms: The pricing expression requires signaling among nearby users, but simultaneous schemes require less CSI exchange than the sequential methods in.The pricing computation has the same overhead as the compared decomposition, while sequential algorithms require more network CSI exchange.
  • Decomposition #2—DC Algorithms: The alternative D.C. decomposition expresses sum-rate as a sum of concave and convex functions and produces a second class of algorithms based on that structure.Its best response can be computed by a fixed-point iteration, with greater CSI exchange needed to estimate cross-channels.
  • Numerical Results: All algorithms reach the same average sum-rate, while SJBR outperforms the compared schemes in convergence behavior; its gap over WMMSE is about one order of magnitude and over MDP up to three.The comparison uses SISO frequency-selective channels with 64 subcarriers, 100 channel realizations, and a 1e-6 termination criterion.
  • Numerical Results: SJBR is almost three orders of magnitude faster than the similarly tuned gradient method, while independent gradient tuning reduces the gap to up to one order of magnitude.The comparison supports the paper’s claim that partial linearization can improve convergence speed relative to gradient schemes.
  • Numerical Results: The gradient method is highly sensitive to parameter choices, whereas Fig. 2 varies ǫ to compare this sensitivity with SJBR’s convergence behavior.The paper also notes sensitivity to network size, SNR, and pair distances, requiring retuning for different settings.

B. Sum-Rate Maximization over MIMO ICs

For MIMO interference channels, the paper applies its pricing-based Jacobi framework to obtain distributed convex best-responses and compares MIMO-SJBR with MIMO-MDP and MIMO-WMMSE. The methods have similar complexity order, while SJBR generally requires fewer iterations and achieves the same average sum-rate in simulations.

  • Pricing-based decomposition: Once the price matrix is available, each user computes its best-response locally by solving a convex optimization problem.For full-column-rank channels with τ_i = 0, a closed-form solution is available up to power-budget multipliers.
  • Pricing-based decomposition: The proposed pricing-based Jacobi schemes are presented as the first convergent class of inexact best-response Jacobi algorithms for MIMO interference channels.
  • Complexity and signaling: The three compared algorithms have similar complexity, with order O(I^2n^3) when n_T = n_R = n.The comparison concerns MIMO-SJBR, MIMO-MDP, and MIMO-WMMSE.
  • Complexity and signaling: The MIMO algorithms require exchanging pricing matrices, producing O(I^2 n_R^2) message exchange per iteration.The communication overhead differs from the SISO setting because users exchange matrices rather than vectors.
  • Numerical results: All algorithms reached the same average sum-rate in the reported simulations, while SJBR required fewer iterations than the alternatives.The experiments compare different user counts, normalized distances, and termination accuracies.
  • Numerical results: SJBR was about one order of magnitude faster at normalized distance d_ij/d_ii = 3, but only slightly faster or comparable to MIMO-WMMSE at d_ij/d_ii = 1.Its convergence speed was also reported as relatively insensitive to the number of users, while competing MIMO-MDP and MIMO-WMMSE methods required no tuning.

VIII. CONCLUSION

The paper concludes that its SCA-based decomposition computes stationary solutions for broad nonconvex sum-utility problems through convergent distributed Jacobi best-response algorithms. Experiments on SISO and MIMO interference channels show faster convergence than ad-hoc state-of-the-art methods with comparable computational complexity.

  • The framework computes stationary solutions of general nonconvex sum-utility problems, including social functions of complex variables.
  • Its main algorithmic result is a convergent distributed Jacobi class in which users simultaneously solve suitably convexified social problems, possibly inexactly.
  • Gradient algorithms and many block-coordinate descent schemes appear as special cases of the framework.
  • Experiments on SISO and MIMO interference channels found faster algorithms than ad-hoc state-of-the-art methods, with the same SISO complexity and similar or better MIMO complexity.
  • Future directions include adaptive step-size selection and extensions using only long-term channel statistics.

APPENDIX

The appendix establishes properties of the best-response mapping and proves convergence of the inexact Jacobi framework through descent arguments. Under the stated assumptions, limit points are stationary solutions, and the exact scheme excludes convergence to local maxima.

  • The convexified subproblem is uniformly strongly convex and has a gradient uniformly Lipschitz continuous in its reference point.
  • The best-response mapping is Lipschitz continuous, and its fixed points correspond to stationary solutions of the social problem.
  • The proof of the inexact scheme combines standard descent arguments with best-response properties and summable computation errors.
  • Coercivity and convergence of the objective sequence imply that the iterates are bounded and that every limit point is a fixed point, hence stationary.
  • For the exact scheme, the objective sequence decreases, so no limit point can be a local maximum.

C. Proof of Theorem 5

The proof interprets Algorithm 3 as an inexact Jacobi scheme and verifies the required error condition for each user's update. This establishes applicability of the general convergence theorem to the algorithm.

  • Algorithm 3 is analyzed by viewing it as an instance of the inexact Jacobi scheme from Algorithm 2.
  • The proof reduces convergence to verifying an error-bound condition for each user’s Step 2a update.
  • The required condition is established using the update error bound, Lipschitz continuity, the updating rule, and a finite positive constant.
Loading 1302.0756v2…