TY - JOUR

T1 - Convergence analysis of the direct extension of ADMM for multiple-block separable convex minimization

AU - Tao, Min

AU - YUAN, Xiaoming

N1 - Funding Information:
X. Yuan: This author was supported by the General Research Fund from Hong Kong Research Grants Council: 12313516.
Funding Information:
M. Tao: This author was supported by the Natural Science Foundation of China: NSFC-11301280 and the sponsorship of Jiangsu overseas research and training program for university prominent young and middle-aged teachers and presidents.

PY - 2018/6/1

Y1 - 2018/6/1

N2 - Recently, the alternating direction method of multipliers (ADMM) has found many efficient applications in various areas; and it has been shown that the convergence is not guaranteed when it is directly extended to the multiple-block case of separable convex minimization problems where there are m ≥ 3 functions without coupled variables in the objective. This fact has given great impetus to investigate various conditions on both the model and the algorithm’s parameter that can ensure the convergence of the direct extension of ADMM (abbreviated as “e-ADMM”). Despite some results under very strong conditions (e.g., at least (m − 1) functions should be strongly convex) that are applicable to the generic case with a general m, some others concentrate on the special case of m = 3 under the relatively milder condition that only one function is assumed to be strongly convex. We focus on extending the convergence analysis from the case of m = 3 to the more general case of m ≥ 3. That is, we show the convergence of e-ADMM for the case of m ≥ 3 with the assumption of only (m − 2) functions being strongly convex; and establish its convergence rates in different scenarios such as the worst-case convergence rates measured by iteration complexity and the globally linear convergence rate under stronger assumptions. Thus the convergence of e-ADMM for the general case of m ≥ 4 is proved; this result seems to be still unknown even though it is intuitive given the known result of the case of m = 3. Even for the special case of m = 3, our convergence results turn out to be more general than the existing results that are derived specifically for the case of m = 3.

AB - Recently, the alternating direction method of multipliers (ADMM) has found many efficient applications in various areas; and it has been shown that the convergence is not guaranteed when it is directly extended to the multiple-block case of separable convex minimization problems where there are m ≥ 3 functions without coupled variables in the objective. This fact has given great impetus to investigate various conditions on both the model and the algorithm’s parameter that can ensure the convergence of the direct extension of ADMM (abbreviated as “e-ADMM”). Despite some results under very strong conditions (e.g., at least (m − 1) functions should be strongly convex) that are applicable to the generic case with a general m, some others concentrate on the special case of m = 3 under the relatively milder condition that only one function is assumed to be strongly convex. We focus on extending the convergence analysis from the case of m = 3 to the more general case of m ≥ 3. That is, we show the convergence of e-ADMM for the case of m ≥ 3 with the assumption of only (m − 2) functions being strongly convex; and establish its convergence rates in different scenarios such as the worst-case convergence rates measured by iteration complexity and the globally linear convergence rate under stronger assumptions. Thus the convergence of e-ADMM for the general case of m ≥ 4 is proved; this result seems to be still unknown even though it is intuitive given the known result of the case of m = 3. Even for the special case of m = 3, our convergence results turn out to be more general than the existing results that are derived specifically for the case of m = 3.

KW - Alternating direction method of multipliers

KW - Convergence analysis

KW - Convex programming

KW - Multiple-block separable models

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

U2 - 10.1007/s10444-017-9560-x

DO - 10.1007/s10444-017-9560-x

M3 - Journal article

AN - SCOPUS:85031432456

SN - 1019-7168

VL - 44

SP - 773

EP - 813

JO - Advances in Computational Mathematics

JF - Advances in Computational Mathematics

IS - 3

ER -