Partial error bound conditions and the linear convergence rate of the alternating direction method of multipliers

Yongchao Liu, Xiaoming YUAN, Shangzhi Zeng, Jin ZHANG*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)

Abstract

In the literature, error bound conditions have been widely used to study the linear convergence rates of various first-order algorithms. Most of the literature focuses on how to ensure these error bound conditions, usually posing numerous assumptions or special structures on the model under discussion. In this paper, we focus on the alternating direction method of multipliers (ADMM) and show that the known error bound conditions for studying the ADMM’s linear convergence rate can indeed be further weakened if the error bound is studied over the specific iterative sequence it generates. An error bound condition based on ADMM’s iterations is thus proposed, and linear convergence under this condition is proved. Furthermore, taking advantage of a specific feature of ADMM’s iterative scheme by which part of the perturbation is automatically zero, we propose the so-called partial error bound condition, which is weaker than known error bound conditions in the literature, and we derive the linear convergence rate of ADMM. We further show that this partial error bound condition is useful for interpreting the difference if the two primal variables are updated in different orders when implementing the ADMM. This has been empirically observed in the literature, yet no theory is known.

Original languageEnglish
Pages (from-to)2095-2123
Number of pages29
JournalSIAM Journal on Numerical Analysis
Volume56
Issue number4
DOIs
Publication statusPublished - 2018

Scopus Subject Areas

  • Numerical Analysis
  • Computational Mathematics
  • Applied Mathematics

User-Defined Keywords

  • Alternating direction method of multipliers
  • Calmness
  • Convex programming
  • Linear convergence rate
  • Partial error bound

Fingerprint

Dive into the research topics of 'Partial error bound conditions and the linear convergence rate of the alternating direction method of multipliers'. Together they form a unique fingerprint.

Cite this