On the Sublinear Convergence Rate of Multi-Block ADMM

Abstract

The alternating direction method of multipliers (ADMM) is widely used in solving structured convex optimization problems. Despite of its success in practice, the convergence properties of the standard ADMM for minimizing the sum of $N$ $(N\ge 3)$ convex functions with $N$ block variables linked by linear constraints, have remained unclear for a very long time. In this paper, we present convergence and convergence rate results for the standard ADMM applied to solve $N$-block $(N\ge 3)$ convex minimization problem, under the condition that one of these functions is convex (not necessarily strongly convex) and the other $N-1$ functions are strongly convex. Specifically, in that case the ADMM is proven to converge with rate $O(1/t)$ in a certain ergodic sense, and $o(1/t)$ in non-ergodic sense, where $t$ denotes the number of iterations. As a by-product, we also provide a simple proof for the $O(1/t)$ convergence rate of two-block ADMM in terms of both objective error and constraint violation, without assuming any condition on the penalty parameter and strong convexity on the functions.

References in corpus (8)

• 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
• A Block Successive Upper Bound Minimization Method of Multipliers for Linearly Constrained Convex Optimization
• Parallel Multi-Block ADMM with o(1/k) Convergence
• A Three-Operator Splitting Scheme and its Optimization Applications
• Faster convergence rates of relaxed Peaceman-Rachford and ADMM under regularity assumptions
• Iteration Complexity Analysis of Multi-Block ADMM for a Family of Convex Minimization without Strong Convexity
• Global Convergence of Unmodified 3-Block ADMM for a Class of Convex Minimization Problems

Cited by in corpus (7)

• A Three-Operator Splitting Scheme and its Optimization Applications
• Worst-case Complexity of Cyclic Coordinate Descent: $O(n^2)$ Gap with Randomized Version
• On the Efficiency of Random Permutation for ADMM and Coordinate Descent
• Inexact alternating direction multiplier methods for separable convex optimization
• A Majorized ADMM with Indefinite Proximal Terms for Linearly Constrained Convex Composite Optimization
• The Application of Multi-block ADMM on Isotonic Regression Problems
• Understanding Limitation of Two Symmetrized Orders by Worst-case Complexity