TY - JOUR

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

AU - Cai, Xingju

AU - Han, Deren

AU - YUAN, Xiaoming

N1 - Funding Information:
Xingju Cai is supported by the NSFC Grant 11401315 and the NSF from Jiangsu province BK20140914. Deren Han is supported by a project funded by PAPD of Jiangsu Higher Education Institutions and the NSFC Grants 11371197 and 11431002. Xiaoming Yuan was supported by the NSFC/RGC Joint Research Scheme: N_PolyU504/14.

PY - 2017/1/1

Y1 - 2017/1/1

N2 - 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.

AB - 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.

KW - Alternating direction method of multipliers

KW - Convergence analysis

KW - Convex programming

KW - Separable structure

UR - http://www.scopus.com/inward/record.url?scp=84979999818&partnerID=8YFLogxK

U2 - 10.1007/s10589-016-9860-y

DO - 10.1007/s10589-016-9860-y

M3 - Article

AN - SCOPUS:84979999818

SN - 0926-6003

VL - 66

SP - 39

EP - 73

JO - Computational Optimization and Applications

JF - Computational Optimization and Applications

IS - 1

ER -