Modified proximal symmetric ADMMs for multi-block separable convex optimization with linear constraints. (English) Zbl 1492.90130
Summary: We consider the linearly constrained separable convex optimization problem whose objective function is separable with respect to \(m\) blocks of variables. A bunch of methods have been proposed and extensively studied in the past decade. Specifically, a modified strictly contractive Peaceman-Rachford splitting method (SC-PRCM) [S.-H. Jiang and M. Li, J. Ind. Manag. Optim. 14, No. 1, 397–412 (2018; Zbl 1412.90109)] has been well studied in the literature for the special case of \(m = 3\). Based on the modified SC-PRCM, we present modified proximal symmetric ADMMs (MPSADMMs) to solve the multi-block problem. In MPSADMMs, all subproblems but the first one are attached with a simple proximal term, and the multipliers are updated twice. At the end of each iteration, the output is corrected via a simple correction step. Without stringent assumptions, we establish the global convergence result and the \(O(1/t)\) convergence rate in the ergodic sense for the new algorithms. Preliminary numerical results show that our proposed algorithms are effective for solving the linearly constrained quadratic programming and the robust principal component analysis problems.
MSC:
| 90C25 | Convex programming |
| 65K05 | Numerical mathematical programming methods |
| 94A08 | Image processing (compression, reconstruction, etc.) in information and communication theory |
Keywords:
separable convex optimization; multiple blocks; symmetric alternating direction method of multipliers; proximal point algorithmCitations:
Zbl 1412.90109Software:
RecPFReferences:
| [1] | Bai, J. C., Guo, K. and Chang, X. K., A family of multi-parameterized proximal point algorithms, IEEE Access7(1) (2019) 164021-164028. |
| [2] | Bai, J. C., Hager, W. W. and Zhang, H. C., An inexact accelerated stochastic ADMM for separable convex optimization, Optimization Online (2020), http://www.optimization-online.org/DB˙HTML/2020/08/7990.html. · Zbl 1487.90521 |
| [3] | Bai, J. C., Li, J. C. and Zhang, H. C., Generalized symmetric ADMM for separable convex optimization, Comput. Optim. Appl.70 (2018) 129-170. · Zbl 1461.65126 |
| [4] | Candès, E. J., Li, X. D., Ma, Y. and Wright, J., Robust principal component analysis?J. ACM58(1) (2011) 1-37. · Zbl 1327.62369 |
| [5] | Chandrasekaran, V., Parrilo, P. A. and Willsky, A. S., Latent variable graphical model selection via convex optimization, Ann. Statist.40(4) (2012) 1935-1967. · Zbl 1257.62061 |
| [6] | Chen, C. H., He, B. S., Ye, Y. Y. and Yuan, X. M., The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent, Math. Prog.155(1-2) (2016) 57-79. · Zbl 1332.90193 |
| [7] | Chui, C. K., Lin, S. B. and Zhou, D. X., Deep neural networks for rotation-invariance approximation and learning, Anal. Appl.17(5) (2019) 737-772. · Zbl 1423.68378 |
| [8] | Corman, E. and Yuan, X. M., A generalized proximal point algorithm and its convergence rate, SIAM J. Optim.24(4) (2014) 1614-1638. · Zbl 1311.90099 |
| [9] | Facchinei, F. and Pang, J. S., Finite Dimensional Variational Inequalities and Complementarity Problems, , Vol. I (Springer, Berlin, 2003). · Zbl 1062.90001 |
| [10] | Gabay, D. and Mercier, B., A dual algorithm for the solution of nonlinear variational problems via finite element approximations, Comput. Math. Appl.2(1) (1976) 17-40. · Zbl 0352.65034 |
| [11] | Glowinski, R., Oden, J. T. and Tallec, P. L., Augmented Lagrangian and Operator-Splitting Methods in Nonlinear Mechanics (SIAM, 1989). · Zbl 0698.73001 |
| [12] | Han, D. R., Kong, W. W. and Zhang, W. X., A partial splitting augmented Lagrangian method for low patch-rank image decomposition, J. Math. Imaging Vis.51(1) (2015) 145-160. · Zbl 1332.68270 |
| [13] | Han, D. R., Yuan, X. M. and Zhang, W. X., An augmented Lagrangian based parallel splitting method for separable convex minimization with applications to image processing, Math. Comput.83(289) (2014) 2263-2291. · Zbl 1311.90100 |
| [14] | He, B. S., Parallel splitting augmented Lagrangian methods for monotone structured variational inequalities, Comput. Optim. Appl.42(2) (2009) 195-212. · Zbl 1183.65080 |
| [15] | He, B. S., My 20 years research on alternating direction method of multipliers, Oper. Res. Trans.22 (2018) 1-31. · Zbl 1413.90201 |
| [16] | He, B. S., Study on the splitting methods for separable convex optimization in a unified algorithmic framework, Anal. Theory Appl.36(3) (2020) 262-282. · Zbl 1474.90331 |
| [17] | He, B. S., Hou, L. S. and Yuan, X. M., On full Jacobian decomposition of the augmented Lagrangian method forseparable convex programming, SIAM J. Optim.25(4) (2015) 2274-2312. · Zbl 1327.90209 |
| [18] | He, B. S., Liu, H., Wang, Z. R. and Yuan, X. M., A strictly contractive Peaceman-Rachford splitting method for convex programming, SIAM J. Optim.24(3) (2014) 1011-1040. · Zbl 1327.90210 |
| [19] | He, B. S., Ma, F. and Yuan, X. M., Convergence study on the symmetric version of ADMM with larger step sizes, SIAM J. Imaging Sci.9(3) (2016) 1467-1501. · Zbl 1381.90066 |
| [20] | He, B. S., Tao, M., Xu, M. H. and Yuan, X. M., An alternating direction-based contraction method for linearly constrained separable convex programming problems, Optimization62(4) (2013) 573-596. · Zbl 1273.90122 |
| [21] | He, B. S., Tao, M. and Yuan, X. M., Alternating direction method with Gaussian back substitution for separable convex programming, SIAM J. Optim.22(2) (2012) 313-340. · Zbl 1273.90152 |
| [22] | He, B. S., Tao, M. and Yuan, X. M., A splitting method for separable convex programming, IMA J. Numer. Anal.35(1) (2015) 394-426. · Zbl 1310.65062 |
| [23] | He, B. S., Xu, M. H. and Yuan, X. M., Block-wise ADMM with a relaxation factor for multiple-block convex programming, J. Oper. Res. Soc. China6(4) (2018) 485-506. · Zbl 1424.90204 |
| [24] | Hou, L. S., He, H. J. and Yang, J. F., A partially parallel splitting method for multiple-block separable convex programming with applications to robust PCA, Comput. Optim. Appl.63(1) (2016) 273-303. · Zbl 1343.90061 |
| [25] | Jiang, S. H. and Li, M., A modified strictly contractive Peaceman-Rachford splitting method for multi-block separable convex programming, J. Ind. Manag. Optim.14(1) (2018) 397-412. · Zbl 1412.90109 |
| [26] | R. M. Larsen, Lancaos bidiagonalization with partial reorthogonalization, Technical report, (1998) DAIMI PB-357, Department of Computer Science, Aarhus University, http://soi.stanford.edu/rmunk/PROPACK. |
| [27] | Lions, P. L. and Mercier, B., Splitting algorithms for the sum of two nonlinear operators, SIAM J. Numer. Anal.16(6) (1976) 964-979. · Zbl 0426.65050 |
| [28] | Ma, F. and Ni, M. F., A class of customized proximal point algorithms for linearly constrained convex optimization, Comput. Appl. Math.37(2) (2018) 896-911. · Zbl 06912443 |
| [29] | McLachlan, G. J., Discriminant analysis and statistical pattern recognition, J. R. Stat. Soc. A Stat.168(3) (2005) 469-636. |
| [30] | Peaceman, D. W. and Rachford, H. H., The numerical solution of parabolic and elliptic differential equations, SIAM J. Math. Appl.3(1) (1955) 28-41. · Zbl 0067.35801 |
| [31] | Shen, W., Yang, Z. H., Ying, Y. M. and Yuan, X. M., Stability and optimization error of stochastic gradient descent for pairwise learning, Anal. Appl.18(5) (2020) 887-927. · Zbl 1490.68191 |
| [32] | Shen, Y., Zhang, X. Y. and Zhang, X. Y., A partial PPA block-wise ADMM for multi-block linearly constrained separable convex optimization, Optimization70(3) (2021) 631-657. · Zbl 1465.90065 |
| [33] | Shen, Y., Zuo, Y. N. and Yu, A. L., A partially proximal S-ADMM for separable convex optimization with linear constraints, Appl. Nume. Math.160 (2021) 65-83. · Zbl 1459.90159 |
| [34] | Tao, M. and Yuan, X. M., Recovering low-rank and sparse components of matrices from incomplete and noisy observations, SIAM J. Optim.21(1) (2011) 57-81. · Zbl 1218.90115 |
| [35] | Wang, J. J. and Song, W., An algorithm twisted from generalized ADMM for multi-block separable convex minimization models, J. Comput. Appl. Math.309 (2017) 342-358. · Zbl 1462.90095 |
| [36] | Wang, Y. L., Yang, J. F., Yin, W. T. and Zhang, Y., A new alternating minimization algorithm for total variation image reconstruction, SIAM J. Imag. Sci.1(3) (2008) 248-272. · Zbl 1187.68665 |
| [37] | Wu, Z. M., Liu, F. X. and Li, M., A proximal Peaceman-Rachford splitting method for solving the multi-block separable convex minimization problems, Int. J. Comput. Math.96(4) (2019) 708-728. · Zbl 1499.90163 |
| [38] | Zhou, D. X., Deep distributed convolutional neural networks: Universality, Anal. Appl.16(6) (2018) 895-919. · Zbl 1442.68214 |
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.
