See the original article notice from the Numdam source
MR ZblThe alternating direction method of multipliers (ADMM) is a benchmark for solving a linearly constrained convex minimization model with a two-block separable objective function; and it has been shown that its direct extension to a multiple-block case where the objective function is the sum of more than two functions is not necessarily convergent. For the multiple-block case, a natural idea is to artificially group the objective functions and the corresponding variables as two groups and then apply the original ADMM directly —- the block-wise ADMM is accordingly named because each of the resulting ADMM subproblems may involve more than one function in its objective. Such a subproblem of the block-wise ADMM may not be easy as it may require minimizing more than one function with coupled variables simultaneously. We discuss how to further decompose the block-wise ADMM’s subproblems and obtain easier subproblems so that the properties of each function in the objective can be individually and thus effectively used, while the convergence can still be ensured. The generalized ADMM and the strictly contractive Peaceman-Rachford splitting method, two schemes closely relevant to the ADMM, will also be extended to the block-wise versions to tackle the multiple-block convex programming cases. We present the convergence analysis, including both the global convergence and the worst-case convergence rate measured by the iteration complexity, for these three block-wise splitting schemes in a unified framework.
DOI: 10.5802/smai-jcm.6
Keywords: Convex programming, Operator splitting methods, Alternating direction method of multipliers, proximal point algorithm, Douglas-Rachford splitting method, Peaceman-Rachford splitting method, Convergence rate, Iteration complexity
He, Bingsheng 1 ; Yuan, Xiaoming 2
He, Bingsheng; Yuan, Xiaoming. Block-wise Alternating Direction Method of Multipliers for Multiple-block Convex Programming and Beyond. The SMAI Journal of computational mathematics, Volume 1 (2015), pp. 145-174. doi: 10.5802/smai-jcm.6
@article{SMAI-JCM_2015__1__145_0,
author = {He, Bingsheng and Yuan, Xiaoming},
title = {Block-wise {Alternating} {Direction} {Method} of {Multipliers} for {Multiple-block} {Convex} {Programming} and {Beyond}},
journal = {The SMAI Journal of computational mathematics},
pages = {145--174},
year = {2015},
publisher = {Soci\'et\'e de Math\'ematiques Appliqu\'ees et Industrielles},
volume = {1},
doi = {10.5802/smai-jcm.6},
mrnumber = {3620372},
zbl = {1418.90193},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.5802/smai-jcm.6/}
}
TY - JOUR AU - He, Bingsheng AU - Yuan, Xiaoming TI - Block-wise Alternating Direction Method of Multipliers for Multiple-block Convex Programming and Beyond JO - The SMAI Journal of computational mathematics PY - 2015 SP - 145 EP - 174 VL - 1 PB - Société de Mathématiques Appliquées et Industrielles UR - http://geodesic.mathdoc.fr/articles/10.5802/smai-jcm.6/ DO - 10.5802/smai-jcm.6 LA - en ID - SMAI-JCM_2015__1__145_0 ER -
%0 Journal Article %A He, Bingsheng %A Yuan, Xiaoming %T Block-wise Alternating Direction Method of Multipliers for Multiple-block Convex Programming and Beyond %J The SMAI Journal of computational mathematics %D 2015 %P 145-174 %V 1 %I Société de Mathématiques Appliquées et Industrielles %U http://geodesic.mathdoc.fr/articles/10.5802/smai-jcm.6/ %R 10.5802/smai-jcm.6 %G en %F SMAI-JCM_2015__1__145_0
Cited by Sources: