Linear Rate Convergence of the Alternating Direction Method of Multipliers for Convex Composite Programming

Indexed by:期刊论文

Journal:MATHEMATICS OF OPERATIONS RESEARCH

Included Journals:SCIE

Volume:43

Issue:2

Page Number:622-637

ISSN No.:0364-765X

Key Words:ADMM; calmness; Q-linear convergence; multiblock; composite conic programming

Abstract: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 + 5(1/2))/2). This semi-proximal ADMM, which covers the classic one, has the advantage to resolve the potentially nonsolvability issue of the sub-problems in the classic ADMM and possesses the abilities of handling the multi-block cases efficiently. We demonstrate the usefulness of the obtained results when applied to two- and multi-block convex quadratic (semidefinite) programming.

Date of Publication:2018-05-01