Linear rate convergence of the alternating direction method of multipliers for convex composite programming

D. Han, Defeng Sun, L. Zhang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

37 Citations (Scopus)

Abstract

© 2017 INFORMS. In this paper, we aim to prove the linear rate convergence of the alternating direction method of multipliers (ADMM) for solving linearly constrained convex composite optimization problems. Under a mild calmness condition, which holds automatically for convex composite piecewise linear-quadratic programming, we establish the global Q-linear rate of convergence for a general semi-proximal ADMM with the dual step-length being taken in (0,(1+51/2)/2). This semi-proximal ADMM, which covers the classic one, has the advantage to resolve the potentially nonsolvability issue of the subproblems in the classic ADMM and possesses the abilities of handling the multi-block cases e ciently. We demonstrate the usefulness of the obtained results when applied to two- and multi-block convex quadratic (semidefinite) programming.
Original languageEnglish
Pages (from-to)622-637
Number of pages16
JournalMathematics of Operations Research
Volume43
Issue number2
DOIs
Publication statusPublished - 1 May 2018

Keywords

  • ADMM
  • Calmness
  • Composite conic programming
  • Multiblock
  • Q-linear convergence

ASJC Scopus subject areas

  • Mathematics(all)
  • Computer Science Applications
  • Management Science and Operations Research

Cite this