Extrapolated smoothing descent algorithm for constrained nonconvex and nonsmooth composite problems. (English) Zbl 1511.65047
Summary: In this paper, the authors propose a novel smoothing descent type algorithm with extrapolation for solving a class of constrained nonsmooth and nonconvex problems, where the nonconvex term is possibly nonsmooth. Their algorithm adopts the proximal gradient algorithm with extrapolation and a safe-guarding policy to minimize the smoothed objective function for better practical and theoretical performance. Moreover, the algorithm uses a easily checking rule to update the smoothing parameter to ensure that any accumulation point of the generated sequence is an (affine-scaled) Clarke stationary point of the original nonsmooth and nonconvex problem. Their experimental results indicate the effectiveness of the proposed algorithm.
MSC:
| 65K05 | Numerical mathematical programming methods |
| 94A08 | Image processing (compression, reconstruction, etc.) in information and communication theory |
| 90C26 | Nonconvex programming, global optimization |
Keywords:
constrained nonconvex and nonsmooth optimization; smooth approximation; proximal gradient algorithm with extrapolation; gradient descent algorithm; image reconstructionReferences:
| [1] | Attouch, H.; Bolte, J.; Svaiter, B. F., Convergence of descent methods for semi-algebraic and tame problems: Proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods, Math. Program., 137, 91-129 (2013) · Zbl 1260.49048 · doi:10.1007/s10107-011-0484-9 |
| [2] | Bao, C. L.; Dong, B.; Hou, L. K., Image restoration by minimizing zero norm of wavelet frame coefficients, Inverse Probl., 32, 115004 (2016) · Zbl 1409.94026 · doi:10.1088/0266-5611/32/11/115004 |
| [3] | Bian, W.; Chen, X. J., Linearly constrained non-Lipschitz optimization for image restoration, SIAM J. Imaging Sci., 8, 2294-2322 (2015) · Zbl 1327.90299 · doi:10.1137/140985639 |
| [4] | Bian, W.; Chen, X. J., Optimality and complexity for constrained optimization problems with non-convex regularization, Math. Oper. Res., 42, 1063-1084 (2017) · Zbl 1386.90167 · doi:10.1287/moor.2016.0837 |
| [5] | Bian, W.; Chen, X. J., A smoothing proximal gradient algorithm for nonsmooth convex regression with cardinality penalty, SIAM J. Numer. Anal., 58, 858-883 (2020) · doi:10.1137/18M1186009 |
| [6] | Bian, W.; Chen, X. J.; Ye, Y. Y., Complexity analysis of interior point algorithms for non-Lipschitz and nonconvex minimization, Math. Program., 149, 301-327 (2015) · Zbl 1318.90075 · doi:10.1007/s10107-014-0753-5 |
| [7] | Bonettini, S.; Loris, I.; Porta, F., On the convergence of a linesearch based proximal-gradient method for nonconvex optimization, Inverse Probl., 33, 055005 (2017) · Zbl 1373.65040 · doi:10.1088/1361-6420/aa5bfd |
| [8] | Burke, J. V.; Ferris, M. C.; Qian, M. J., On the Clarke subdifferential of the distance function of a closed set, J. Math. Anal. Appl., 166, 199-213 (1992) · Zbl 0761.49009 · doi:10.1016/0022-247X(92)90336-C |
| [9] | Candes, E. J.; Wakin, M. B.; Boyd, S. P., Enhancing sparsity by reweighted ℓ_1 minimization, J. Fourier Anal. Appl., 14, 877-905 (2008) · Zbl 1176.94014 · doi:10.1007/s00041-008-9045-x |
| [10] | Chan, R. H.; Tao, M.; Yuan, X. M., Constrained total variation deblurring models and fast algorithms based on alternating direction method of multipliers, SIAM J. Imaging Sci., 6, 680-697 (2013) · Zbl 1279.68322 · doi:10.1137/110860185 |
| [11] | Chen, X. J., Smoothing methods for nonsmooth, nonconvex minimization, Math. Program., 134, 71-99 (2012) · Zbl 1266.90145 · doi:10.1007/s10107-012-0569-0 |
| [12] | Chen, X. J.; Ng, M. K.; Zhang, C., Non-Lipschitz ℓ_p-regularization and box constrained model for image restoration, IEEE Trans. Image Process., 21, 4709-4721 (2012) · Zbl 1373.94080 · doi:10.1109/TIP.2012.2214051 |
| [13] | Chen, X. J.; Niu, L. F.; Yuan, Y. X., Optimality conditions and a smoothing trust region Newton method for nonLipschitz optimization, SIAM J. Optim., 23, 1528-1552 (2013) · Zbl 1291.90238 · doi:10.1137/120871390 |
| [14] | Chen, X. J.; Zhou, W. J., Smoothing nonlinear conjugate gradient method for image restoration using nonsmooth nonconvex minimization, SIAM J. Imaging Sci., 3, 765-790 (2010) · Zbl 1200.65031 · doi:10.1137/080740167 |
| [15] | Chen, Y. M.; Liu, H. C.; Ye, X. J.; Zhang, Q. C., Learnable descent algorithm for nonsmooth nonconvex image reconstruction, SIAM J. Imaging Sci., 14, 1532-1564 (2021) · Zbl 1474.90353 · doi:10.1137/20M1353368 |
| [16] | Clarke, F. H., Optimization and Nonsmooth Analysis (1990), Philadelphia: John Wiley and Sons, Philadelphia · Zbl 0696.49002 · doi:10.1137/1.9781611971309 |
| [17] | Foucart, S.; Lai, M. J., Sparsest solutions of underdetermined linear systems via ℓ_q-minimization for 0 < q < 1, Appl. Comput. Harmon. Anal., 26, 395-407 (2009) · Zbl 1171.90014 · doi:10.1016/j.acha.2008.09.001 |
| [18] | Fukushima, M.; Mine, H., A generalized proximal point algorithm for certain non-convex minimization problems, International Journal of Systems Science, 12, 989-1000 (1981) · Zbl 0467.65028 · doi:10.1080/00207728108963798 |
| [19] | Gao, Y. M.; Wu, C. L., On a general smoothly truncated regularization for variational piecewise constant image restoration: construction and convergent algorithms, Inverse Probl., 36, 045007 (2020) · Zbl 1471.94001 · doi:10.1088/1361-6420/ab6619 |
| [20] | Ghadimi, S.; Lan, G. H., Accelerated gradient methods for nonconvex nonlinear and stochastic programming, Math. Program., 156, 59-99 (2016) · Zbl 1335.62121 · doi:10.1007/s10107-015-0871-8 |
| [21] | Gu, B., Wang, D., Huo, Z. Y. and Huang, H., Inexact proximal gradient methods for non-convex and non-smooth optimization, in AAAI, 32, 2018. |
| [22] | Hintermüller, M. and Wu, T., Nonconvex TV^q-models in image restoration: Analysis and a trust-region regularization based superlinearly convergent solver, SIAM J. Imaging Sci., 6, 2013, 1385-1415. · Zbl 1281.65033 |
| [23] | Kak, A. C.; Slaney, M., Principles of Computerized Tomographic Imaging (2001), Philadelphia, PA, USA: SIAM, Philadelphia, PA, USA · Zbl 0984.92017 · doi:10.1137/1.9780898719277 |
| [24] | Kong, W. W.; Melo, J. G.; Monteiro, R. D., Complexity of a quadratic penalty accelerated inexact proximal point method for solving linearly constrained nonconvex composite programs, SIAM J. Optim., 29, 2566-2593 (2019) · Zbl 1504.90101 · doi:10.1137/18M1171011 |
| [25] | Kong, W. W.; Melo, J. G.; Monteiro, R. D., An efficient adaptive accelerated inexact proximal point method for solving linearly constrained nonconvex composite problems, Comput. Optim. Appl., 76, 305-346 (2020) · Zbl 1443.90282 · doi:10.1007/s10589-020-00188-w |
| [26] | Lai, M. J.; Xu, Y. Y.; Yin, W. T., Improved iteratively reweighted least squares for unconstrained smoothed ℓ_q minimization, SIAM J. Numer. Anal., 51, 927-957 (2013) · Zbl 1268.49038 · doi:10.1137/110840364 |
| [27] | Li, H. and Lin, Z. C., Accelerated proximal gradient methods for nonconvex programming, in NIPS, 2015, 379-387. |
| [28] | Li, Q. W., Zhou, Y., Liang, Y. B. and Varshney, P. K., Convergence analysis of proximal gradient with momentum for nonconvex optimization, in ICML, PMLR, 2017, 2111-2119. |
| [29] | Lions, P-L; Mercier, B., Splitting algorithms for the sum of two nonlinear operators, SIAM J. Numer. Anal., 16, 964-979 (1979) · Zbl 0426.65050 · doi:10.1137/0716071 |
| [30] | Liu, Z. F.; Wu, C. L.; Zhao, Y. N., A new globally convergent algorithm for non-Lipschitz l_p − l_q minimization, Adv. Comput. Math., 45, 1369-1399 (2019) · Zbl 1415.49022 · doi:10.1007/s10444-019-09668-y |
| [31] | Nesterov, Y., Smooth minimization of non-smooth functions, Math. Program., 103, 127-152 (2005) · Zbl 1079.90102 · doi:10.1007/s10107-004-0552-5 |
| [32] | Nikolova, M., Analysis of the recovery of edges in images and signals by minimizing nonconvex regularized least-squares, SIAM J. Multiscale Model. Simul., 4, 960-991 (2005) · Zbl 1091.94007 · doi:10.1137/040619582 |
| [33] | Nikolova, M.; Ng, M. K.; Tam, C. P., Fast nonconvex nonsmooth minimization methods for image restoration and reconstruction, IEEE Trans. Image Process., 19, 3073-3088 (2010) · Zbl 1371.94277 · doi:10.1109/TIP.2010.2052275 |
| [34] | Nikolova, M.; Ng, M. K.; Zhang, S. Q.; Ching, W. K., Efficient reconstruction of piecewise constant images using nonsmooth nonconvex minimization, SIAM J. Imaging Sci., 1, 2-25 (2008) · Zbl 1207.94017 · doi:10.1137/070692285 |
| [35] | Ochs, P.; Chen, Y. J.; Brox, T.; Pock, T., iPiano: Inertial proximal algorithm for nonconvex optimization, SIAM J. Imaging Sci., 7, 1388-1419 (2014) · Zbl 1296.90094 · doi:10.1137/130942954 |
| [36] | Ochs, P.; Dosovitskiy, A.; Brox, T.; Pock, T., On iteratively reweighted algorithms for nonsmooth nonconvex optimization in computer vision, SIAM J. Imaging Sci., 8, 331-372 (2015) · Zbl 1326.65078 · doi:10.1137/140971518 |
| [37] | Rudin, L. I.; Osher, S.; Fatemi, E., Nonlinear total variation based noise removal algorithms, Phys. D, Nonlinear Phenomena, 60, 259-168 (1992) · Zbl 0780.49028 · doi:10.1016/0167-2789(92)90242-F |
| [38] | Villa, S.; Salzo, S.; Baldassarre, L.; Verri, A., Accelerated and inexact forward-backward algorithms, SIAM J. Optim, 23, 1607-1633 (2013) · Zbl 1295.90049 · doi:10.1137/110844805 |
| [39] | Wang, W.; Chen, Y. M., An accelerated smoothing gradient method for nonconvex nonsmooth minimization in image processing, J. Sci. Comput., 90, 1-18 (2022) · Zbl 1483.65102 · doi:10.1007/s10915-021-01677-8 |
| [40] | Wang, W.; Wu, C. L.; Gao, Y. M., A nonconvex truncated regularization and box-constrained model for CT reconstruction, Inverse Probl. Imag., 14, 867-890 (2020) · Zbl 1460.92114 · doi:10.3934/ipi.2020040 |
| [41] | Wang, W.; Wu, C. L.; Tai, X. C., A globally convergent algorithm for a constrained non-Lipschitz image restoration model, J. Sci. Comput., 83, 1-19 (2020) · Zbl 1455.94037 · doi:10.1007/s10915-020-01190-4 |
| [42] | Wen, B.; Chen, X. J.; Pong, T. K., Linear convergence of proximal gradient algorithm with extrapolation for a class of nonconvex nonsmooth minimization problems, SIAM J. Optim., 27, 124-145 (2017) · Zbl 1359.90138 · doi:10.1137/16M1055323 |
| [43] | Wu, C. L.; Tai, X. C., Augmented Lagrangian method, dual methods, and split Bregman iteration for ROF, vectorial TV, and high order models, SIAM J. Imaging Sci., 3, 300-339 (2010) · Zbl 1206.90245 · doi:10.1137/090767558 |
| [44] | Wu, Z.; Li, M., General inertial proximal gradient method for a class of nonconvex nonsmooth optimization problems, Comput. Optim. Appl., 73, 129-158 (2019) · Zbl 1420.90054 · doi:10.1007/s10589-019-00073-1 |
| [45] | Xu, Z. B.; Chang, X. Y.; Xu, F. M.; Zhang, H., ℓ_½ regularization: A thresholding representation theory and a fast solver, IEEE Trans. Neural Netw. Learn. Syst., 23, 1013-1027 (2012) · doi:10.1109/TNNLS.2012.2197412 |
| [46] | Yang, L., Proximal gradient method with extrapolation and line search for a class of nonconvex and nonsmooth problems, 2017, arXiv:1711.06831. |
| [47] | Yao, Q. M., Kwok, J. T., Gao, F., et al., Efficient inexact proximal gradient algorithm for nonconvex problems, 2016, arXiv:1612.09069. |
| [48] | Zeng, C.; Jia, R.; Wu, C. L., An iterative support shrinking algorithm for non-Lipschitz optimization in image restoration, J. Math. Imaging Vis., 61, 122-139 (2019) · Zbl 1487.94034 · doi:10.1007/s10851-018-0830-0 |
| [49] | Zeng, C.; Wu, C. L., On the edge recovery property of noncovex nonsmooth regularization in image restoration, SIAM J. Numer. Anal., 56, 1168-1182 (2018) · Zbl 1391.49050 · doi:10.1137/17M1123687 |
| [50] | Zhang, H. M.; Dong, B.; Liu, B. D., A reweighted joint spatial-radon domain CT image reconstruction model for metal artifact reduction, SIAM J. Imaging Sci., 11, 707-733 (2018) · Zbl 1421.94011 · doi:10.1137/17M1140212 |
| [51] | Zhang, X.; Zhang, X. Q., A new proximal iterative hard thresholding method with extrapolation for ℓ_0 minimization, J. Sci. Comput., 79, 809-826 (2019) · Zbl 1423.90201 · doi:10.1007/s10915-018-0874-8 |
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.
