×

On the convergence of the direct extension of ADMM for three-block separable convex minimization models with one strongly convex function. (English) Zbl 1372.90079

Summary: The alternating direction method of multipliers (ADMM) is a benchmark for solving a two-block linearly constrained convex minimization model whose objective function is the sum of two functions without coupled variables. Meanwhile, it is known that the convergence is not guaranteed if the ADMM is directly extended to a multiple-block convex minimization model whose objective function has more than two functions. Recently, some authors have actively studied the strong convexity condition on the objective function to sufficiently ensure the convergence of the direct extension of ADMM or the resulting convergence when the original scheme is appropriately twisted. We focus on the three-block case of such a model whose objective function is the sum of three functions, and discuss the convergence of the direct extension of ADMM. We show that when one function in the objective is strongly convex, the penalty parameter and the operators in the linear equality constraint are appropriately restricted, it is sufficient to guarantee the convergence of the direct extension of ADMM. We further estimate the worst-case convergence rate measured by the iteration complexity in both the ergodic and nonergodic senses, and derive the globally linear convergence in asymptotical sense under some additional conditions.

MSC:

90C25 Convex programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Boley, D.: Local linear convergence of ADMM on quadratic or linear programs. SIAM J. Optim. 23(4), 2183-2207 (2013) · Zbl 1288.65086 · doi:10.1137/120878951
[2] Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J.: Distributed optimization and statistical learning via the alternating direction method of multipliers. In: Jordan, M. (ed.) Foundations and Trends in Machine Learning, vol. 3,pp. 1-122 (2011) · Zbl 1229.90122
[3] Chamboulle, A., Pock, T.: A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vis. 40, 120-145 (2011) · Zbl 1255.68217 · doi:10.1007/s10851-010-0251-1
[4] Chandrasekaran, V., Parrilo, P.A., Willsky, A.S.: Latent variable graphical model selection via convex optimization. Ann. Stat. 40, 1935-1967 (2012) · Zbl 1257.62061 · doi:10.1214/11-AOS949
[5] 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. 155, 57-79 (2016) · Zbl 1332.90193 · doi:10.1007/s10107-014-0826-5
[6] Chen, C.H., Shen, Y., You, Y.F.: On the convergence analysis of the alternating direction method of multipliers with three blocks. Abstr. Appl. Anal. 2013 (2013), Article ID 183961 · Zbl 1302.90148
[7] Corman, E., Yuan, X.M.: A generalized proximal point algorithm and its convergence rate. SIAM J. Optim. 24(4), 1614-1638 (2014) · Zbl 1311.90099 · doi:10.1137/130940402
[8] Deng, W., Yin, W.T.: On the global and linear convergence of the generalized alternating direction method of multipliers. J. Sci. Comput. 66(3), 889-916 (2016) · Zbl 1379.65036 · doi:10.1007/s10915-015-0048-x
[9] Deng, W., Lai, M.J., Peng, Z.M., Yin, W.T.: Parallel multi-block ADMM with \[o(1/k)\] o(1/k) convergence. Manuscript (2014) · Zbl 1398.65121
[10] Eckstein, J., Yao, W.: Understanding the convergence of the alternating direction method of multipliers: theoretical and computational perspectives. Pac. J. Optim. 11, 619-644 (2015) · Zbl 1330.90074
[11] Glowinski, R.: Numerical Methods for Nonlinear Variational Problems. Springer, New York (1984) · Zbl 0536.65054 · doi:10.1007/978-3-662-12613-4
[12] Glowinski, R., Marrocco, A.: Sur l’approximation paréléments finis d’ordre un et larésolution parpénalisation-dualité d’une classe de problèmes de Dirichlet non linéaires. Revue Fr. Autom. Inf. Rech. Opér., Anal. Numér. 2, 41-76 (1975) · Zbl 0368.65053
[13] Glowinski, R.: On alternating direction methods of multipliers: a historical perspective. Model. Simul. Optim. Sci. Technol. Comput. Methods Appl. Sci. 34, 59-82 (2014) · Zbl 1320.65098
[14] Han, D.R., Yuan, X.M.: A note on the alternating direction method of multipliers. J. Optim. Theory Appl. 155, 227-238 (2013) · Zbl 1255.90093 · doi:10.1007/s10957-012-0003-z
[15] Han, D.R., Yuan, X.M.: Local linear convergence of the alternating direction method of multipliers for quadratic programs. SIAM J. Numer. Anal. 51, 3446-3457 (2013) · Zbl 1285.90033 · doi:10.1137/120886753
[16] Han, D.R., Yuan, X.M., Zhang, W.X.: An augmented-Lagrangian-based parallel splitting method for separable convex programming with applications to image processing. Math. Comput. 83, 2263-2291 (2014) · Zbl 1311.90100 · doi:10.1090/S0025-5718-2014-02829-9
[17] He, B.S., Tao, M., Yuan, X.M.: Alternating direction method with Gaussian back substitution for separable convex programming. SIAM J. Optim. 22, 313-340 (2012) · Zbl 1273.90152 · doi:10.1137/110822347
[18] 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. Math. Oper. Res. (under revision) · Zbl 1371.90103
[19] He, B.S., Tao, M., Yuan, X.M.: A splitting method for separable convex programming. IMA J. Numer. Anal. 35, 394-426 (2015) · Zbl 1310.65062 · doi:10.1093/imanum/drt060
[20] Hestenes, M.R.: Multiplier and gradient methods. J. Optim. Theory Appl. 4, 303-320 (1969) · Zbl 0174.20705 · doi:10.1007/BF00927673
[21] Hong, M.Y., Luo, Z.Q.: On the linear convergence of alternating direction method of multipliers. Math. Program. (to appear) · Zbl 1362.90313
[22] Li, M., Sun, D.F., Toh, K.C.: A convergent \[33\]-block semi-proximal ADMM for convex minimization problems with one strongly convex block. Asia Pac. J. Oper. Res. 32, 1550024 (2015). 19 pages · Zbl 1327.90214 · doi:10.1142/S0217595915500244
[23] Lin, T.Y., Ma, S.Q., Zhang, S.Z.: On the sublinear convergence rate of multi-block ADMM. J. Oper. Res. Soc. China 3, 251-274 (2015) · Zbl 1323.90052 · doi:10.1007/s40305-015-0092-0
[24] Lin, T.Y., Ma, S.Q., Zhang, S.Z.: On the global linear convergence of the ADMM with multi-block variables. SIAM J. Optim. 25, 1478-1497 (2015) · Zbl 1333.90095 · doi:10.1137/140971178
[25] Martinet, B.: Regularization d’inequations variationelles par approximations successives. Revue Francaise d’Informatique et de Recherche Opérationelle 4, 154-159 (1970) · Zbl 0215.21103
[26] Moreau, J.J.: Proximité et dualit ’e dans un espace Hilbertien. Bull. Soc. Math. France 93, 273-299 (1965) · Zbl 0136.12101
[27] McLachlan, G.J.: Discriminant Analysis and Statistical Pattern Recognition, vol. 544. Wiley, New York (2004) · Zbl 1108.62317
[28] Mohan, K., London, P., Fazel, M., Witten, D., Lee, S.: Node-based learning of multiple gaussian graphical models. J. Mach. Learn. Res. 15, 445-488 (2014) · Zbl 1318.62181
[29] Peng, Y.G., Ganesh, A., Wright, J., Xu, W.L., Ma, Y.: Robust alignment by sparse and low-rank decomposition for linearly correlated images. IEEE Trans. Pattern Anal. Mach. Intell. 34, 2233-2246 (2012) · Zbl 1274.60197 · doi:10.1109/TPAMI.2011.282
[30] Powell, MJD; Fletcher, R. (ed.), A method for nonlinear constraints in minimization problems, 283-298 (1969), New York
[31] Robinson, S.M.: Some continuity properties of polyhedral multifunctions. Math. Program. Stud. 14, 206-214 (1981) · Zbl 0449.90090 · doi:10.1007/BFb0120929
[32] Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970) · Zbl 0193.18401 · doi:10.1515/9781400873173
[33] Rockafellar, R.T.: Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14, 877-898 (1976) · Zbl 0358.90053 · doi:10.1137/0314056
[34] Tao, M., Yuan, X.M.: Recovering low-rank and sparse components of matrices from incomplete and noisy observations. SIAM J. Optim. 21, 57-81 (2011) · Zbl 1218.90115 · doi:10.1137/100781894
[35] Yang, W.H., Han, D.R.: Linear convergence of alternating direction method of multipliers for a class of convex optimization problems. SIAM J. Numer. Anal. 54(2), 625-640 (2016) · Zbl 1342.90138 · doi:10.1137/140974237
[36] Zheng, X.Y., Ng, K.F.: Metric subregularity of piecewise linear multifunctions and applications to piecewise linear multiobjective optimization. SIAM J. Optim. 24, 154-174 (2014) · Zbl 1306.90123 · doi:10.1137/120889502
[37] Zhou, X., Yang, C., Yu, W.: Moving object detection by detecting contiguous outliers in the Low-Rank representation. IEEE Trans. Pattern Anal. Mach. Intell. 35, 597-610 (2013) · doi:10.1109/TPAMI.2012.132
[38] Zhou, Z., Li, X., Wright, J., Candes, E.J., Ma, Y.: Stable principal component pursuit. In: Proceedings of International Symposium on Information Theory. Austin (2010) · Zbl 0449.90090
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.