×
Lapucci, Matteo; Levato, Tommaso; Sciandrone, Marco

Convergent inexact penalty decomposition methods for cardinality-constrained problems. (English) Zbl 1470.90094

J. Optim. Theory Appl. 188, No. 2, 473-496 (2021).
Summary: In this manuscript, we consider the problem of minimizing a smooth function with cardinality constraint, i.e., the constraint requiring that the \(\ell_0\)-norm of the vector of variables cannot exceed a given threshold value. A well-known approach of the literature is represented by the class of penalty decomposition methods, where a sequence of penalty subproblems, depending on the original variables and new variables, are inexactly solved by a two-block decomposition method. The inner iterates of the decomposition method require to perform exact minimizations with respect to the two blocks of variables. The computation of the global minimum with respect to the original variables may be prohibitive in the case of nonconvex objective function. In order to overcome this nontrivial issue, we propose a modified penalty decomposition method, where the exact minimizations with respect to the original variables are replaced by suitable line searches along gradient-related directions. We also present a derivative-free penalty decomposition algorithm for black-box optimization. We state convergence results of the proposed methods, and we report the results of preliminary computational experiments.

MSC:

90C26 Nonconvex programming, global optimization
90C30 Nonlinear programming
65K05 Numerical mathematical programming methods

Keywords:

cardinality constraint; penalty decomposition method; nonconvex optimization; global convergence; derivative-free optimization

Software:

