×

Inertial generalized proximal Peaceman-Rachford splitting method for separable convex programming. (English) Zbl 1464.90056

Summary: The Peaceman-Rachford splitting method (PRSM) is a preferred method for solving the two-block separable convex minimization problems with linear constraints at present. In this paper, we propose an inertial generalized proximal PRSM (abbreviated as IGPRSM) to improve computing efficiency, which unify the ideas of inertial proximal point and linearization technique. Both subproblems are linearized by positive semi-definite proximal matrices, and we explain why the matrix cannot be indefinite. The global convergence and the worst-case asymptotic iteration complexity are derived theoretically via the variational inequality framework. Numerical experiments on LASSO, total variation (TV) based denoising models and image decomposition problems are presented to show the effectiveness of the introduced method even compared with the state-of-the-art methods.

MSC:

90C25 Convex programming
90C30 Nonlinear programming
94A08 Image processing (compression, reconstruction, etc.) in information and communication theory

Software:

RecPF
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alvarez, F., Weak convergence of a relaxed and inertial hybrid projection-proximal point algorithm for maximal monotone operators in Hilbert space, SIAM J. Optim., 14, 3, 773-782 (2004) · Zbl 1079.90096
[2] Alvarez, F.; Attouch, H., An inertial proximal method for maximal monotone operators via discretization of a nonlinear oscillator with damping, Set-Valued Anal., 9, 1-2, 3-11 (2001) · Zbl 0991.65056
[3] Bai, J.; Li, J.; Xu, F.; Zhang, H., Generalized symmetric ADMM for separable convex optimization, Comput. Optim. Appl., 70, 1, 129-170 (2018) · Zbl 1461.65126
[4] Beck, A.; Teboulle, M., A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2, 1, 183-202 (2009) · Zbl 1175.94009
[5] Boyd, SP; Parikh, N.; Chu, E.; Peleato, B.; Eckstein, J., Distributed optimization and statistical learning via the alternating direction method of multipliers, Found. Trends Mach. Learn. Arch., 3, 1, 1-122 (2011) · Zbl 1229.90122
[6] Chambolle, A.; Pock, T., On the ergodic convergence rates of a first-order primal-dual algorithm, Math. Program., 159, 1-2, 253-287 (2016) · Zbl 1350.49035
[7] Chang, X.; Liu, S.; Zhao, P.; Song, D., A generalization of linearized alternating direction method of multipliers for solving two-block separable convex programming, J. Comput. Appl. Math., 357, 251-272 (2019) · Zbl 1415.65134
[8] Chen, C.; Chan, RH; Ma, S.; Yang, J., Inertial proximal ADMM for linearly constrained separable convex optimization, SIAM J. Imaging Sci., 8, 2239-2267 (2015) · Zbl 1328.65134
[9] Chen, L.; Sun, D.; Toh, KC, An efficient inexact symmetric Gauss-Seidel based majorized ADMM for high-dimensional convex composite conic programming, Math. Program., 161, 1, 237-270 (2017) · Zbl 1356.90105
[10] Corman, E.; Yuan, X., A generalized proximal point algorithm and its convergence rate, SIAM J. Optim., 24, 4, 1614-1638 (2014) · Zbl 1311.90099
[11] Donoho, DL; Tsaig, Y., Fast solution of \(l_1\)-norm minimization problems when the solution may be sparse, IEEE Trans. Inf. Theory, 54, 11, 4789-4812 (2008) · Zbl 1247.94009
[12] Dou, M.; Li, H.; Liu, X., An inertial proximal Peaceman-Rachford splitting method, SCI. SIN. Math., 47, 2, 333-348 (2017) · Zbl 1499.90157
[13] Douglas, J.; Rachford, HH, On the numerical solution of heat conduction problems in two and three space variables, Trans. Am. Math. Soc., 82, 421-439 (1956) · Zbl 0070.35401
[14] Eckstein, J., Some saddle-function splitting methods for convex programming, Optim. Methods Softw., 4, 1, 75-83 (1994)
[15] Eckstein, J.; Bertsekas, DP, On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Program., 55, 3, 293-318 (1992) · Zbl 0765.90073
[16] Fazel, M.; Pong, T.; Sun, D.; Tseng, P., Hankel matrix rank minimization with applications to system identification and realization, SIAM J. Matrix Anal. Appl., 34, 3, 946-977 (2013) · Zbl 1302.90127
[17] Fortin, M.; Glowinski, R., Augmented Lagrangian Methods (1983), Amsterdam: North-Holland, Amsterdam · Zbl 0525.65045
[18] Gabay, D.: Chapter IX applications of the method of multipliers to variational inequalities. Studies in Mathematics and Its Applications, vol 15, pp 299-331 (1983). doi:10.1016/S0168-2024(08)70034-1
[19] Gabay, D.; Mercier, B., A dual algorithm for the solution of nonlinear variational problems via finite element approximation, Comput. Math. Appl., 2, 1, 17-40 (1976) · Zbl 0352.65034
[20] Gao, B.; Ma, F., Symmetric alternating direction method with indefinite proximal regularization for linearly constrained convex optimization, J. Optim. Theory Appl., 176, 1, 178-204 (2018) · Zbl 1453.65133
[21] Glowinski, R., Lectures on Numerical Methods for Non-linear Variational Problems (1980), Bombay: Tata Institute of Fundamental Research, Springer, Bombay · Zbl 0456.65035
[22] Glowinski, R.; Marrocco, A., Sur l’approximation, par elements finis d’ordre un, et la resolution, par penalisation-dualit’e, d’une classe de problems de Dirichlet non lineares, Ann. Stat., 9, 41-76 (1975) · Zbl 0368.65053
[23] Goldfarb, D.; Ma, S.; Scheinberg, K., Fast alternating linearization methods for minimizing the sum of two convex functions, Math. Program. Ser. A, 141, 1-2, 349-382 (2013) · Zbl 1280.65051
[24] Gu, Y., Jiang, B., Han, D.: A semi-proximal-based strictly contractive Peaceman-Rachford splitting method. arXiv preprint arXiv:1506.02221 (2015)
[25] Han, D.; Kong, W.; Zhang, W., A partial splitting augmented Lagrangian method for low patch-rank image decomposition, J. Math. Imaging Vis., 51, 1, 145-160 (2015) · Zbl 1332.68270
[26] Han, D.; Yuan, X.; Zhang, W.; Cai, X., An ADM-based splitting method for separable convex programming, Comput. Optim. Appl., 54, 2, 343-369 (2013) · Zbl 1269.90078
[27] He, B.; Liu, H.; Wang, Z.; Yuan, X., A strictly contractive Peaceman-Rachford splitting method for convex programming, SIAM J. Optim., 24, 3, 1011-1040 (2014) · Zbl 1327.90210
[28] He, B.; Ma, F.; Yuan, X., Convergence study on the symmetric version of ADMM with larger step sizes, SIAM J. Imaging Sci., 9, 3, 1467-1501 (2016) · Zbl 1381.90066
[29] He, B., Ma, F., Yuan, X.: Optimal linearized alternating direction method of multipliers for convex programming. http://www.optimization-online.org (2017)
[30] He, B.; Tao, M.; Yuan, X., Alternating direction method with Gaussian back substitution for separable convex programming, SIAM J. Optim., 22, 2, 313-340 (2012) · Zbl 1273.90152
[31] He, B.; Yuan, X., 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
[32] He, B.; Yuan, X., On non-ergodic convergence rate of Douglas-Rachford alternating direction method of multipliers, Numer. Math., 130, 3, 567-577 (2015) · Zbl 1320.90060
[33] He, Y.; Li, H.; Liu, X., Relaxed inertial proximal Peaceman-Rachford splitting method for separable convex programming, Front. Math. China, 13, 3, 1-24 (2018) · Zbl 1401.90154
[34] Jiang, F.; Wu, Z.; Cai, X., Generalized ADMM with optimal indefinite proximal term for linearly constrained convex optimization, J. Ind. Manag. Optim., 13, 5, 1-22 (2017)
[35] Li, X.; Sun, D.; Toh, K., A Schur complement based semi-proximal ADMM for convex quadratic conic programming and extensions, Math. Program., 155, 1, 333-373 (2016) · Zbl 1342.90134
[36] Lions, PL; Mercier, B., Splitting algorithms for the sum of two nonlinear operators, SIAM J. Numer. Anal., 16, 6, 964-979 (1979) · Zbl 0426.65050
[37] Lorenz, DA; Pock, T., An inertial forward-backward algorithm for monotone inclusions, J. Math. Imaging Vis., 51, 2, 311-325 (2015) · Zbl 1327.47063
[38] Ma, S., Alternating proximal gradient method for convex minimization, J. Sci. Comput., 68, 2, 546-572 (2016) · Zbl 1371.65056
[39] Moudafi, A.; Oliny, M., Convergence of a splitting inertial proximal method for monotone operators, J. Comput. Appl. Math., 155, 2, 447-454 (2003) · Zbl 1027.65077
[40] Opial, Z., Weak convergence of the sequence of successive approximations for nonexpansive mappings, Bull. Am. Math. Soc., 73, 4, 591-597 (1967) · Zbl 0179.19902
[41] Peaceman, DW; Rachford, HH, The numerical solution of parabolic and elliptic differential equations, J. Soc. Ind. Appl. Math., 3, 1, 28-41 (1955) · Zbl 0067.35801
[42] Rudin, LI; Osher, S.; Fatemi, E., Nonlinear total variation based noise removal algorithms, Phys. D Nonlinear Phenomena, 60, 1-4, 259-268 (1992) · Zbl 0780.49028
[43] Sun, H.; Tian, M.; Sun, M., The symmetric ADMM with indefinite proximal regularization and its application, J. Inequal. Appl., 2017, 1, 172 (2017) · Zbl 1368.90128
[44] Sun, M.; Liu, J., Generalized Peaceman-Rachford splitting method for separable convex programming with applications to image processing, J. Appl. Math. Comput., 51, 1-2, 605-622 (2016) · Zbl 1338.90307
[45] Sun, M.; Wang, Y.; Liu, J., Generalized Peaceman-Rachford splitting method for multiple-block separable convex programming with applications to robust PCA, Calcolo, 54, 1, 77-94 (2017) · Zbl 1368.90129
[46] Tibshirani, R., Regression shrinkage and selection via the LASSO: a retrospective, J. R. Stat. Soc. Ser. B Stat. Methodol., 73, 3, 273-282 (2011) · Zbl 1411.62212
[47] Wang, J.; Song, W., An algorithm twisted from generalized ADMM for multi-block separable convex minimization models, J. Comput. Appl. Math., 309, 342-358 (2017) · Zbl 1462.90095
[48] Wang, Y.; Yang, J.; Yin, W.; Zhang, Y., A new alternating minimization algorithm for total variation image reconstruction, SIAM J. Imaging Sci., 1, 3, 248-272 (2008) · Zbl 1187.68665
[49] Yang, J.; Yin, W.; Zhang, Y.; Wang, Y., A fast algorithm for edge-preserving variational multichannel image restoration, SIAM J. Imaging Sci., 2, 2, 569-592 (2009) · Zbl 1181.68304
[50] Yang, J.; Yuan, X., Linearized augmented Lagrangian and alternating direction methods for nuclear norm minimization, Math. Comput., 82, 281, 301-329 (2012) · Zbl 1263.90062
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.