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.

The 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
Classification: 90C25, 90C06, 65K05
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
Bingsheng He 1; Xiaoming Yuan 2

1 Department of Mathematics, South University of Science and Technology of China, and Department of Mathematics, Nanjing University, China
2 Department of Mathematics, Hong Kong Baptist University, Hong Kong
@article{SMAI-JCM_2015__1__145_0,
author = {Bingsheng He and Xiaoming Yuan},
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},
publisher = {Soci\'et\'e de Math\'ematiques Appliqu\'ees et Industrielles},
volume = {1},
year = {2015},
doi = {10.5802/smai-jcm.6},
language = {en},
url = {https://smai-jcm.centre-mersenne.org/articles/10.5802/smai-jcm.6/}
}
TY  - JOUR
AU  - Bingsheng He
AU  - Xiaoming Yuan
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  - https://smai-jcm.centre-mersenne.org/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 Bingsheng He
%A Xiaoming Yuan
%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 https://smai-jcm.centre-mersenne.org/articles/10.5802/smai-jcm.6/
%R 10.5802/smai-jcm.6
%G en
%F SMAI-JCM_2015__1__145_0
Bingsheng He; Xiaoming Yuan. 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. https://smai-jcm.centre-mersenne.org/articles/10.5802/smai-jcm.6/

[1] S. Boyd; N. Parikh; E. Chu; B. Peleato; J. Eckstein Distributed optimization and statistical learning via the alternating direction method of multipliers, Foun. Trends Mach. Learn., Volume 3 (2011) no. 1, pp. 1-122 | DOI | Zbl

[2] X. J. Cai; G. Y. Gu; B. S. He; X. M. Yuan A proximal point algorithm revisit on the alternating direction method of multipliers, Sci. China Math., Volume 56 (2013) no. 10, pp. 2179-2186 | DOI | MR | Zbl

[3] C. H. Chen; B. S. He; Y. Y. Ye; X. M. Yuan The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent, Math. Program., Volume 155 (2016) no. 1-2, pp. 57-79 | DOI | MR

[4] E. Corman; X. M. Yuan A generalized proximal point algorithm and its convergence rate, SIAM J. Optim, Volume 24 (2014) no. 4, pp. 1614-1638 | DOI | MR

[5] J. Douglas; H. H. Rachford On the numerical solution of heat conduction problems in two and three space variables, Trans. Amer. Math. Soc., Volume 82 (1956) no. 2, pp. 421-439 | DOI | MR | Zbl

[6] J. Eckstein; D. P. Bertsekas On the Douglas–Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Program., Volume 55 (1992) no. 1-3, pp. 293-318 | DOI | MR | Zbl

[7] J. Eckstein; W. Yao Augmented Lagrangian and alternating direction methods for convex optimization: A tutorial and some illustrative computational results, RUTCOR Research Reports, Volume 32 (2012)

[8] E. Esser; X. Zhang; T. F. Chan A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science, SIAM J. Imaging Sci., Volume 3 (2010) no. 4, pp. 1015-1046 | DOI | MR | Zbl

[9] F. Facchinei; J. S. Pang Finite-Dimensional Variational Inequalities and Complementarity Problems, Volume I, Springer Science & Business Media, 2003 | MR | Zbl

[10] D. Gabay; M. Fortin; R. Glowinski Applications of the Method of Multipliers to Variational Inequalities, Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary-Value Problems (Studies in Mathematics and Its Applications), Volume 15, Elsevier, 1983, pp. 299 -331 http://www.sciencedirect.com/science/article/pii/S0168202408700341 | DOI

[11] R. Glowinski Numerical Methods for Nonlinear Variational Problems, Springer-Verlag Berlin Heidelberg, 1984 | Zbl

[12] R. Glowinski On alternating direction methods of multipliers: a historical perspective, Modeling, Simulation and Optimization for Science and Technology, Springer, 2014, pp. 59-82 | MR

[13] R. Glowinski; T. Kärkkäinen; K. Majava; Y. Kuznetsov; P. Neittanmaki; O. Pironneau On the convergence of operator-splitting methods, Numerical Methods for Scienfic computing, Variational Problems and Applications, CIMNE, 2003 | MR

[14] R. Glowinski; A. Marroco Sur l’approximation, par éléments finis d’ordre un, et la résolution, par pénalisation-dualité d’une classe de problèmes de Dirichlet non linéaires, Revue française d’automatique, informatique, recherche opérationnelle. Analyse numérique, Volume 9 (1975) no. 2, pp. 41-76 | Numdam | MR | Zbl

[15] E. G. Golʼshteĭn; N. V. Tretʼyakov Modified Lagrangians in convex programming and their generalizations, Point-to-Set Maps and Mathematical Programming, Springer, 1979, pp. 86-97 | Zbl

[16] W. W. Hager; C. Ngo; M. Yashtini; H. Zhang An alternating direction approximate Newton algorithm for ill-conditioned inverse problems with application to parallel MRI, Journal of the Operations Research Society of China, Volume 3 (2015) no. 2, pp. 139-162 | DOI | MR

[17] B. S. He; L. S. Hou; X. M. Yuan On full Jacobian decomposition of the augmented Lagrangian method for separable convex programming, SIAM J. Optim, Volume 25 (2015) no. 4, pp. 2274-2312 | DOI | MR

[18] B. S. He; L. Z. Liao; D. Han; H. Yang A new inexact alternating directions method for monotone variational inequalities, Math. Program., Volume 92 (2002) no. 1, pp. 103-118 | DOI | MR | Zbl

[19] B. S. He; H. Liu; J. Lu; X. M. Yuan; R. Glowinksi; S. Osher; W. Yin Application of the strictly contractive Peaceman-Rachford splitting method to multi-block convex programming, Operator Splitting Methods and Applications, to appear

[20] B. S. He; H. Liu; Z. R. Wang; X. M. Yuan A Strictly Contractive Peaceman–Rachford Splitting Method for Convex Programming, SIAM J. Optim, Volume 24 (2014) no. 3, pp. 1011-1040 | DOI | MR

[21] B. S. He; M. Tao; X. M. Yuan Convergence rate and iteration complexity on the alternating direction method of multipliers with a substitution procedure for separable convex programming

[22] B. S. He; M. Tao; X. M. Yuan Alternating direction method with Gaussian back substitution for separable convex programming, SIAM J. Optim, Volume 22 (2012) no. 2, pp. 313-340 | DOI | MR | Zbl

[23] B. S. He; M. Tao; X. M. Yuan A splitting method for separable convex programming, IMA J. Numer. Anal., Volume 35 (2015) no. 1, pp. 394-426 | DOI | MR

[24] B. S. He; X. M. Yuan On the O(1/n) Convergence Rate of the Douglas-Rachford Alternating Direction Method, SIAM J. Numer. Anal., Volume 50 (2012) no. 2, pp. 700-709 | DOI | MR | Zbl

[25] B. S. He; X. M. Yuan On non-ergodic convergence rate of Douglas–Rachford alternating direction method of multipliers, Numerische Mathematik, Volume 130 (2015) no. 3, pp. 567-577 | DOI | MR

[26] M. Hong; Z. Q. Luo On the linear convergence of the alternating direction method of multipliers, Math. Program. (to appear)

[27] P. L. Lions; B. Mercier Splitting algorithms for the sum of two nonlinear operators, SIAM J. Numer. Anal., Volume 16 (1979) no. 6, pp. 964-979 | DOI | MR | Zbl

[28] B. Martinet Brève communication. Régularisation d’inéquations variationnelles par approximations successives, Revue française d’informatique et de recherche opérationnelle, série rouge, Volume 4 (1970) no. 3, pp. 154-158 | Numdam | MR | Zbl

[29] Yu. Nesterov Gradient methods for minimizing composite functions, Math. Program., Volume 140 (2013) no. 1, pp. 125-161 | DOI | MR | Zbl

[30] F. Ng; X. M. Yuan Inexact alternating direction methods for image recovery, SIAM J. Sci. Comput., Volume 33 (2011) no. 4, pp. 1643-1668 | DOI | MR | Zbl

[31] D. H. Peaceman; H. H. Rachford The numerical solution of parabolic and elliptic differential equations, SIAM J. Appl. Math., Volume 3 (1955) no. 1, pp. 28-41 | DOI | MR | Zbl

[32] Y.G. Peng; A. Ganesh; J. Wright; W. L. Xu; Y. Ma RASL: Robust alignment by sparse and low-rank decomposition for linearly correlated images, IEEE Trans. Pattern Anal. Mach. Intel., Volume 34 (2012) no. 11, pp. 2233-2246 | DOI

[33] R. Shefi; M. Teboulle Rate of convergence analysis of decomposition methods based on the proximal method of multipliers for convex minimization, SIAM J. Optim, Volume 24 (2014) no. 1, pp. 269-297 | DOI | MR | Zbl

[34] M. Tao; X. M. Yuan Recovering low-rank and sparse components of matrices from incomplete and noisy observations, SIAM J. Optim, Volume 21 (2011) no. 1, pp. 57-81 | DOI | MR | Zbl

[35] X. F. Wang; X. M. Yuan The linearized alternating direction method of multipliers for Dantzig selector, SIAM J. Sci. Comput., Volume 34 (2012) no. 5, p. A2792-A2811 | DOI | MR | Zbl

[36] J. F. Yang; X. M. Yuan Linearized augmented Lagrangian and alternating direction methods for nuclear norm minimization, Math. Comput., Volume 82 (2013) no. 281, pp. 301-329 | DOI | MR | Zbl

Cited by Sources: