A smoothing proximal gradient algorithm with extrapolation for the relaxation of \({\ell_0}\) regularization problem. (English) Zbl 1516.90103
Summary: In this paper, we consider the exact continuous relaxation model of \({\ell_0}\) regularization problem, which was given by W. Bian and X. Chen [SIAM J. Numer. Anal. 58, No. 1, 858–883, (2020; doi:10.1137/18M1186009] and propose a smoothing proximal gradient algorithm with extrapolation (SPGE) for this kind of problems. Under a general choice of extrapolation parameter, it is proved that all the accumulation points have a common support set, and the ability of the SPGE algorithm to identify the zero entries of the accumulation point within finite iterations is available. We show that any accumulation point of the sequence generated by the SPGE algorithm is a lifted stationary point of the relaxation model. Moreover, a convergence rate concerning proximal residual is established. Finally, we conduct three numerical experiments to illustrate the efficiency of the SPGE algorithm compared with the smoothing proximal gradient (SPG) algorithm proposed by Bian and Chen (2020).
MSC:
| 90C30 | Nonlinear programming |
| 90C52 | Methods of reduced gradient type |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
smoothing approximation; proximal gradient method; extrapolation; \({\ell_0}\) regularization problemSoftware:
iPianoReferences:
| [1] | Beck, A.: First order methods in optimization. Soc. Ind. Appl. Math. (2017) · Zbl 1384.65033 |
| [2] | Beck, A.; Teboulle, M., A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2, 183-202 (2009) · Zbl 1175.94009 · doi:10.1137/080716542 |
| [3] | Beck, A.; Teboulle, M., Smoothing and first order methods: a unified framework, SIAM J. Optim., 22, 557-580 (2012) · Zbl 1251.90304 · doi:10.1137/100818327 |
| [4] | Bertsekas, D.P.: Nonlinear Programming. Athena Scientific, Cambridge, MA (1999) (2nd printing) · Zbl 1015.90077 |
| [5] | Bian, W., Smoothing accelerated algorithm for constrained nonsmooth convex optimization problems, Sci. Sin. Math., 50, 1651-1666 (2020) · Zbl 1499.90151 · doi:10.1360/SSM-2020-0181 |
| [6] | Bian, W.; Chen, X., A smoothing proximal gradient algorithm for nonsmooth convex regression with cardinality penalty, SIAM J. Numer. Anal., 58, 858-883 (2020) · doi:10.1137/18M1186009 |
| [7] | Bian, W.; Chen, X., Smoothing neural network for constrained non-Lipschitz optimization with applications, IEEE Trans. Neural Netw. Learn. Syst., 23, 399-411 (2012) · doi:10.1109/TNNLS.2011.2181867 |
| [8] | Chambolle, A.; Dossal, C., On the convergence of the iterates of the “fast iterative shrinkage/thresholding algorithm”, J. Optim. Theory Appl., 166, 968-982 (2015) · Zbl 1371.65047 · doi:10.1007/s10957-015-0746-4 |
| [9] | Chen, X., Smoothing methods for nonsmooth, nonconvex minimization, Math. Program., 134, 71-99 (2012) · Zbl 1266.90145 · doi:10.1007/s10107-012-0569-0 |
| [10] | Chen, X.; Fukushima, M., A smoothing method for a mathematical program with P-matrix linear complementarity constraints, Comput. Optim. Appl., 27, 223-246 (2004) · Zbl 1046.90086 · doi:10.1023/B:COAP.0000013057.54647.6d |
| [11] | Chen, X.; Nashed, Z.; Qi, L., Smoothing methods and semismooth methods for nondifferentiable operator equations, SIAM J. Numer. Anal., 38, 1200-1216 (2000) · Zbl 0979.65046 · doi:10.1137/S0036142999356719 |
| [12] | Clarkson, KL; Hazan, E.; Woodruff, DP, Sublinear optimization for machine learning, J. ACM, 59, 1-49 (2012) · Zbl 1281.68177 · doi:10.1145/2371656.2371658 |
| [13] | Donoho, DL, Compressed sensing, IEEE Trans. Inf. Theory, 52, 1289-1306 (2006) · Zbl 1288.94016 · doi:10.1109/TIT.2006.871582 |
| [14] | Ghadimi, S.; Lan, G., 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 |
| [15] | Hu, M.; Fukushima, M., Smoothing approach to Nash equilibrium formulations for a class of equilibrium problems with shared complementarity constraints, Comput. Optim. Appl., 52, 415-437 (2012) · Zbl 1275.90107 · doi:10.1007/s10589-011-9416-0 |
| [16] | Jain, P., Kar, P.: Non-convex optimization for machine learning (2017). arXiv:1712.07897 |
| [17] | Liang, J., Schonlieb, C.B.: “Faster FISTA.” European Signal Processing Conference. (2018) |
| [18] | Li, W., Bian, W., Toh, K., C.: DC algorithms for a class of sparse group \({\ell_0}\) regularized optimization problems (2021). arXiv:2109.05251 |
| [19] | Luo, ZQ; Tseng, P., Error bounds and convergence analysis of feasible descent methods: a general approach, Ann. Oper. Res., 46, 157-178 (1993) · Zbl 0793.90076 · doi:10.1007/BF02096261 |
| [20] | Nesterov, Y., Smooth minimization of non-smooth functions, Math. Program., 103, 127-152 (2005) · Zbl 1079.90102 · doi:10.1007/s10107-004-0552-5 |
| [21] | Nesterov, Y., Introductory Lectures on Convex Programming (2004), Dordrecht: Kluwer Academic Publisher, Dordrecht · doi:10.1007/978-1-4419-8853-9 |
| [22] | Nesterov, Y., Gradient methods for minimizing composite functions, Math. Program., 140, 125-161 (2013) · Zbl 1287.90067 · doi:10.1007/s10107-012-0629-5 |
| [23] | Nesterov, Y., Smoothing technique and its applications in semidefinite optimization, Math. Program., 110, 245-259 (2007) · Zbl 1126.90058 · doi:10.1007/s10107-006-0001-8 |
| [24] | Ochs, P.; Chen, Y.; 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 |
| [25] | O’Donoghue, B.; Candes, EJ, Adaptive restart for accelerated gradient schemes, Found. Comput. Math., 15, 715-732 (2015) · Zbl 1320.90061 · doi:10.1007/s10208-013-9150-3 |
| [26] | Pang, JS; Razaviyayn, M.; Alvarado, A., Computing B-stationary points of nonsmooth DC programs, Math. Oper. Res., 42, 95-118 (2017) · Zbl 1359.90106 · doi:10.1287/moor.2016.0795 |
| [27] | Parikh, N.; Boyd, S., Proximal algorithms, Found. Trends Mach. Learn., 1, 127-239 (2014) |
| [28] | Polyak, BT, Some methods of speeding up the convergence of iteration methods, USSR Comput. Math. Math., 4, 1-17 (1964) · Zbl 0147.35301 · doi:10.1016/0041-5553(64)90137-5 |
| [29] | Polyak, RA, Nonlinear rescaling vs. smoothing technique in convex optimization, Math. Program., 92, 197-235 (2002) · Zbl 1022.90014 · doi:10.1007/s101070100293 |
| [30] | Qi, L.; Sun, D.; Zhou, G., A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities, Math. Program., 87, 1-35 (2000) · Zbl 0989.90124 · doi:10.1007/s101079900127 |
| [31] | Wen, B.; Chen, X.; Pong, TK, 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 |
| [32] | Wu, F., Bian, W., Xue, X.: Smoothing fast iterative hard thresholding algorithm for \({\ell_0}\) regularized nonsmooth convex regression problem (2021). arXiv:2104.13107 |
| [33] | Zhang, C.; Chen, X., Smoothing projected gradient method and its application to stochastic linear complementarity problems, SIAM J. Optim., 20, 627-649 (2009) · Zbl 1204.65073 · doi:10.1137/070702187 |
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.
