Source-linked AI summary
Global Convergence of ADMM in Nonconvex Nonsmooth Optimization
Yu Wang, Wotao Yin, Jinshan Zeng
TL;DR
The paper studies when ADMM converges for nonconvex, nonsmooth optimization with coupled linear equality constraints. It develops a global convergence analysis for a multi-block ADMM scheme under stated assumptions and applies it to broad objective and constraint classes. The results provide convergence guarantees across several application domains and include an example where ADMM converges while bounded-penalty ALM diverges.
Problem
The paper asks when ADMM converges for nonconvex, nonsmooth problems, where existing theory is limited despite successful applications and divergence examples.
Method
The paper analyzes a multi-block ADMM algorithm that sequentially updates primal variables and then the dual variable, using assumptions and techniques that accommodate broad nonconvex objectives, constraints, and matrix mappings.
Results
The analysis establishes global convergence guarantees for Algorithm 1 across broad nonconvex functions, nonconvex constraint sets, and applications in matrix decomposition, sparse recovery, machine learning, and manifold optimization.
Takeaways & Limitations
The results extend ADMM convergence theory to several nonconvex nonsmooth models and indicate that ADMM may converge in settings where bounded-penalty ALM diverges.
Takeaways & Limitations
The convergence guarantees depend on assumptions that the paper identifies as essential in general, including A2 and A5.
Abstract
from arXiv · showhide
In this paper, we analyze the convergence of the alternating direction method of multipliers (ADMM) for minimizing a nonconvex and possibly nonsmooth objective function, $φ(x_0,\ldots,x_p,y)$, subject to coupled linear equality constraints. Our ADMM updates each of the primal variables $x_0,\ldots,x_p,y$, followed by updating the dual variable. We separate the variable $y$ from $x_i$'s as it has a special role in our analysis. The developed convergence guarantee covers a variety of nonconvex functions such as piecewise linear functions, $\ell_q$ quasi-norm, Schatten-$q$ quasi-norm ($0<q<1$), minimax concave penalty (MCP), and smoothly clipped absolute deviation (SCAD) penalty. It also allows nonconvex constraints such as compact manifolds (e.g., spherical, Stiefel, and Grassman manifolds) and linear complementarity constraints. Also, the $x_0$-block can be almost any lower semi-continuous function. By applying our analysis, we show, for the first time, that several ADMM algorithms applied to solve nonconvex models in statistical learning, optimization on manifold, and matrix decomposition are guaranteed to converge. Our results provide sufficient conditions for ADMM to converge on (convex or nonconvex) monotropic programs with three or more blocks, as they are special cases of our model. ADMM has been regarded as a variant to the augmented Lagrangian method (ALM). We present a simple example to illustrate how ADMM converges but ALM diverges with bounded penalty parameter $β$. Indicated by this example and other analysis in this paper, ADMM might be a better choice than ALM for some nonconvex \emph{nonsmooth} problems, because ADMM is not only easier to implement, it is also more likely to converge for the concerned scenarios.
1 Introduction
The paper asks when multi-block ADMM converges for nonconvex, nonsmooth problems with coupled linear constraints, and develops a general convergence framework addressing this question. Its analysis covers broad objective and constraint classes, allows flexible block updates, and establishes convergence guarantees for several applications.
- Problem setting: ADMM is studied for possibly nonconvex, nonsmooth objectives subject to coupled linear equality constraints.The model separates the last variable y from the x_i blocks and incorporates additional variable constraints through indicator functions.
- Motivation: The paper addresses why ADMM often succeeds in applications despite limited convergence theory for nonconvex, nonsmooth problems and even divergence on some convex three-block problems.This motivates the central question of when ADMM-type algorithms converge in the presence of nonconvex nonsmooth functions.
- Method: Algorithm 1 generalizes ADMM to multiple variable blocks, sequentially minimizing the augmented Lagrangian over each primal block before updating y and the dual variable.The x_1,...,x_p blocks may be updated in arbitrary order provided x_0 is first and y is last; inexact, linearized, and prox-gradient variants can preserve the analysis principles.
- Convergence analysis: Under assumptions on the objective and matrices, Algorithm 1 is proved to converge, and it reduces to cyclic coordinate descent when all constraint matrices are zero.The analysis also develops techniques for rank-deficient linear mappings and uses restricted prox-regularity to handle some nonconvex nonsmooth objectives.
- ADMM versus ALM: A simple example shows bounded-penalty ALM can diverge while ADMM converges, illustrating a setting where ADMM may have an advantage for nonconvex nonsmooth problems.The paper reports that ALM diverges for bounded penalty sequences, whereas ADMM converges in finite steps for fixed β > 4 on that example.
- Scope and applications: The convergence conditions are weaker than prior assumptions and cover nonconvex functions and sets including MCP, SCAD, ℓq and Schatten-q penalties, manifolds, and complementarity constraints.The resulting guarantees apply to statistical regression, manifold-constrained optimization, matrix decomposition, sparse recovery, and related problems.
2 Main results
The paper establishes convergence of a multi-block ADMM under assumptions covering broad classes of nonconvex and nonsmooth objectives, with stronger global convergence under the Kurdyka–Łojasiewicz condition.
- Objective-function assumptions: Restricted prox-regularity extends the admissible objectives beyond convex and smooth functions to include nonsmooth nonconvex examples such as ℓ_q and Schatten-q quasi-norms.The framework also includes indicators of compact C2 manifolds.
- Objective-function assumptions: The analysis requires only coercivity over the feasible set, which is weaker than coercivity over the entire space.This assumption is automatic when the feasible set is bounded.
- Matrix and sub-minimization assumptions: Assumption A3 uses unique Lipschitz continuous sub-minimization paths for the y- and x_i-subproblems, weakening the usual full-column-rank requirement on A_i and B.The condition permits nontrivial null spaces while controlling the corresponding minimizers.
- Convergence theorems: Under A1–A3 and the stated regularity assumptions, Algorithm 1 generates a bounded sequence whose limit points are stationary for the augmented Lagrangian when β is sufficiently large.The result applies both to a decoupled objective with regularity conditions on f and h and to a coupled Lipschitz-differentiable objective.
- Convergence theorems: If the augmented Lagrangian is a Kurdyka–Łojasiewicz function, the entire sequence converges to a unique limit point.The paper notes that real analytic and semi-algebraic functions satisfy the KL property.
- Convergence theorems: Theorem 2 provides the same subsequential and global convergence conclusions when x and y are coupled, provided the full objective is Lipschitz differentiable.Theorem 1 instead treats decoupled x and y objectives with potentially nonsmooth nonconvex components.
3 Proof
The proof establishes global convergence by showing boundedness, sufficient descent, subgradient control, and limiting continuity for the ADMM iterates. Under a Kurdyka–Łojasiewicz condition, every sequence converges to a stationary point, with additional rate guarantees.
- Convergence framework: Proposition 2 shows that P1–P4 guarantee at least one limit point, and every limit point is stationary.Stationarity is expressed as 0 ∈ ∂Lβ(x*, y*, w*).
- Global convergence: If Lβ is a K L function, the full sequence (xk, yk, wk) converges globally to a unique point (x*, y*, w*).Here, “globally” means regardless of the initial point.
- Proof mechanisms: The sufficient-descent and subgradient properties are obtained from the block-update inequalities, y and w updates, and restricted prox-regularity conditions.The analysis relaxes a stronger condition by introducing an exclusion set, which is needed for functions such as the ℓq quasi-norm.
- Descent and boundedness: For sufficiently large β, the augmented Lagrangian is lower bounded and decreasing, while the iterate sequence remains bounded.Lemma 6 establishes monotonicity, convergence of Lβ, and boundedness of {xk, yk, wk}.
- Asymptotic regularity: The proof derives asymptotic regularity: Byk−Byk+1 and wk−wk+1 both converge to zero.These limits follow from the descent and boundedness lemmas together with the dual-primal bound.
- Special case: For piecewise linear fi, sufficiently large β yields the boundedness properties required by the convergence framework.The threshold depends on the stated constants and an arbitrary ε0.
4 Discussion
The discussion compares the paper’s convergence assumptions with related ADMM analyses, examines essential assumptions and update-order effects, and extends the result to inexact subproblem solutions.
- Comparison with related work: The paper’s assumptions are more general than several related works, including more flexible objective functions and matrix conditions.The comparisons include coupled Lipschitz-differentiable terms, restricted prox-regular or piecewise-linear parts, and potentially rank-deficient matrices.
- Tightness of assumptions: A2 is indispensable because, without it, ADMM may fail to find a feasible point, even when A1 and A4–A5 hold.The paper gives examples satisfying A1 and A4–A5 but violating A2.
- Tightness of assumptions: A5 is also indispensable: without smoothness of h, the dual sequence can no longer be controlled by the y-sequence and may diverge.The cited example satisfies all assumptions except A5 and produces a divergent sequence for any β > 0.
- Primal update order: The convergence theorem permits arbitrary orderings of x1,…,xp across iterations, provided x0 is first and y is last before the multiplier update.Alternating the broader primal update order can produce divergence, whereas fixed admissible orders converge in the cited example.
- Inexact optimization: Inexact subproblem solutions preserve the convergence result when their errors are summable, although specific inexact algorithms may require additional conditions.The extension assumes bounded iterates, sufficient descent, and a subgradient bound.
5 Applications
The paper applies its convergence theory to statistical learning, compact-set and manifold optimization, complementarity constraints, and matrix decomposition, obtaining stationary-point guarantees under suitable conditions.
- Overview: The applications section reports novel convergence results for several well-known nonconvex optimization models.The stated application areas include statistical learning, compact manifolds, complementarity constraints, and matrix decomposition.
- Statistical learning: For statistical learning models with suitable coercivity and smoothness assumptions, Algorithm 2 has limit points that are stationary points of the augmented Lagrangian.The covered regularizers include ℓq quasi-norms, SCAD, MCP, and piecewise-linear functions.
- Compact manifolds: For minimization over compact sets, Algorithm 3 has at least one limit point, and every limit point is stationary for sufficiently large β when J is Lipschitz differentiable.Compact manifolds such as spherical, Stiefel, and Grassmann manifolds are included as examples of compact sets.
- Complementarity constraints: For smooth optimization over complementarity constraints, ADMM has limit points that are stationary points of the augmented Lagrangian when h is Lipschitz differentiable and coercive over the complementarity set.The formulation includes mathematical programs with equilibrium constraints and linear complementarity problems as special cases.
- Matrix decomposition: For the matrix decomposition model, Algorithm 4 has at least one limit point, and every limit point is stationary for sufficiently large β.The model permits any lower-bounded lower-semicontinuous penalty p(X), including the Schatten-q quasi-norm for 0 < q ≤ 1.
6 Conclusion
The conclusion presents global convergence results for multi-block ADMM on nonconvex nonsmooth problems and identifies the update ordering needed to avoid divergence.
- Contributions: The paper establishes convergence of multi-block cyclic ADMM for coupled linear-equality problems with nonconvex and nonsmooth objectives.The objective may contain specified nonconvex nonsmooth terms while retaining a smooth h(y) component.
- Scope: The guarantees cover ℓq and Schatten-q quasi-norms, SCAD, and other nonconvex functions, as well as spheres, matrix manifolds, and complementarity constraints.These extensions relax previous assumptions such as semi-convexity.
- Update order: The middle blocks may be reordered between iterations, but x0 must be updated first and y last, immediately before the multiplier.The paper states that other ordering choices can lead to divergent iterates.
- Applications: The results yield convergence guarantees for applications in matrix decomposition, sparse recovery, machine learning, and optimization on compact smooth manifolds.The conclusion describes these guarantees as novel.
Appendix
The appendix supplies technical proofs and examples supporting the convergence theory, including well-defined subproblems, prox-regularity, boundedness, and contrasting ADMM and ALM behavior.
- Prox-regularity: The appendix verifies restricted prox-regularity for Schatten-q quasi-norms and indicators of compact C2 manifolds.The Schatten-q argument uses local Lipschitz continuity, while the manifold argument uses compactness and C2 charts.
- Subproblem well-posedness: The y-subproblem is well defined when β exceeds the stated smoothness-dependent threshold because its objective is coercive with respect to By.Lower semicontinuity and uniqueness for fixed By complete the existence argument.
- Boundedness: The convergence proof bounds the augmented Lagrangian and then uses A1 to bound the primal iterates, which in turn bounds the dual sequence.The proof explicitly connects bounded objective values to bounded iterates and multipliers.