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

• 成果类型: Article
• 署名作者: Han, Deren; Sun, Defeng; Zhang, Liwei
• 署名单位: Nanjing Normal University; Hong Kong Polytechnic University; Dalian University of Technology
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2017.0875
• 发表日期: 2018
• 页码: 622-637
• 关键词: proximal point algorithm; optimization problems; monotone-operators; minimization; Duality; admm

摘要

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.