Local linear convergence of the alternating direction method of multipliers on quadratic or linear programs

Research output: Contribution to journalArticlepeer-review

91 Scopus citations

Abstract

We introduce a novel matrix recurrence yielding a new spectral analysis of the local transient convergence behavior of the alternating direction method of multipliers (ADMM), for the particular case of a quadratic program or a linear program. We identify a particular combination of vector iterates whose convergence can be analyzed via a spectral analysis. The theory predicts that ADMM should go through up to four convergence regimes, such as constant step convergence or linear convergence, ending with the latter when close enough to the optimal solution if the optimal solution is unique and satisfies strict complementarity.

Original languageEnglish (US)
Pages (from-to)2183-2207
Number of pages25
JournalSIAM Journal on Optimization
Volume23
Issue number4
DOIs
StatePublished - Dec 1 2013

Keywords

  • ADMM
  • Linear programming
  • Quadratic programming

Fingerprint Dive into the research topics of 'Local linear convergence of the alternating direction method of multipliers on quadratic or linear programs'. Together they form a unique fingerprint.

Cite this