UCI-ml; SciPy; DFL; TESTGO; DFN; Python; DFBOX_IMPR; SDBOX; DIRMIN; glasso; ElemStatLearn
PDF BibTeX XML Cite
\textit{M. Lapucci} et al., J. Optim. Theory Appl. 188, No. 2, 473--496 (2021; Zbl 1470.90094)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] Blumensath, T.; Davies, M., Iterative hard thresholding for compressed sensing, Appl. Comput. Harmon. Anal., 27, 3, 265-274 (2009) · Zbl 1174.94008
[2] Donoho, DL, Compressed sensing, IEEE Trans. Inf. Theory, 52, 4, 1289-1306 (2006) · Zbl 1288.94016
[3] Bertsimas, D.; King, A.; Mazumder, R., Best subset selection via a modern optimization lens, Ann. Statist., 44, 813-852 (2016) · Zbl 1335.62115
[4] Di Gangi, L., Lapucci, M., Schoen, F., Sortino, A.: An efficient optimization approach for best subset selection in linear regression, with application to model selection and fitting in autoregressive time-series. Comput. Optim. Appl. (2019) · Zbl 1435.90088
[5] Miyashiro, R.; Takano, Y., Mixed integer second-order cone programming formulations for variable selection in linear regression, Eur. J. Oper. Res., 247, 3, 721-731 (2015) · Zbl 1346.90616
[6] Sato, T.; Takano, Y.; Miyashiro, R.; Yoshise, A., Feature subset selection for logistic regression via mixed integer optimization, Comput. Optim. Appl., 64, 3, 865-880 (2016) · Zbl 1352.90068
[7] Rolfs, B.; Rajaratnam, B.; Guillot, D.; Wong, I.; Maleki, A.; Pereira, F.; Burges, CJC; Bottou, L.; Weinberger, KQ, Iterative thresholding algorithm for sparse inverse covariance estimation, Advances in Neural Information Processing Systems 25, 1574-1582 (2012), New York: Curran Associates, Inc., New York
[8] Friedman, J.; Hastie, T.; Tibshirani, R., Sparse inverse covariance estimation with the graphical Lasso, Biostatistics, 9, 3, 432-441 (2008) · Zbl 1143.62076
[9] Teng, Y.; Yang, L.; Yu, B.; Song, X., A penalty palm method for sparse portfolio selection problems, Optim. Methods Softw., 32, 1, 126-147 (2017) · Zbl 1366.91162
[10] Carreira-Perpinan, M.A., Idelbayev, Y.: “Learning-compression” algorithms for neural net pruning. In: 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 8532-8541 (2018)
[11] Jin, X., Yuan, X., Feng, J., Yan, S.: Training skinny deep neural networks with iterative hard thresholding methods (2016)
[12] Bienstock, D., Computational study of a family of mixed-integer quadratic programming problems, Math. Program., 74, 2, 121-140 (1996) · Zbl 0855.90090
[13] Natarajan, BK, Sparse approximate solutions to linear systems, SIAM J. Comput., 24, 2, 227-234 (1995) · Zbl 0827.68054
[14] Tibshirani, R., Regression shrinkage and selection via the Lasso, J. Roy. Stat. Soc.: Ser. B (Methodol.), 58, 1, 267-288 (1996) · Zbl 0850.62538
[15] Chartrand, R., Exact reconstruction of sparse signals via nonconvex minimization, IEEE Signal Process. Lett., 14, 10, 707-710 (2007)
[16] Chen, X.; Xu, F.; Ye, Y., Lower bound theory of nonzero entries in solutions of \(\ell_2-\ell_p\) minimization, SIAM J. Sci. Comput., 32, 5, 2832-2852 (2010) · Zbl 1242.90174
[17] Beck, A.; Eldar, Y., Sparsity constrained nonlinear optimization: Optimality conditions and algorithms, SIAM J. Optim., 23, 3, 1480-1509 (2013) · Zbl 1295.90051
[18] Lu, Z.; Zhang, Y., Sparse approximation via penalty decomposition methods, SIAM J. Optim., 23, 4, 2448-2478 (2013) · Zbl 1295.90056
[19] Bertsekas, DP, Nonlinear programming, J. Oper. Res. Soc., 48, 3, 334-334 (1997)
[20] Jörnsten, K., Näsberg, M., Smeds, P.: Variable Splitting: A New Lagrangean Relaxation Approach to Some Mathematical Programming Models. LiTH MAT R.: Matematiska Institutionen. University of Linköping, Department of Mathematics (1985)
[21] Bertsekas, DP; Tsitsiklis, JN, Parallel and Distributed Computation: Numerical Methods (1989), New Jersey: Prentice hall Englewood Cliffs, New Jersey · Zbl 0743.65107
[22] Beck, A.; Tetruashvili, L., On the convergence of block coordinate descent type methods, SIAM J. Optim., 23, 4, 2037-2060 (2013) · Zbl 1297.90113
[23] Fasano, G.; Liuzzi, G.; Lucidi, S.; Rinaldi, F., A linesearch-based derivative-free approach for nonsmooth constrained optimization, SIAM J. Optim., 24, 3, 959-992 (2014) · Zbl 1302.90207
[24] Liuzzi, G.; Lucidi, S.; Piccialli, V., Exploiting derivative-free local searches in direct-type algorithms for global optimization, Comput. Optim. Appl., 65, 2, 449-475 (2016) · Zbl 1370.90194
[25] Lucidi, S.; Sciandrone, M., A derivative-free algorithm for bound constrained optimization, Comput. Optim. Appl., 21, 2, 119-142 (2002) · Zbl 0988.90033
[26] Hastie, T.; Tibshirani, R.; Friedman, J., The Elements of Statistical Learning: Data Mining, Inference, and Prediction (2009), New York: Springer Science & Business Media, New York · Zbl 1273.62005
[27] Weston, J.; Elisseeff, A.; Schölkopf, B.; Tipping, M., Use of the zero-norm with linear models and kernel methods, J. Mach. Learn. Res., 3, Mar, 1439-1461 (2003) · Zbl 1102.68605
[28] Bach, F.; Jenatton, R.; Mairal, J.; Obozinski, G., Optimization with sparsity-inducing penalties, Found. Trends Mach. Learn., 4, 1, 1-106 (2012) · Zbl 06064248
[29] Dua, D., Graff, C.: UCI machine learning repository (2017). http://archive.ics.uci.edu/ml
[30] Virtanen, P.; Gommers, R.; Oliphant, TE, SciPy 1.0 Contributors: SciPy 1.0: fundamental algorithms for scientific computing in python, Nat. Methods, 17, 261-272 (2020)
[31] Dolan, ED; Moré, JJ, Benchmarking optimization software with performance profiles, Math. Program., 91, 2, 201-213 (2002) · Zbl 1049.90004
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.