On the convergence of the direct extension of ADMM for three-block separable convex minimization models with one strongly convex function

详细信息    查看全文

• 作者：Xingju Cai ; Deren Han ; Xiaoming Yuan
• 关键词：Alternating direction method of multipliers ; Convergence analysis ; Convex programming ; Separable structure
• 刊名：Computational Optimization and Applications
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：66
• 期：1
• 页码：39-73
• 全文大小：
• 刊物类别：Mathematics and Statistics
• 刊物主题：Optimization; Operations Research, Management Science; Operation Research/Decision Theory; Statistics, general; Convex and Discrete Geometry;
• 出版者：Springer US
• ISSN：1573-2894
• 卷排序：66

文摘

The alternating direction method of multipliers (ADMM) is a benchmark for solving a two-block linearly constrained convex minimization model whose objective function is the sum of two functions without coupled variables. Meanwhile, it is known that the convergence is not guaranteed if the ADMM is directly extended to a multiple-block convex minimization model whose objective function has more than two functions. Recently, some authors have actively studied the strong convexity condition on the objective function to sufficiently ensure the convergence of the direct extension of ADMM or the resulting convergence when the original scheme is appropriately twisted. We focus on the three-block case of such a model whose objective function is the sum of three functions, and discuss the convergence of the direct extension of ADMM. We show that when one function in the objective is strongly convex, the penalty parameter and the operators in the linear equality constraint are appropriately restricted, it is sufficient to guarantee the convergence of the direct extension of ADMM. We further estimate the worst-case convergence rate measured by the iteration complexity in both the ergodic and nonergodic senses, and derive the globally linear convergence in asymptotical sense under some additional conditions.