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

详细信息    查看全文

• 作者：Liang Chen ; Defeng Sun ; Kim-Chuan Toh
• 关键词：Alternating direction method of multipliers (ADMM) ; Convergence ; Counterexample ; Large step ; length
• 刊名：Computational Optimization and Applications
• 出版年：2017
• 出版时间：March 2017
• 年：2017
• 卷：66
• 期：2
• 页码：327-343
• 全文大小：
• 刊物类别：Mathematics and Statistics
• 刊物主题：Optimization; Operations Research, Management Science; Operation Research/Decision Theory; Statistics, general; Convex and Discrete Geometry;
• 出版者：Springer US
• ISSN：1573-2894
• 卷排序：66

文摘

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+\sqrt{5})/2\).