Source-linked AI summary
Convergence Analysis of Alternating Direction Method of Multipliers for a Family of Nonconvex Problems
Mingyi Hong, Zhi-Quan Luo, Meisam Razaviyayn
TL;DR
The paper studies how to establish convergence guarantees for ADMM on certain nonconvex consensus and sharing problems, where existing theory is limited. It analyzes classical and flexible proximal variants under regularity conditions and sufficiently large penalty parameters. The resulting guarantees place iterates or limit points at stationary solutions without assumptions on the generated iterates, with sharing-problem convergence independent of the number of variable blocks.
Problem
ADMM is widely used for nonconvex optimization, but its convergence theory remains limited beyond special convex settings and often relies on restrictive assumptions about the iterates.
Method
The paper analyzes classical, flexible, and proximal ADMM variants for selected nonconvex consensus and sharing problems under regularity conditions and sufficiently large penalty parameters.
Results
The analyzed ADMM methods converge to stationary solutions for the selected nonconvex problems, and sharing-problem convergence does not depend on the number of variable blocks.
Takeaways & Limitations
The analysis supplies theoretical justification for ADMM in these nonconvex settings while covering flexible block schedules and proximal updates without assumptions on generated iterates.
Takeaways & Limitations
The convergence claims require problem-specific assumptions, including conditions such as D1; without D1, decreasing augmented Lagrangian values alone do not ensure convergence to stationary solutions.
Abstract
from arXiv · showhide
The alternating direction method of multipliers (ADMM) is widely used to solve large-scale linearly constrained optimization problems, convex or nonconvex, in many engineering fields. However there is a general lack of theoretical understanding of the algorithm when the objective function is nonconvex. In this paper we analyze the convergence of the ADMM for solving certain nonconvex consensus and sharing problems, and show that the classical ADMM converges to the set of stationary solutions, provided that the penalty parameter in the augmented Lagrangian is chosen to be sufficiently large. For the sharing problems, we show that the ADMM is convergent regardless of the number of variable blocks. Our analysis does not impose any assumptions on the iterates generated by the algorithm, and is broadly applicable to many ADMM variants involving proximal update rules and various flexible block selection rules.
1. Introduction.
The paper addresses limited convergence theory for ADMM beyond two-block convex problems, especially when objectives are nonconvex. It establishes convergence for selected nonconvex consensus and sharing problems under sufficiently large penalty parameters, without assumptions on generated iterates.
- ADMM has strong practical use in large-scale linearly constrained optimization, including machine learning, computer vision, signal processing, and networking.The paper notes that ADMM often converges faster in practice than dual ascent and the method of multipliers.
- Most existing convergence analysis focuses on two-block convex separable problems, while multi-block convex ADMM can diverge on pathological examples.For two-block convex problems, convergence is established under mild conditions, with sublinear and sometimes linear rates under additional assumptions.
- When objectives are nonconvex, ADMM convergence remains largely open despite strong empirical performance across applications such as matrix factorization, phase retrieval, clustering, and tensor decomposition.The paper presents this gap as a mismatch between practical use and theoretical understanding.
- Prior nonconvex analyses often assume that limit points exist and successive primal and dual iterate differences vanish, assumptions described as nonstandard and overly restrictive.The paper asks whether convergence can be established without assumptions imposed directly on the iterates.
- For a class of nonconvex consensus and sharing problems, sufficiently large penalty parameters and regularity conditions guarantee convergence to stationary solutions without assumptions on the iterates.The paper states that computable bounds for the penalty parameter are available.
- The analysis covers ADMM variants with per-block proximal updates and flexible block-selection rules.The stated algorithmic framework includes primal-variable updates and dual-variable updates within ADMM.
2. The Nonconvex Consensus Problem.
The paper formulates a nonconvex consensus problem for distributed solution and analyzes classical, flexible, and proximal ADMM variants. Under regularity conditions and sufficiently large penalty parameters, these methods converge to stationary solutions under specified update rules.
- Problem formulation: The consensus formulation permits each distributed agent to handle one local variable and local function, although reformulation increases problem dimension and may require more iterations than centralized methods.Its main benefit is distributed flexibility rather than guaranteed iteration efficiency.
- Classical ADMM: Classical ADMM sequentially updates the two primal blocks and then performs an inexact dual ascent step.The formulation uses x0 and the collection {xk} as the two primal blocks.
- Flexible updates: Flexible ADMM allows randomized or period-T essentially cyclic block-selection rules, including updates in which selected primal and dual variables are computed at each iteration.The generalized method includes the classical algorithm as a special case.
- Convergence mechanism: With sufficiently large penalty parameters, the augmented Lagrangian decreases or converges under the stated assumptions for the analyzed ADMM variants.The required penalty bounds are described as computable, and sufficiently large parameters can satisfy the decrease condition.
- Convergence results: Any limit point of the classical and proximal flexible ADMM sequences is a stationary solution, and compactness of X yields convergence to the set of stationary solutions.The classical result covers essentially cyclic updates deterministically and randomized updates almost surely; the proximal result is stated for period-T essentially cyclic updates.
- Proximal ADMM: The proximal extension replaces exact subproblem minimization with proximal steps, addressing the limitation that exact solves may be impractical when cheap iterations are preferred.Its convergence theorem requires Assumptions A1, A3, and B together with period-T essentially cyclic block updates.
3. The Nonconvex Sharing Problem.
The paper formulates a nonconvex sharing problem as a linearly constrained problem and analyzes flexible ADMM variants under regularity and sufficiently large penalty conditions. The resulting algorithms converge to stationary solutions, including with cyclic or randomized block updates, and extend to proximal variants.
- Problem formulation: The sharing problem introduces x0 so agent variables are coupled through ℓ and satisfy Akxk = x0.This reformulation yields a single linear constraint and K + 1 variable blocks.
- Algorithm: The flexible ADMM permits period-T essentially cyclic or randomized block-selection rules.At each iteration, selected agent blocks and possibly x0 are updated before the dual variable.
- Assumptions: Convergence analysis assumes closed convex sets, full-column-rank Ak matrices, lower-bounded objectives, regularity of gk, and a sufficiently large penalty parameter ρ.The assumptions allow smooth nonconvex or convex possibly nonsmooth gk, while requiring smooth coupling and strong convexity of subproblems under the stated conditions.
- Convergence results: The algorithm converges deterministically under essentially cyclic updates and almost surely under randomized updates.The theorem applies to the nonconvex consensus formulation and establishes the corresponding convergence modes under Assumption C.
- Convergence results: If every Xk is compact, Algorithm 4 converges to the set of stationary solutions of the nonconvex sharing problem.The result also specializes to convex objectives without requiring small dual stepsizes or strong convexity, and proximal extensions can remove the strong-convexity requirement.
- Extensions: The analysis extends to proximal flexible ADMM, allowing inexact and simpler block updates with carefully bounded penalty and proximal coefficients.The proof follows the same general strategy as the preceding convergence analysis.
4. Extensions.
The extension uses Assumption D to establish feasibility and stationarity for broader ADMM settings, while clarifying its requirements and limitations.
- Assumption D requires well-defined iterations with a uniformly lower-bounded augmented Lagrangian.Without this lower bound, the augmented Lagrangian may decrease while tending to −∞, preventing a convergence claim to stationary solutions.
- The assumptions allow smooth nonconvex or nonsmooth convex block objectives and a smooth coupling function that is blockwise convex but not jointly convex.They also require closed convex constraint sets and feasibility of the linearly constrained problem.
- A sufficiently large penalty parameter makes each subproblem strongly convex, with ργk(ρ) > 2σ required for all blocks.The strong-convexity modulus γk(ρ) is nondecreasing in ρ.
- Under Assumption D, the primal feasibility gap converges to zero and every limit point of the iterate sequence is a stationary solution.This conclusion extends the convergence argument to the broader problem setting considered in the section.
- Assumption D is made on the iterates rather than directly on the problem, so its validity must be verified separately for each linearly constrained problem.The paper notes that this remains a drawback even though it verifies the conditions for the consensus and sharing problems.
- For a two-variable family with invertible A, convergence follows when ρ > Lg/λmin(AAT), while a weaker condition permits the x1 subproblem to be convex without strong convexity.The stated bound verifies D1, and sufficiently large ρ together with invertibility of A verifies D4.