×

A faster generalized ADMM-based algorithm using a sequential updating scheme with relaxed step sizes for multiple-block linearly constrained separable convex programming. (English) Zbl 1465.90103

Summary: The multi-block linearly constrained separable convex optimization is frequently applied in numerous applications, including image/signal processing, statistical learning, and data mining, where the objective function is the sum of multiple individual convex functions, and the key constraints are linear. A classical approach to solving such optimization problem could be the alternating direction method of multipliers (ADMM). It decomposes the subproblem into a series of small-scale ones such that its per-iteration cost may be meager. ADMM, however, is designed initially for the two-block model, and its convergence cannot be guaranteed for a general multi-block model without additional assumptions. Y.-H. Dai et al. [Math. Comput. 86, No. 303, 315–343 (2017; Zbl 1348.90520)] proposed the algorithm SUSLM (for Sequential Updating Scheme of the Lagrange Multiplier) for separable convex programming problems. The Lagrange multipliers are updated several times at each iteration, and a correction step is imposed at the end of each iteration. In order to derive its convergence property, a correction step is imposed at the end of each iteration. In this paper, we improve the SUSLM algorithm by introducing two controlled parameters in the updating expressions for decision variables and Lagrange multipliers. The condition of step sizes is then relaxed. We show experimentally that our SUSLM algorithm converges faster than SUSLM. Moreover, result comparisons on robust principal component analysis (RPCA) show better performances than other ADMM-based algorithms.

MSC:

90C30 Nonlinear programming
65K05 Numerical mathematical programming methods
94A08 Image processing (compression, reconstruction, etc.) in information and communication theory

Citations:

Zbl 1348.90520

Software:

