Optimization Online


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

Tianyi Lin (tylin***at***se.cuhk.edu.hk)
Shiqian Ma (sqma***at***se.cuhk.edu.hk)
Shuzhong Zhang (zhangs***at***umn.edu)

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

Keywords: Alternating Direction Method of Multipliers, Global Linear Convergence, Convex Optimization

Category 1: Convex and Nonsmooth Optimization


Download: [PDF]

Entry Submitted: 08/19/2014
Entry Accepted: 08/19/2014
Entry Last Modified: 05/24/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society