Source-linked AI summary
On the Global Linear Convergence of the ADMM with Multi-Block Variables
Tianyi Lin, Shiqian Ma, Shuzhong Zhang
TL;DR
The paper addresses whether standard ADMM converges for convex optimization with N≥3 linked variable blocks, given that convergence can fail without additional conditions. It analyzes conditions for the original multi-block method and proves global linear convergence in three scenarios, while identifying constraints on two scenarios.
Problem
For convex optimization with N≥3 linked blocks, ADMM convergence was unclear because the method may fail without further conditions.
Method
The paper analyzes the original Gauss-Seidel multi-block ADMM and identifies three condition scenarios for global linear convergence.
Results
The authors prove global linear convergence for the original standard multi-block ADMM when N≥3.
Takeaways & Limitations
The results provide convergence guarantees for a widely used multi-block ADMM under conditions relevant to large-scale convex optimization models.
Takeaways & Limitations
Scenarios 2 and 3 require all constraint sets X_i to be the whole space, while scenario 1 essentially requires only x_N to be unconstrained.
Abstract
from arXiv · showhide
The alternating direction method of multipliers (ADMM) has been widely used for solving structured convex optimization problems. In particular, the ADMM can solve convex programs that minimize the sum of $N$ convex functions with $N$-block variables linked by some linear constraints. While the convergence of the ADMM for $N=2$ was well established in the literature, it remained an open problem for a long time whether or not the ADMM for $N \ge 3$ is still convergent. Recently, it was shown in [3] that without further conditions the ADMM for $N\ge 3$ may actually fail to converge. In this paper, we show that under some easily verifiable and reasonable conditions the global linear convergence of the ADMM when $N\geq 3$ can still be assured, which is important since the ADMM is a popular method for solving large scale multi-block optimization models and is known to perform very well in practice even when $N\ge 3$. Our study aims to offer an explanation for this phenomenon.
1 Introduction
The paper studies standard ADMM for convex problems with N≥3 linked variable blocks, where convergence had been unclear and could fail without additional conditions. It establishes global linear convergence for the original multi-block method under stated conditions.
- Problem formulation: The problem minimizes a sum of N convex functions over block variables linked by one linear constraint.The formulation uses closed convex functions, closed convex sets, and matrices A_i linking x_i through ΣA_i x_i=b.
- ADMM method: Standard multi-block ADMM updates the primal variables x_1,…,x_N in Gauss-Seidel order using an augmented Lagrangian.The augmented Lagrangian uses multiplier λ and penalty parameter γ>0.
- Prior convergence results: For N=2, ADMM convergence was established through its equivalence to Douglas-Rachford operator splitting, with later sublinear and linear results also reported.The cited convergence results in this discussion all concern the two-block case.
- Open multi-block question: For N≥3, convergence remained unclear, and a recent counterexample showed that standard ADMM may fail to converge without further conditions.Existing sufficient-condition results and modified multi-block variants were studied separately.
- Contribution: The paper proves global linear convergence for the original standard multi-block ADMM when N≥3.The authors distinguish their result from prior two-block results, local results, and a variant using a small dual step size.
2 Preliminaries and Technical Lemmas
This section motivates multi-block ADMM, compares standard Gauss-Seidel updates with modified variants, and develops assumptions and technical lemmas for proving global linear convergence.
- Motivation and comparisons: Multi-block ADMM can outperform modified methods in practice, although standard convexity alone does not guarantee convergence.The comparison concerns Gauss-Seidel ADMM, proximal Jacobian ADMM, corrected Jacobian ADMM, and variable-splitting ADMM.
- Assumptions and notation: The analysis assumes a non-empty primal-dual optimal set and uses σ_i to quantify each function’s convexity.A positive σ_i corresponds to strong convexity, while σ_i = 0 for convex functions that are not strongly convex.
- Convergence scenarios: The paper identifies three scenarios whose conditions are designed to yield global linear convergence of the standard multi-block ADMM.The scenarios and their conditions are summarized in Table 2.
- Technical lemmas: The technical analysis follows Gauss-Seidel primal updates, derives first-order optimality relations, and establishes inequalities used to control primal and dual iterates.The proof repeatedly combines subproblem optimality conditions with the multiplier update and norm identities.
- Technical lemmas: Under scenarios 2 or 3 and suitable conditions on γ, the generated iterates converge to a primal-dual optimal solution.Scenario 2 uses strong convexity of f1, whereas scenario 3 uses full column rank of A1 to obtain convergence of x1.
3 Global Linear Convergence of the ADMM
Under three scenarios, the standard multi-block ADMM is proved globally linearly convergent for N≥3, with corresponding R-linear convergence of iterates under additional rank conditions. The paper also gives an inequality-constrained extension and numerical evidence from randomly generated instances.
- Global convergence results: The analysis establishes global linear convergence of the standard multi-block ADMM under three scenarios with suitable penalty-parameter conditions.The three results are stated in Theorems 3.1–3.3.
- R-linear convergence: The resulting primal-variable sequences converge R-linearly under the conditions of Theorems 3.1, 3.2, or 3.3.Additional full-column-rank assumptions on A_i for i=1,...,N−1 yield R-linear convergence of the corresponding variables.
- Limitations: The scope remains limited for fully constrained block variables because the paper leaves open whether linear convergence holds when all blocks are constrained.Scenarios 2 and 3 require the constraint sets to be the whole space, whereas scenario 1 permits most blocks to be constrained.
- Extensions: Scenario 1 also provides a linear convergence rate for convex optimization problems with inequality constraints after introducing a nonnegative slack variable.Theorem 3.1 applies when all objective functions are strongly convex, ∇f_N is Lipschitz continuous, x_N is unconstrained, and A_N has full row rank.
- Numerical illustration: The numerical example tests a three-block quadratic problem over 100 iterations and reports linear convergence for all tested randomly generated instances.Two plotted instances use γ=1.79×10^-2 and γ=1.70×10^-2, respectively, with δ_1=1.01×10^-2 in both cases.
4 Conclusions
The paper establishes linear convergence for the original multi-block ADMM under suitable conditions and highlights its importance for large-scale convex optimization.
- The original ADMM for convex optimization with multi-block variables is linearly convergent under specified conditions.
- The paper presents three scenarios guaranteeing a linear convergence rate for the multi-block ADMM.
- Convergence and complexity analysis are important because ADMM is widely used for large-scale models in image processing, statistics, and machine learning.