A note on the convergence of ADMM for linearly constrained convex optimization problems

L. Chen, Defeng Sun, K.-C. Toh

Research output: Journal article publicationJournal articleAcademic researchpeer-review

18 Citations (Scopus)

Abstract

© 2016, Springer Science+Business Media New York.This note serves two purposes. Firstly, we construct a counterexample to show that the statement on the convergence of the alternating direction method of multipliers (ADMM) for solving linearly constrained convex optimization problems in a highly influential paper by Boyd et al. (Found Trends Mach Learn 3(1):1-122, 2011) can be false if no prior condition on the existence of solutions to all the subproblems involved is assumed to hold. Secondly, we present fairly mild conditions to guarantee the existence of solutions to all the subproblems of the ADMM and provide a rigorous convergence analysis on the ADMM with a computationally more attractive large step-length that can even exceed the practically much preferred golden ratio of (1+5)/2.
Original languageEnglish
Pages (from-to)327-343
Number of pages17
JournalComputational Optimization and Applications
Volume66
Issue number2
DOIs
Publication statusPublished - 1 Mar 2017
Externally publishedYes

Keywords

  • Alternating direction method of multipliers (ADMM)
  • Convergence
  • Counterexample
  • Large step-length

ASJC Scopus subject areas

  • Control and Optimization
  • Computational Mathematics
  • Applied Mathematics

Cite this