×

Two-step fixed-point proximity algorithms for multi-block separable convex problems. (English) Zbl 1368.65088

The authors develop convergent and computationally efficient algorithms for solving multi-block separable convex optimization problems. Moreover, specific two-step fixed-point proximity algorithms from the proposed iterative schemes are derived and their global convergence is established. Numerical experiments demonstrate the numerical efficiency of the proposed algorithms.

MSC:

65K05 Numerical mathematical programming methods
90C25 Convex programming
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Attouch, H., Briceno-Arias, L.M., Combettes, P.L.: A parallel splitting method for coupled monotone inclusions. SIAM J. Control Optim. 48, 3246-3270 (2010) · Zbl 1218.47089 · doi:10.1137/090754297
[2] Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces, AMS Books in Mathematics. Springer, New York (2011) · Zbl 1218.47001 · doi:10.1007/978-1-4419-9467-7
[3] Cai, J., Chan, R., Shen, Z.: A framelet-based image inpainting algorithm. Appl. Comput. Harmonic Anal. 24, 131-149 (2007) · Zbl 1135.68056 · doi:10.1016/j.acha.2007.10.002
[4] Cai, X., Han, D., Yuan, X.: On the convergence of the direct extension of ADMM for three-block separable convex minimization models with one strongly convex function. Comput. Optim. Appl. (2016). doi:10.1007/s10589-016-9860-y · Zbl 1372.90079 · doi:10.1007/s10589-016-9860-y
[5] Cai, J., Osher, S., Shen, Z.: Linearized Bregman iteration for frame based image deblurring. SIAM J. Imaging Sci. 2, 226-252 (2009) · Zbl 1175.94010 · doi:10.1137/080733371
[6] Chambolle, 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
[7] Chan, R., Chan, T., Shen, L., Shen, Z.: Wavelet algorithms for high-resolution image reconstruction. SIAM J. Sci. Comput. 24, 1408-1432 (2003) · Zbl 1031.68127 · doi:10.1137/S1064827500383123
[8] Chan, R., Riemenschneider, S.D., Shen, L., Shen, Z.: Tight frame: the efficient way for high-resolution image reconstruction. Appl. Comput. Harmonic Anal. 17, 91-115 (2004) · Zbl 1046.42026 · doi:10.1016/j.acha.2004.02.003
[9] Chen, C., He, B., Ye, Y., Yuan, X.: The direct extension of admm for multi-block convex minimization problems is not necessarily convergent. Math. Program. 155, 57-79 (2016) · Zbl 1332.90193
[10] Cortes, C., Vapnik, V.: Support-vector networks. Mach. Learn. 20, 273-297 (1995) · Zbl 0831.68098
[11] Davis, D., Yin, W.: A three-operator splitting scheme and its optimization applications. UCLA CAM Report 15-13 · Zbl 1464.47041
[12] Deng, W., Lai, M.-J., Peng, Z., Yin, W.: Parallel multi-block admm with o(1/k) convergence, UCLA CAM 13-64 (2014) · Zbl 1328.90107
[13] 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. 3, 1015-1046 (2010) · Zbl 1206.90117 · doi:10.1137/09076934X
[14] 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. Comput. Math.Appl. 2, 17-40 (1976) · Zbl 0352.65034 · doi:10.1016/0898-1221(76)90003-1
[15] Goldstein, T., Osher, S.: The split Bregman method for \[\ell^1\] ℓ1 regularization problems. SIAM J. Imaging Sci. 2, 323-343 (2009) · Zbl 1177.65088 · doi:10.1137/080725891
[16] He, B., Tao, M., Yuan, X.: 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
[17] He, B., Yuan, X.: Linearized alternating direction method of multipliers with gaussian back substitution for seperable convex programming. Numer. Algebra Control Optim. 22, 247-260 (2013) · Zbl 1264.90139 · doi:10.3934/naco.2013.3.247
[18] Li, M., Sun, D., Toh, K.-C.: A convergent 3-block semi-proximal admm for convex minimization problems with one strongly convex block. Asia Pacific J. Oper. Res. 32, 1550024 (2015) · Zbl 1327.90214 · doi:10.1142/S0217595915500244
[19] Li, Q., Micchelli, C.A., Shen, L., Xu, Y.: A proximity algorithm accelerated by Gauss-Seidel iterations for L1/TV denoising models. Inverse Probl. 28, 095003 (2012) · Zbl 1273.65085 · doi:10.1088/0266-5611/28/9/095003
[20] Li, Q., Shen, L., Yuesheng, X., Zhang, N.: Multi-step fixed-point proximity algorithms for solving a class of convex optimization problems arising from image processing. Adv. Comput. Math. 41, 387-422 (2015) · Zbl 1326.65069 · doi:10.1007/s10444-014-9363-2
[21] Li, Q., Shen, L., Yang, L.: Split-bregman iteration for framelet based image inpainting. Appl. Comput. Harmonic Anal. 32, 145-154 (2012) · Zbl 1236.94021 · doi:10.1016/j.acha.2011.09.007
[22] Li, Q., Zhang, N.: Fast proximity-gradient algorithms for structured convex optimization problems. Appl. Comput. Harmonic Anal. 41, 491-517 (2016) · Zbl 1346.65031 · doi:10.1016/j.acha.2015.11.004
[23] Lin, T., Ma, S., Zhang, S.: On the 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] Lustig, M., Donoho, D., Pauly, J.M.: Sparse MRI: the application of compressed sensing for rapid MR imaging. Magn. Reson. Med. 58, 1182-1195 (2007) · doi:10.1002/mrm.21391
[25] Micchelli, C.A., Shen, L., Xu, Y.: Proximity algorithms for image models: denoising. Inverse Probl. 27, 045009 (2011) · Zbl 1216.94015 · doi:10.1088/0266-5611/27/4/045009
[26] Moreau, J.J.: Fonctions convexes duales et points proximaux dans un espace hilbertien. C.R. Acad. Sci. Paris Sér. A Math. 255, 1897-2899 (1962) · Zbl 0118.10502
[27] Nikolova, M.: Local strong homogeneity of a regularized estimator. SIAM J. Appl. Math. 61, 633-658 (2000) · Zbl 0991.94015 · doi:10.1137/S0036139997327794
[28] Rudin, L.I., Osher, S.: Total variation based image restoration with free local constraints, In: IEEE International Conference on Image Processing, pp. 31-35 (1994)
[29] Ruszczynski, A.: Parallel decomposition of multistage stochastic programming problems. Math. Program. 58, 201-228 (1993) · Zbl 0777.90036 · doi:10.1007/BF01581267
[30] Sawatzky, A., Qi, X., Schirra, C.O., Anastasio, M.A.: Proximal ADMM for multi-channel image reconstruction in spectral X-ray CT. IEEE Trans. Med. Imaging 33, 1657-1668 (2014) · doi:10.1109/TMI.2014.2321098
[31] Shi, W., Ling, W., Wu, W., Yin, W.: Extra: an exact first-order algorithm for decentralized consensus optimization. SIAM J. Optim. 25, 944-966 (2015) · Zbl 1328.90107 · doi:10.1137/14096668X
[32] Sun, D., Toh, K.C., Yang, L.: A convergent 3-block semi-proximal alternating direction method of multipliers for conic programming with \[44\]-type of constraints. SIAM J. Optim. 25, 882-915 (2014) · Zbl 1328.90083
[33] Tyrrell Rockafellar, R.: Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14, 877-898 (1976) · Zbl 0358.90053 · doi:10.1137/0314056
[34] Tibshirani, R., Saunders, M., Rosset, S., Zhu, J., Knight, K.: Sparsity and smoothness via the fused lasso. J. R. Stat. Soc. 67, 91-108 (2005) · Zbl 1060.62049 · doi:10.1111/j.1467-9868.2005.00490.x
[35] Tibshirani, R.: Regression shrinkage and selection via the lasso. J. R. Stat. Soc. 58, 267-288 (1996) · Zbl 0850.62538
[36] Wen, Z., Goldfarb, D., Yin, W.: Alternating direction augmented lagrangian methods for semidefinite programming. Math. Program. Comput. 2, 203-230 (2010) · Zbl 1206.90088 · doi:10.1007/s12532-010-0017-1
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.