Block-wise Alternating Direction Method of Multipliers for Multiple-block Convex Programming and Beyond

He, Bingsheng; Yuan, Xiaoming

The SMAI Journal of computational mathematics, Tome 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.

Classification : 90C25, 90C06, 65K05
Mots clés : 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

[1] Boyd, S.; Parikh, N.; Chu, E.; Peleato, B.; Eckstein, J. 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] Cai, X. J.; Gu, G. Y.; He, B. S.; Yuan, X. M. 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

[3] Chen, C. H.; He, B. S.; Ye, Y. Y.; Yuan, X. M. 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 | Zbl

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

[5] Douglas, J.; Rachford, H. H. 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] Eckstein, J.; Bertsekas, D. P. 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] Eckstein, J.; Yao, W. Augmented Lagrangian and alternating direction methods for convex optimization: A tutorial and some illustrative computational results, RUTCOR Research Reports, Volume 32 (2012)

[8] Esser, E.; Zhang, X.; Chan, T. F. 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] Facchinei, F.; Pang, J. S. Finite-Dimensional Variational Inequalities and Complementarity Problems, Volume I, Springer Science & Business Media, 2003

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

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

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

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

[14] Glowinski, R.; Marroco, A. 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 | DOI | Numdam | Zbl

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

[16] Hager, W. W.; Ngo, C.; Yashtini, M.; Zhang, H. 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 | Zbl

[17] He, B. S.; Hou, L. S.; Yuan, X. M. 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 | Zbl

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

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

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

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

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

[24] He, B. S.; Yuan, X. M. 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] He, B. S.; Yuan, X. M. 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 | Zbl

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

[27] Lions, P. L.; Mercier, B. 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] Martinet, B. 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] Nesterov, Yu. Gradient methods for minimizing composite functions, Math. Program., Volume 140 (2013) no. 1, pp. 125-161 | DOI | MR | Zbl

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

[31] Peaceman, D. H.; Rachford, H. H. 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] Peng, Y.G.; Ganesh, A.; Wright, J.; Xu, W. L.; Ma, Y. 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] Shefi, R.; Teboulle, M. 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] Tao, M.; Yuan, X. M. 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] Wang, X. F.; Yuan, X. M. 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] Yang, J. F.; Yuan, X. M. Linearized augmented Lagrangian and alternating direction methods for nuclear norm minimization, Math. Comput., Volume 82 (2013) no. 281, pp. 301-329 | DOI | MR | Zbl