LMaFit; spcov
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Yang, J. F.; Zhang, Y., Alternating direction algorithms for \(\ell_1\)-problems in compressive sensing, SIAM J. Sci. Comput., 33, 1, 250-278 (2011) · Zbl 1256.65060
[2] Liu, Z. S.; Li, J. C.; Li, G.; Bai, J. C.; Liu, X. N., A new model for sparse and low-rank matrix decomposition, J. Appl. Anal. Comput., 7, 2, 600-616 (2017) · Zbl 1488.65103
[3] Bien, J.; Tibshirani, R. J., Sparse estimation of a covariance matrix, Biometrika, 98, 4, 807-820 (2011) · Zbl 1228.62063
[4] Hestenes, M. R., Multiplier and gradient methods, J. Optim. Theory Appl., 4, 5, 303-320 (1969) · Zbl 0174.20705
[5] Glowinski, R.; Marrocco, 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, RAIRO, R-2, 41-76 (1975), (in French) · Zbl 0368.65053
[6] Gabay, D.; Mercier, B., A dual algorithm for the solution of nonlinear variational problems via finite element approximations, Comput. Math. Appl., 2, 1, 17-40 (1976) · Zbl 0352.65034
[7] He, B. S.; Liao, L. Z.; Han, D. R.; Yang, H., A new inexact alternating directions method for monotone variational inequalities, Math. Program., 92, 1, 103-118 (2002) · Zbl 1009.90108
[8] Tao, M.; Yuan, X. M., Recovering low-rank and sparse components of matrices from incomplete and noisy observations, SIAM J. Optim., 21, 1, 57-81 (2011) · Zbl 1218.90115
[9] Shen, Y.; Wen, Z. W.; Zhang, Y., Augmented Lagrangian alternating direction method for matrix separation based on low-rank factorization, Optim. Methods Softw., 29, 2, 239-263 (2014) · Zbl 1285.90068
[10] Han, D. R.; Yuan, X. M., A note on the alternating direction method of multipliers, J. Optim. Theory Appl., 155, 1, 227-238 (2012) · Zbl 1255.90093
[11] He, B. S.; Yuan, X. M., On the o(1/n) convergence rate of the douglas-rachford alternating direction method, SIAM J. Numer. Anal., 50, 2, 700-709 (2012) · Zbl 1245.90084
[12] Hong, M. Y.; Luo, Z. Q., On the linear convergence of the alternating direction method of multipliers, Math. Program., 162, 1-2, 165-199 (2017) · Zbl 1362.90313
[13] 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., Special Issue (2013) · Zbl 1302.90148
[14] 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, 1, 57-79 (2014) · Zbl 1332.90193
[15] 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., 25, 4, 2274-2312 (2015) · Zbl 1327.90209
[16] He, B. S.; Tao, M.; Yuan, X. M., A splitting method for separable convex programming, IMA J. Numer. Anal., 35, 1, 394-426 (2015) · Zbl 1310.65062
[17] Hou, L. S.; He, H. J.; Yang, J. F., A partially parallel splitting method for multiple-block separable convex programming with applications to robust pca, Comput. Optim. Appl., 63, 1, 273-303 (2016) · Zbl 1343.90061
[18] He, B. S.; Yuan, X. M., Block-wise alternating direction method of multipliers for multiple-block convex programming and beyond, SMAI J. Comput. Math., 1, 145-174 (2015) · Zbl 1418.90193
[19] He, B. S.; Xu, M. H.; Yuan, X. M., Block-wise ADMM with a relaxation factor for multiple-block convex programming, J. Oper. Res. Soc. China, 6, 485-505 (2018) · Zbl 1424.90204
[20] Shen, Y.; Zhang, X. Y.; Zhang, X. Y., A partial PPA block-wise ADMM for multi-block linearly constrained separable convex optimization, Optimization (2020)
[21] He, B. S.; Liu, H.; Wang, Z. R.; Yuan, X. M., A strictly contractive peaceman-rachford splitting method for convex programming, SIAM J. Optim., 24, 3, 1011-1040 (2014) · Zbl 1327.90210
[22] He, B. S.; Liu, H.; Lu, J. W.; Yuan, X. M., Application of the strictly contractive Peaceman-Rachford splitting method to multi-block separable convex programming, (Splitting Methods in Communication, Imaging, Science, and Engineering. Splitting Methods in Communication, Imaging, Science, and Engineering, Scientific Computation (2016), Springer: Springer Cham), 195-235 · Zbl 1372.65172
[23] Bai, J. C.; Li, J. C.; Xu, F. M.; Zhang, H. C., Generalized symmetric ADMM for separable convex optimization, Comput. Optim. Appl., 70, 129-170 (2018) · Zbl 1461.65126
[24] J.C. Bai, H.C. Zhang, A one-parameter family of middle proximal ADMM for constrained separable convex optimization, preprint, http://www.optimization-online.org/DB_HTML/2017/11/6319.html.
[25] He, B. S.; Tao, M.; Xu, M. H.; Yuan, X. M., An alternating direction-based contraction method for linearly constrained separable convex programming problems, Optimization, 62, 4, 573-596 (2013) · Zbl 1273.90122
[26] He, B. S.; Tao, M.; Yuan, X. M., Alternating direction method with Gaussian back substitution for separable convex programming, SIAM J. Optim., 22, 2, 313-340 (2012) · Zbl 1273.90152
[27] Dai, Y. H.; Han, D. R.; Zhang, W. X., A sequential updating scheme of the Lagrange multiplier for separable convex programming, Math. Comp., 86, 1, 315-343 (2017) · Zbl 1348.90520
[28] He, B. S., Parallel splitting augmented Lagrangian methods for monotone structured variational inequalities, Comput. Optim. Appl., 42, 2, 195-212 (2009) · Zbl 1183.65080
[29] Han, D. R.; Yuan, X. M.; Zhang, W. X., An augmented Lagrangian based parallel splitting method for separable convex minimization with applications to image processing, Math. Comp., 83, 289, 2263-2291 (2014) · Zbl 1311.90100
[30] Candès, E. J.; Li, X. D.; Ma, Y.; Wright, J., Robust principal component analysis?, J. ACM, 58, 3, Article 11 pp. (2009) · Zbl 1327.62369
[31] J. Wright, A. Ganesh, S. Rao, Y. Ma, Robust principal component analysis: Exact recovery of corrupted low-rank matrices by convex optimization, in: Proceedings of Neural Information Processing Systems (NIPS), December 2009.
[32] Han, D. R.; Kong, W. W.; Zhang, W. X., A partial splitting augmented Lagrangian method for low patch-rank image decomposition, J. Math. Imaging Vision, 51, 1, 145-160 (2015) · Zbl 1332.68270
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.