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.
@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 = {Journal of computational mathematics},
volume = {1},
year = {2015},
pages = {145-174},
doi = {10.5802/smai-jcm.6},
language = {en},
url = {http://dml.mathdoc.fr/item/SMAI-JCM_2015__1__145_0}
}
He, Bingsheng; Yuan, Xiaoming. Block-wise Alternating Direction Method of Multipliers for Multiple-block Convex Programming and Beyond. Journal of computational mathematics, Tome 1 (2015) pp. 145-174. doi : 10.5802/smai-jcm.6. http://gdmltest.u-ga.fr/item/SMAI-JCM_2015__1__145_0/
[1] Distributed optimization and statistical learning via the alternating direction method of multipliers, Foun. Trends Mach. Learn., Tome 3 (2011) no. 1, pp. 1-122 | Article | Zbl 1229.90122
[2] A proximal point algorithm revisit on the alternating direction method of multipliers, Sci. China Math., Tome 56 (2013) no. 10, pp. 2179-2186 | Article | MR 3102635 | Zbl 1292.65062
[3] The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent, Math. Program., Tome 155 (2016) no. 1-2, pp. 57-79 | Article | MR 3439797
[4] A generalized proximal point algorithm and its convergence rate, SIAM J. Optim, Tome 24 (2014) no. 4, pp. 1614-1638 | Article | MR 3268621
[5] On the numerical solution of heat conduction problems in two and three space variables, Trans. Amer. Math. Soc., Tome 82 (1956) no. 2, pp. 421-439 | Article | MR 84194 | Zbl 0070.35401
[6] On the Douglas–Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Program., Tome 55 (1992) no. 1-3, pp. 293-318 | Article | MR 1168183 | Zbl 0765.90073
[7] Augmented Lagrangian and alternating direction methods for convex optimization: A tutorial and some illustrative computational results, RUTCOR Research Reports, Tome 32 (2012)
[8] A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science, SIAM J. Imaging Sci., Tome 3 (2010) no. 4, pp. 1015-1046 | Article | MR 2763706 | Zbl 1206.90117
[9] Finite-Dimensional Variational Inequalities and Complementarity Problems, Volume I, Springer Science & Business Media (2003) | MR 1955648 | Zbl 1062.90001
[10] Applications of the Method of Multipliers to Variational Inequalities, Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary-Value Problems, Elsevier (Studies in Mathematics and Its Applications) Tome 15 (1983), pp. 299 -331 http://www.sciencedirect.com/science/article/pii/S0168202408700341 | Article
[11] Numerical Methods for Nonlinear Variational Problems, Springer-Verlag Berlin Heidelberg (1984) | Zbl 1139.65050
[12] On alternating direction methods of multipliers: a historical perspective, Modeling, Simulation and Optimization for Science and Technology, Springer (2014), pp. 59-82 | MR 3330832
[13] On the convergence of operator-splitting methods, Numerical Methods for Scienfic computing, Variational Problems and Applications, CIMNE (2003) | MR 2427782
[14] 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, Tome 9 (1975) no. 2, pp. 41-76 | Numdam | MR 388811 | Zbl 0368.65053
[15] Modified Lagrangians in convex programming and their generalizations, Point-to-Set Maps and Mathematical Programming, Springer (1979), pp. 86-97 | Zbl 0427.90072
[16] An alternating direction approximate Newton algorithm for ill-conditioned inverse problems with application to parallel MRI, Journal of the Operations Research Society of China, Tome 3 (2015) no. 2, pp. 139-162 | Article | MR 3348268
[17] On full Jacobian decomposition of the augmented Lagrangian method for separable convex programming, SIAM J. Optim, Tome 25 (2015) no. 4, pp. 2274-2312 | Article | MR 3424071
[18] A new inexact alternating directions method for monotone variational inequalities, Math. Program., Tome 92 (2002) no. 1, pp. 103-118 | Article | MR 1892298 | Zbl 1009.90108
[19] Application of the strictly contractive Peaceman-Rachford splitting method to multi-block convex programming, Operator Splitting Methods and Applications (to appear)
[20] A Strictly Contractive Peaceman–Rachford Splitting Method for Convex Programming, SIAM J. Optim, Tome 24 (2014) no. 3, pp. 1011-1040 | Article | MR 3231988
[21] Convergence rate and iteration complexity on the alternating direction method of multipliers with a substitution procedure for separable convex programming
[22] Alternating direction method with Gaussian back substitution for separable convex programming, SIAM J. Optim, Tome 22 (2012) no. 2, pp. 313-340 | Article | MR 2968856 | Zbl 1273.90152
[23] A splitting method for separable convex programming, IMA J. Numer. Anal., Tome 35 (2015) no. 1, pp. 394-426 | Article | MR 3335210
[24] On the O(1/n) Convergence Rate of the Douglas-Rachford Alternating Direction Method, SIAM J. Numer. Anal., Tome 50 (2012) no. 2, pp. 700-709 | Article | MR 2914282 | Zbl 1245.90084
[25] On non-ergodic convergence rate of Douglas–Rachford alternating direction method of multipliers, Numerische Mathematik, Tome 130 (2015) no. 3, pp. 567-577 | Article | MR 3347463
[26] On the linear convergence of the alternating direction method of multipliers, Math. Program. (to appear)
[27] Splitting algorithms for the sum of two nonlinear operators, SIAM J. Numer. Anal., Tome 16 (1979) no. 6, pp. 964-979 | Article | MR 551319 | Zbl 0426.65050
[28] 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, Tome 4 (1970) no. 3, pp. 154-158 | Numdam | MR 298899 | Zbl 0215.21103
[29] Gradient methods for minimizing composite functions, Math. Program., Tome 140 (2013) no. 1, pp. 125-161 | Article | MR 3071865 | Zbl 1287.90067
[30] Inexact alternating direction methods for image recovery, SIAM J. Sci. Comput., Tome 33 (2011) no. 4, pp. 1643-1668 | Article | MR 2821262 | Zbl 1234.94013
[31] The numerical solution of parabolic and elliptic differential equations, SIAM J. Appl. Math., Tome 3 (1955) no. 1, pp. 28-41 | Article | MR 71874 | Zbl 0067.35801
[32] RASL: Robust alignment by sparse and low-rank decomposition for linearly correlated images, IEEE Trans. Pattern Anal. Mach. Intel., Tome 34 (2012) no. 11, pp. 2233-2246 | Article
[33] Rate of convergence analysis of decomposition methods based on the proximal method of multipliers for convex minimization, SIAM J. Optim, Tome 24 (2014) no. 1, pp. 269-297 | Article | MR 3166972 | Zbl 1291.90176
[34] Recovering low-rank and sparse components of matrices from incomplete and noisy observations, SIAM J. Optim, Tome 21 (2011) no. 1, pp. 57-81 | Article | MR 2765489 | Zbl 1218.90115
[35] The linearized alternating direction method of multipliers for Dantzig selector, SIAM J. Sci. Comput., Tome 34 (2012) no. 5, p. A2792-A2811 | Article | MR 3023726 | Zbl 1263.90061
[36] Linearized augmented Lagrangian and alternating direction methods for nuclear norm minimization, Math. Comput., Tome 82 (2013) no. 281, pp. 301-329 | Article | MR 2983026 | Zbl 1263.90062