On the Global Linear Convergence of the ADMM with Multi-Block Variables

Abstract

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\ge 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.

References in corpus (5)

• On the Linear Convergence of the Alternating Direction Method of Multipliers
• Solving Multiple-Block Separable Convex Minimization Problems Using Two-Block Alternating Direction Method of Multipliers
• Parallel Multi-Block ADMM with o(1/k) Convergence
• A Three-Operator Splitting Scheme and its Optimization Applications
• Iteration Complexity Analysis of Multi-Block ADMM for a Family of Convex Minimization without Strong Convexity

Cited by in corpus (7)

• Convergence Analysis of Alternating Direction Method of Multipliers for a Family of Nonconvex Problems
• On the Efficiency of Random Permutation for ADMM and Coordinate Descent
• Global Convergence of Unmodified 3-Block ADMM for a Class of Convex Minimization Problems
• A Majorized ADMM with Indefinite Proximal Terms for Linearly Constrained Convex Composite Optimization
• A unified differential equation solver approach for separable convex optimization: splitting, acceleration and nonergodic rate
• A Scalable Frank-Wolfe based Augmented Lagrangian Method for Linearly Constrained Composite Convex Programming
• Understanding Limitation of Two Symmetrized Orders by Worst-case Complexity