Extrapolated Smoothing Descent Algorithm for Constrained Nonconvex and Nonsmooth Composite Problems

Abstract

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.

Keywords

Constrained nonconvex and nonsmooth optimization / Smooth approximation / Proximal gradient algorithm with extrapolation / Gradient descent algorithm / Image reconstruction

References

[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., 2013, 137: 91-129

[2] Bao C L, Dong B, Hou L K Image restoration by minimizing zero norm of wavelet frame coefficients. Inverse Probl., 2016, 32: 115004

[3] Bian W, Chen X J. Linearly constrained non-Lipschitz optimization for image restoration. SIAM J. Imaging Sci., 2015, 8: 2294-2322

[4] Bian W, Chen X J. Optimality and complexity for constrained optimization problems with non-convex regularization. Math. Oper. Res., 2017, 42: 1063-1084

[5] Bian W, Chen X J. A smoothing proximal gradient algorithm for nonsmooth convex regression with cardinality penalty. SIAM J. Numer. Anal., 2020, 58: 858-883

[6] Bian W, Chen X J, Ye Y Y. Complexity analysis of interior point algorithms for non-Lipschitz and nonconvex minimization. Math. Program., 2015, 149: 301-327

[7] Bonettini S, Loris I, Porta F On the convergence of a linesearch based proximal-gradient method for nonconvex optimization. Inverse Probl., 2017, 33: 055005

[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., 1992, 166: 199-213

[9] Candes E J, Wakin M B, Boyd S P. Enhancing sparsity by reweighted ℓ ₁ minimization. J. Fourier Anal. Appl., 2008, 14: 877-905

[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., 2013, 6: 680-697

[11] Chen X J. Smoothing methods for nonsmooth, nonconvex minimization. Math. Program., 2012, 134: 71-99

[12] Chen X J, Ng M K, Zhang C. Non-Lipschitz ℓ _p-regularization and box constrained model for image restoration. IEEE Trans. Image Process., 2012, 21: 4709-4721

[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., 2013, 23: 1528-1552

[14] Chen X J, Zhou W J. Smoothing nonlinear conjugate gradient method for image restoration using nonsmooth nonconvex minimization. SIAM J. Imaging Sci., 2010, 3: 765-790

[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., 2021, 14: 1532-1564

[16] Clarke F H. Optimization and Nonsmooth Analysis, 1990, Philadelphia: John Wiley and Sons

[17] Foucart S, Lai M J. Sparsest solutions of underdetermined linear systems via ℓ _q-minimization for 0 < q < 1. Appl. Comput. Harmon. Anal., 2009, 26: 395-407

[18] Fukushima M, Mine H. A generalized proximal point algorithm for certain non-convex minimization problems. International Journal of Systems Science, 1981, 12: 989-1000

[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., 2020, 36: 045007

[20] Ghadimi S, Lan G H. Accelerated gradient methods for nonconvex nonlinear and stochastic programming. Math. Program., 2016, 156: 59-99

[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.

[23] Kak A C, Slaney M. Principles of Computerized Tomographic Imaging, 2001, Philadelphia, PA, USA: SIAM

[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., 2019, 29: 2566-2593

[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., 2020, 76: 305-346

[26] Lai M J, Xu Y Y, Yin W T. Improved iteratively reweighted least squares for unconstrained smoothed ℓ _q minimization. SIAM J. Numer. Anal., 2013, 51: 927-957

[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., 1979, 16: 964-979

[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., 2019, 45: 1369-1399

[31] Nesterov Y. Smooth minimization of non-smooth functions. Math. Program., 2005, 103: 127-152

[32] Nikolova M. Analysis of the recovery of edges in images and signals by minimizing nonconvex regularized least-squares. SIAM J. Multiscale Model. Simul., 2005, 4: 960-991

[33] Nikolova M, Ng M K, Tam C P. Fast nonconvex nonsmooth minimization methods for image restoration and reconstruction. IEEE Trans. Image Process., 2010, 19: 3073-3088

[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., 2008, 1: 2-25

[35] Ochs P, Chen Y J, Brox T, Pock T. iPiano: Inertial proximal algorithm for nonconvex optimization. SIAM J. Imaging Sci., 2014, 7: 1388-1419

[36] Ochs P, Dosovitskiy A, Brox T, Pock T. On iteratively reweighted algorithms for nonsmooth nonconvex optimization in computer vision. SIAM J. Imaging Sci., 2015, 8: 331-372

[37] Rudin L I, Osher S, Fatemi E. Nonlinear total variation based noise removal algorithms. Phys. D, Nonlinear Phenomena, 1992, 60: 259-168

[38] Villa S, Salzo S, Baldassarre L, Verri A. Accelerated and inexact forward-backward algorithms. SIAM J. Optim, 2013, 23: 1607-1633

[39] Wang W, Chen Y M. An accelerated smoothing gradient method for nonconvex nonsmooth minimization in image processing. J. Sci. Comput., 2022, 90: 1-18

[40] Wang W, Wu C L, Gao Y M. A nonconvex truncated regularization and box-constrained model for CT reconstruction. Inverse Probl. Imag., 2020, 14: 867-890

[41] Wang W, Wu C L, Tai X C. A globally convergent algorithm for a constrained non-Lipschitz image restoration model. J. Sci. Comput., 2020, 83: 1-19

[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., 2017, 27: 124-145

[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., 2010, 3: 300-339

[44] Wu Z, Li M. General inertial proximal gradient method for a class of nonconvex nonsmooth optimization problems. Comput. Optim. Appl., 2019, 73: 129-158

[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., 2012, 23: 1013-1027

[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., 2019, 61: 122-139

[49] Zeng C, Wu C L. On the edge recovery property of noncovex nonsmooth regularization in image restoration. SIAM J. Numer. Anal., 2018, 56: 1168-1182

[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., 2018, 11: 707-733

[51] Zhang X, Zhang X Q. A new proximal iterative hard thresholding method with extrapolation for ℓ ₀ minimization. J. Sci. Comput., 2019, 79: 809-826