Source-linked AI summary
On the Convergence of Alternating Direction Lagrangian Methods for Nonconvex Structured Optimization Problems
Sindri Magnússon, Pradeep Chathuranga Weeraddana, Michael G. Rabbat, Carlo Fischione
TL;DR
Large-scale structured optimization has important nonconvex applications, but convergence guarantees for scalable methods in this regime are difficult to establish. This paper analyzes alternating-direction penalty and multiplier methods and gives conditions for asymptotic feasibility or first-order convergence, including a characterized class for ADMM.
Problem
The paper studies the lack of established convergence guarantees for scalable methods applied to structured nonconvex optimization problems.
Source: §I · p. 1, A. Problem Statement · p. 2Method
The authors analyze ADPM, which alternates primal updates with a growing penalty, and ADMM, an alternating-direction multiplier method.
Source: C. Alternating Direction Lagrangian… · p. 3, A. Algorithm Description · p. 7Results
ADPM asymptotically achieves primal feasibility under stated assumptions, with additional sufficient conditions for FON convergence; ADMM has sufficient FON-convergence conditions and a characterized low-dimensional problem class.
Source: §VI · p. 12Takeaways & Limitations
The methods are illustrated on nonconvex cooperative localization in wireless sensor networks.
Source: §VI · p. 12For ADPM, general characterization of the objective value after convergence is technically challenging without convexity of the objective functions.
Source: C. Algorithm properties: Constrained… · p. 7
Abstract
from arXiv · showhide
Nonconvex and structured optimization problems arise in many engineering applications that demand scalable and distributed solution methods. The study of the convergence properties of these methods is in general difficult due to the nonconvexity of the problem. In this paper, two distributed solution methods that combine the fast convergence properties of augmented Lagrangian-based methods with the separability properties of alternating optimization are investigated. The first method is adapted from the classic quadratic penalty function method and is called the Alternating Direction Penalty Method (ADPM). Unlike the original quadratic penalty function method, in which single-step optimizations are adopted, ADPM uses an alternating optimization, which in turn makes it scalable. The second method is the well-known Alternating Direction Method of Multipliers (ADMM). It is shown that ADPM for nonconvex problems asymptotically converges to a primal feasible point under mild conditions and an additional condition ensuring that it asymptotically reaches the standard first order necessary conditions for local optimality are introduced. In the case of the ADMM, novel sufficient conditions under which the algorithm asymptotically reaches the standard first order necessary conditions are established. Based on this, complete convergence of ADMM for a class of low dimensional problems are characterized. Finally, the results are illustrated by applying ADPM and ADMM to a nonconvex localization problem in wireless sensor networks.
I. INTRODUCTION
The paper addresses the gap between scalable methods for structured optimization and the limited convergence theory for nonconvex problems. It studies a separable, linearly coupled problem and explains why centralized penalty methods must be adapted for distributed execution.
I. INTRODUCTION
- Structured large-scale nonconvex applications are common, but their theoretical guarantees are less established than those for convex problems.The paper cites recommender systems, wireless sensor localization, smart-grid power flow, and LDPC decoding as examples.Source: §I · p. 1
A. Related Literature
- Prior work reported appealing nonconvex ADMM behavior numerically, while theoretical convergence guarantees in the nonconvex regime remained absent.The related-work discussion also notes that diminishing step sizes can yield poor convergence rates for gradient-based methods.Source: A. Related Literature · pp. 1–2
B. Notation and Definitions
- The paper defines FON conditions through primal and dual feasibility, complementary slackness, and a vanishing Lagrangian gradient.These conditions provide the first-order optimality notion used in the paper.Source: B. Notation and Definitions · p. 2
A. Problem Statement
- The studied problem minimizes separable functions of x and z subject to the affine coupling constraint Ax+Bz=c, a form that includes consensus and sharing problems.In network settings, x can represent private agent variables and z the coupling between agents.Source: A. Problem Statement · p. 2
B. Penalty and Augmented Lagrangian Methods
- The quadratic penalty method increases its penalty parameter toward infinity, whereas the method of multipliers updates multipliers to seek convergence without that requirement.Under bounded multipliers, the cited quadratic-penalty result states that every limit point is a global minimum; the method of multipliers is generally local for nonconvex problems.Source: B. Penalty and Augmented Lagrangian… · pp. 2–3
- Despite separable structure, classical penalty and augmented Lagrangian methods require a centralized joint primal update, so their convergence assertions do not cover splitting it into distributed steps.This motivates adapting the methods to allow separate x- and z-updates.Source: B. Penalty and Augmented Lagrangian… · p. 3
C. Alternating Direction Lagrangian Methods
The paper introduces alternating direction Lagrangian methods (ADLM), splitting primal optimization into x- and z-steps. It analyzes the ADPM and ADMM variants under distinct conditions and illustrates their application to cooperative wireless-sensor localization.
C. Alternating Direction Lagrangian Methods
- ADLM splits the primal optimization into two steps, first in x and then in z, and includes ADPM and ADMM variants.ADPM follows a quadratic-penalty approach, while ADMM is the classic method-of-multipliers variant.Source: C. Alternating Direction Lagrangian… · p. 3
D. Contribution and Structure of the Paper
- For unconstrained ADPM, the paper states that zero multipliers and a penalty parameter tending to infinity yield asymptotic primal feasibility; with further conditions, convergent iterates satisfy FON conditions.The additional conditions include a nonsummable sequence of reciprocal penalties and convergence of the primal iterates.Source: D. Contribution and Structure of the… · p. 3
- For constrained ADPM, convex sets and a summable reciprocal-penalty sequence give asymptotic primal feasibility with bounded multiplier sequences.The paper also gives an example illustrating why convexity of the sets is needed in general.Source: D. Contribution and Structure of the… · p. 3
- For ADMM with fixed penalty, convergence of the multipliers implies that every limit point satisfies FON conditions, even when the constraint sets may be nonconvex.The paper also characterizes convergence for a class of problems, determining the limit point from the initialization.Source: D. Contribution and Structure of the… · p. 3
- The paper illustrates the methods by applying them to distributed cooperative localization in wireless sensor networks.Source: D. Contribution and Structure of the… · p. 3
III. ALTERNATING DIRECTION PENALTY METHOD
This section studies ADPM convergence for the stated problem in unconstrained and constrained settings.
III. ALTERNATING DIRECTION PENALTY METHOD
- The section introduces ADPM and studies its properties for unconstrained and constrained variable sets.Source: §III · p. 3
A. Algorithm Description
ADPM alternates minimization of the augmented Lagrangian over x and z, while its penalty parameter grows and its multiplier sequence remains bounded. The section describes conditions and problem structures that can make these updates tractable.
A. Algorithm Description
- ADPM alternates x- and z-minimization of the augmented Lagrangian, with the penalty parameter tending to infinity and the multiplier sequence bounded.The x- and z-updates are the algorithm's main optimization steps.Source: A. Algorithm Description · p. 4
- When the feasible set is convex, the objective is twice continuously differentiable with a lower-bounded Hessian, and the relevant constraint matrix has full column rank, a sufficiently large penalty makes an update strongly convex.The stated threshold is ρ(t) > −α/λmin(A^T A) for the x-update (with the analogous condition for z).Source: A. Algorithm Description · p. 4
- For an indefinite quadratic objective, positivity of its quadratic form on the null space of A suffices for convexity of the x-update at sufficiently large penalty.Source: A. Algorithm Description · p. 4
- If the objective is separable across uncoupled low-dimensional x-blocks, the x-update is separable and can use global methods such as branch and bound.Source: A. Algorithm Description · p. 4
B. Algorithm Properties: Unconstrained Case
For the unconstrained case, the stated ADPM results establish primal feasibility and, with additional sequence and convergence conditions, first-order necessary (FON) conditions. The analysis relies on assumptions that ensure bounded iterates.
B. Algorithm Properties: Unconstrained Case
- ADPM satisfies primal feasibility in the unconstrained case; if the iterates converge and the reciprocal penalty sequence is nonsummable, their limit satisfies the FON conditions.The stated assumptions include X = R^n and Z = R^m.Source: B. Algorithm Properties: Unconstrained… · p. 4
- The analysis assumes g(x)=0, A=I, c=0, and full-column-rank B, plus either a bounded gradient or the stated norm and gradient-sign conditions.The latter conditions imply bounded iterates under the lemma’s stated bound on z(t).Source: B. Algorithm Properties: Unconstrained… · p. 4
- The paper also reports that updating y by the usual residual recursion can be beneficial numerically, although the proposition analyzes y(t)=0.The recursion is y(t+1)=y(t)+ρ(x(t+1)−Bz(t+1)).Source: B. Algorithm Properties: Unconstrained… · pp. 4–5
C. Algorithm properties: Constrained Case
For compact convex constraint sets, ADPM’s primal residual converges to zero under the stated regularity and penalty-growth assumptions, without requiring convex objectives. The section also shows that nonconvex sets can invalidate feasibility and notes that general objective-value properties are difficult to characterize.
C. Algorithm properties: Constrained Case
- The feasibility result requires convex constraint sets, but makes no convexity assumption on f or g.The paper identifies the convexity of X and Z as essential for guaranteeing primal feasibility in general.Source: C. Algorithm properties: Constrained… · p. 5
- Under the stated assumptions, ADPM’s primal residual converges to zero when X and Z are convex and compact and the penalty sequence grows at the specified rate.The assumptions also include continuously differentiable f and g, Slater’s condition for each set, and full-column-rank A and B.Source: C. Algorithm properties: Constrained… · pp. 5–6
- With nonconvex sets, ADPM can converge to an infeasible point: for the described initialization and y(t)=0, the iterates converge to (0,0).The example states that (0,0) is infeasible.Source: C. Algorithm properties: Constrained… · p. 7, Figure 1 · p. 7
- Because differentiability is weaker than objective convexity, general properties of ADPM’s objective value after convergence are technically challenging to characterize.The paper describes ADPM as resembling a sequential optimization approach and reports numerical experiments on its objective-value behavior.Source: C. Algorithm properties: Constrained… · p. 7
IV. ALTERNATING DIRECTION METHOD OF MULTIPLIERS
The paper introduces its nonconvex ADMM analysis, with the algorithm specified next and convergence properties examined afterward.
IV. ALTERNATING DIRECTION METHOD OF MULTIPLIERS
- The section investigates general properties of ADMM in a nonconvex setting and separates the algorithm description from the convergence analysis.The algorithm is stated in Section IV-A, followed by convergence properties in Section IV-B.Source: §IV · p. 7
A. Algorithm Description
ADMM alternates primal-variable updates, then updates the multiplier and checks a stopping criterion. Its penalty parameter is fixed, and the convergence assertions do not require globally solved subproblems.
A. Algorithm Description
- Each iteration initializes or carries forward z, y, and ρ, updates x and z by optimization, updates y, and checks whether to stop.If the stopping criterion is unmet, the algorithm advances to the next iteration.Source: A. Algorithm Description · p. 7
- ADMM uses a fixed penalty parameter, and the convergence assertions require only that each subproblem solution be a local minimum, not a global one.The paper states that such local or global subproblem solutions suffice for its convergence results.Source: A. Algorithm Description · p. 7
B. Algorithm Properties
For nonconvex ADMM, convergent dual variables and the stated regularity and subproblem assumptions ensure that every primal limit point satisfies the problem’s first-order necessary conditions (FON). In a scalar setting with ρ>L and a specified initialization, the paper further characterizes convergence using the starting point.
ADMM convergence
- Regularity and constraint qualifications yield locally valid multipliers for the update subproblems, which are used to establish the limit-point FON result.The argument establishes eventual linear independence of active constraint gradients and existence of suitable multipliers along convergent subsequences.Source: B. Algorithm Properties · p. 8
- If the ADMM dual sequence converges and Assumptions 3, 7, 8, and 9 hold, every primal limit point satisfies the FON conditions.The subproblems must be solved locally or globally; the result applies even when the objective or feasible sets are nonconvex.Source: B. Algorithm Properties · pp. 8–9
Scalar ADMM characterization
- When the primal and dual sequences converge, the primal limit satisfies FON; in the scalar case, the algorithm either converges or diverges to ±∞.The scalar characterization assumes f,g:R→R, x=z, L-Lipschitz derivatives, ρ>L, and y(0)=g′(z(0)).Source: B. Algorithm Properties · p. 9
- Under those scalar assumptions, the limit is the closest stationary point in the direction where f+g decreases; if none exists in that direction, the iterates diverge.The limiting point is determined by z(0) and the sign of f′(z(0))+g′(z(0)).Source: B. Algorithm Properties · pp. 9–10
Scope
- The scalar characterization does not extend directly to multiple dimensions because identifying the direction toward a stationary point is the stated challenge.The paper notes that this direction is readily obtained in the one-dimensional case, unlike the multidimensional case.Source: B. Algorithm Properties · p. 10
V. APPLICATION: COOPERATIVE LOCALIZATION IN WIRELESS SENSOR NETWORKS
The paper applies its alternating direction Lagrangian methods to cooperative localization by reformulating the problem in consensus form with local copies at each node. The resulting distributed procedure supports either ADPM or ADMM updates and can be compared fairly with distributed gradient descent using the same communication.
Distributed formulation
- The localization problem is reformulated in consensus form by giving each node a local copy of neighboring sensor locations and enforcing consistency with global variables.The application estimates sensor locations from squared-distance measurements on graph edges; the stated maximum-likelihood problem is NP-hard.Source: §V · pp. 10–11
Distributed algorithm
- In D-ADLM, each node solves a local optimization, nodes average to update z, and local penalty and dual variables are updated.The distributed procedure can use ADPM or ADMM, depending on how ρ and y are updated.Source: §V · p. 11
Comparison method
- The D-GD baseline uses the same communication as D-ADLM but replaces its optimization subproblem with a gradient-descent step.The authors present this shared communication requirement as making D-GD a fair comparison.Source: §V · p. 11
A. Numerical Results
On the test network, all algorithms show decreasing consensus and gradient measures, with ADMM variants generally having faster gradient-norm decay. All methods produce estimates close to true locations, while ADMM-1 and ADMM-10 obtain better objective values than the visually closer DGD estimates for two nodes.
Test-network results
- ADMM-1 and ADMM-10 show faster gradient-norm decay than DGD, ADPM, and ADPM-y, while all algorithms show decreasing consensus and gradient measures.Fig. 2 plots scaled consensus and gradient norms against iterations; together these quantities comprise the stated FON conditions.Source: A. Numerical Results · p. 12, Figure 2 · p. 12
- The dual variables shown for ADMM-1 and ADMM-10 converge, which the authors use with Proposition 3 to infer their convergence.The paper reports similar behavior for the other dual variables.Source: A. Numerical Results · p. 12
- ADMM-1 and ADMM-10 have better objective values, although DGD gives visually better estimates for the diamond and five-pointed-star nodes.All algorithms converge to estimates described as close to the true node locations despite the nonconvex objective.Source: A. Numerical Results · p. 12, Figure 3 · p. 12
Observed stability
- DGD was unstable for many initializations, reaching floating-point infinity within a few iterations.The paper separately states that bounded dual variables are required for the analogous bounded-sequence results for ADPM-y and the ADMM variants.Source: A. Numerical Results · p. 12
VI. CONCLUSIONS
The paper establishes convergence conditions for scalable variants of ADPM and ADMM in nonconvex optimization, then applies them to distributed cooperative localization in wireless sensor networks.
VI. CONCLUSIONS
- ADPM asymptotically reaches primal feasibility under assumptions that hold widely in practice.The paper also gives sufficient conditions for ADPM to asymptotically reach first-order necessary conditions for optimality.Source: §VI · p. 12
- For ADMM, the paper provides sufficient conditions for asymptotic convergence to first-order necessary conditions for local optimality.It identifies a class of problems where those conditions hold.Source: §VI · p. 12
- The paper demonstrates how ADPM and ADMM can be used to design distributed algorithms for nonconvex cooperative localization in wireless sensor networks.Source: §VI · p. 12
- ADPM and ADMM are studied as scalable variants of the Quadratic Penalty Method and Method of Multipliers, respectively.Source: §VI · p. 12