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.

Published online:
DOI: https://doi.org/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
@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},
mrnumber = {3620372},
zbl = {1418.90193},
language = {en},
url = {https://smai-jcm.centre-mersenne.org/articles/10.5802/smai-jcm.6/}
}
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 | Article | Zbl 1229.90122

[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 | Article | MR 3102635

[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 | Article | MR 3439797 | Zbl 1332.90193

[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 | Article | MR 3268621 | Zbl 1311.90099

[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 | Article | MR 84194 | Zbl 0070.35401

[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 | Article | MR 1168183 | Zbl 0765.90073

[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 | Article | MR 2763706 | Zbl 1206.90117

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

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

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

[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 | Zbl 1320.65098

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

[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 | Article | Numdam | Zbl 0368.65053

[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 | Article

[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 | Article | MR 3348268 | Zbl 1317.90235

[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 | Article | MR 3424071 | Zbl 1327.90209

[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 | Article | MR 1892298 | Zbl 1009.90108

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

[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 | Article | MR 3231988 | Zbl 1327.90210

[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 | Article | MR 2968856 | Zbl 1273.90152

[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 | Article | MR 3335210

[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 | Article | MR 2914282 | Zbl 1245.90084

[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 | Article | MR 3347463 | Zbl 1320.90060

[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 | Article | MR 551319 | Zbl 0426.65050

[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 298899 | Zbl 0215.21103

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

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

[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 | Article | MR 71874 | Zbl 0067.35801

[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 | Article

[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 | Article | MR 3166972 | Zbl 1291.90176

[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 | Article | MR 2765489 | Zbl 1218.90115

[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 | Article | MR 3023726 | Zbl 1263.90061

[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 | Article | MR 2983026 | Zbl 1263.90062