{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,10]],"date-time":"2026-01-10T01:03:43Z","timestamp":1768007023883,"version":"3.49.0"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2021,8,23]],"date-time":"2021-08-23T00:00:00Z","timestamp":1629676800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,8,23]],"date-time":"2021-08-23T00:00:00Z","timestamp":1629676800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100009117","name":"Technische Universit\u00e4t Chemnitz","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100009117","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Glob Optim"],"published-print":{"date-parts":[[2022,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study sparsity constrained nonlinear optimization (SCNO) from a topological point of view. Special focus will be on M-stationary points from Burdakov et al. (SIAM J Optim 26:397\u2013425, 2016), also introduced as<jats:inline-formula><jats:alternatives><jats:tex-math>$$N^C$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msup><mml:mi>N<\/mml:mi><mml:mi>C<\/mml:mi><\/mml:msup><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-stationary points in Pan et al. (J Oper Res Soc China 3:421\u2013439, 2015). We introduce nondegenerate M-stationary points and define their M-index. We show that all M-stationary points are generically nondegenerate. In particular, the sparsity constraint is active at all local minimizers of a generic SCNO. Some relations to other stationarity concepts, such as S-stationarity, basic feasibility, and CW-minimality, are discussed in detail. By doing so, the issues of instability and degeneracy of points due to different stationarity concepts are highlighted. The concept of M-stationarity allows to adequately describe the global structure of SCNO along the lines of Morse theory. For that, we study topological changes of lower level sets while passing an M-stationary point. As novelty for SCNO, multiple cells of dimension equal to the M-index are needed to be attached. This intriguing fact is in strong contrast with other optimization problems considered before, where just one cell suffices. As a consequence, we derive a Morse relation for SCNO, which relates the numbers of local minimizers and M-stationary points of M-index equal to one. The appearance of such saddle points cannot be thus neglected from the perspective of global optimization. Due to the multiplicity phenomenon in cell-attachment, a saddle point may lead to more than two different local minimizers. We conclude that the relatively involved structure of saddle points is the source of well-known difficulty if solving SCNO to global optimality.<\/jats:p>","DOI":"10.1007\/s10898-021-01070-7","type":"journal-article","created":{"date-parts":[[2021,8,23]],"date-time":"2021-08-23T02:02:21Z","timestamp":1629684141000},"page":"219-242","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["On nondegenerate M-stationary points for sparsity constrained nonlinear optimization"],"prefix":"10.1007","volume":"82","author":[{"given":"S.","family":"L\u00e4mmel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8031-6069","authenticated-orcid":false,"given":"V.","family":"Shikhman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,8,23]]},"reference":[{"key":"1070_CR1","doi-asserted-by":"publisher","first-page":"1480","DOI":"10.1137\/120869778","volume":"24","author":"A Beck","year":"2013","unstructured":"Beck, A., Eldar, Y.C.: Sparsity constrained nonlinear optimization: optimality conditions and algorithms. SIAM J. Optim. 24, 1480\u20131509 (2013)","journal-title":"SIAM J. Optim."},{"key":"1070_CR2","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1287\/moor.2015.0722","volume":"41","author":"A Beck","year":"2016","unstructured":"Beck, A., Hallak, N.: On the minimization over sparse symmetric sets: projections, optimality conditions, and algorithms. Math. Oper. Res. 41, 196\u2013223 (2016)","journal-title":"Math. Oper. Res."},{"key":"1070_CR3","doi-asserted-by":"publisher","first-page":"496","DOI":"10.1137\/17M1116544","volume":"28","author":"A Beck","year":"2018","unstructured":"Beck, A., Hallak, N.: Proximal mapping for symmetric penalty and sparsity. SIAM J. Optim. 28, 496\u2013527 (2018)","journal-title":"SIAM J. Optim."},{"key":"1070_CR4","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1007\/s10957-018-1320-7","volume":"178","author":"M Bucher","year":"2018","unstructured":"Bucher, M., Schwartz, A.: Second-order optimality conditions and improved convergence results for regularization methods for cardinality-constrained optimization problems. J. Optim. Theory Appl. 178, 383\u2013410 (2018)","journal-title":"J. Optim. Theory Appl."},{"key":"1070_CR5","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1137\/140978077","volume":"26","author":"O Burdakov","year":"2016","unstructured":"Burdakov, O., Kanzow, C., Schwartz, A.: Mathematical programs with cardinality constraints: reformulation by complementarity-type conditions and a regularization method. SIAM J. Optim. 26, 397\u2013425 (2016)","journal-title":"SIAM J. Optim."},{"key":"1070_CR6","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/s10107-016-0986-6","volume":"160","author":"M \u010cervinka","year":"2016","unstructured":"\u010cervinka, M., Kanzow, C., Schwartz, A.: Constraint qualifications and optimality conditions for optimization problems with cardinality constraints. Math. Progr. 160, 353\u2013377 (2016)","journal-title":"Math. Progr."},{"key":"1070_CR7","doi-asserted-by":"publisher","first-page":"1289","DOI":"10.1109\/TIT.2006.871582","volume":"52","author":"DL Donoho","year":"2006","unstructured":"Donoho, D.L.: Compressed sensing. IEEE Trans. Inf. Theory 52, 1289\u20131306 (2006)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1070_CR8","doi-asserted-by":"publisher","first-page":"591","DOI":"10.1007\/s10898-011-9805-z","volume":"52","author":"D Dorsch","year":"2012","unstructured":"Dorsch, D., Shikhman, V., Stein, O.: Mathematical programs with vanishing constraints: critical point theory. J. Glob. Optim. 52, 591\u2013605 (2012)","journal-title":"J. Glob. Optim."},{"key":"1070_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0346-0189-4","volume-title":"Simplicial Homotopy Theory","author":"PG Goerss","year":"2009","unstructured":"Goerss, P.G., Jardine, J.F.: Simplicial Homotopy Theory. Birkh\u00e4user, Basel (2009)"},{"key":"1070_CR10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-71714-7","volume-title":"Stratified Morse Theory","author":"M Goresky","year":"1988","unstructured":"Goresky, M., MacPherson, R.: Stratified Morse Theory. Springer, New York (1988)"},{"key":"1070_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-9449-5","volume-title":"Differential Topology","author":"MW Hirsch","year":"1976","unstructured":"Hirsch, M.W.: Differential Topology. Springer, Berlin-Heidelberg-New York (1976)"},{"key":"1070_CR12","unstructured":"Jongen, H.T.: On non-convex optimization. Dissertation, University of Twente, The Netherlands (1977)"},{"key":"1070_CR13","volume-title":"Nonlinear Optimization in Finite Dimensions","author":"HT Jongen","year":"2000","unstructured":"Jongen, H.T., Jonker, P., Twilt, F.: Nonlinear Optimization in Finite Dimensions. Kluwer Academic Publishers, Dordrecht (2000)"},{"key":"1070_CR14","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1137\/080733693","volume":"20","author":"HT Jongen","year":"2009","unstructured":"Jongen, H.T., Shikhman, V., Ruckmann, J.-J.: MPCC: critical point theory. SIAM J. Optim. 20, 473\u2013484 (2009)","journal-title":"SIAM J. Optim."},{"key":"1070_CR15","doi-asserted-by":"crossref","unstructured":"L\u00e4mmel, S., Shikhman, V.: Critical point theory for sparse recovery. arXiv:2002.10913 (2020)","DOI":"10.1080\/02331934.2021.1981317"},{"key":"1070_CR16","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1007\/s40305-015-0107-x","volume":"3","author":"X Li","year":"2015","unstructured":"Li, X., Song, W.: The first-order necessary conditions for sparsity constrained optimization. J. Oper. Res. Soc. China 3, 521\u2013535 (2015)","journal-title":"J. Oper. Res. Soc. China"},{"key":"1070_CR17","doi-asserted-by":"publisher","first-page":"2448","DOI":"10.1137\/100808071","volume":"23","author":"Z Lu","year":"2013","unstructured":"Lu, Z., Zhang, Y.: Sparse approximation via penalty decomposition methods. SIAM J. Optim. 23, 2448\u20132478 (2013)","journal-title":"SIAM J. Optim."},{"key":"1070_CR18","doi-asserted-by":"publisher","DOI":"10.1515\/9781400881802","volume-title":"Morse Theory","author":"J Milnor","year":"1963","unstructured":"Milnor, J.: Morse Theory. Princeton University Press, Princeton (1963)"},{"key":"1070_CR19","first-page":"1","volume":"5","author":"L Pan","year":"2017","unstructured":"Pan, L., Xiu, N., Fan, J.: Optimality conditions for sparse nonlinear programming. Sci. China Math. 5, 1\u201318 (2017)","journal-title":"Sci. China Math."},{"key":"1070_CR20","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1007\/s40305-015-0101-3","volume":"3","author":"L Pan","year":"2015","unstructured":"Pan, L., Xiu, N., Zhou, S.: On solutions of sparsity constrained optimization. J. Oper. Res. Soc. China 3, 421\u2013439 (2015)","journal-title":"J. Oper. Res. Soc. China"},{"key":"1070_CR21","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02431-3","volume-title":"Variational Analysis","author":"R Rockafellar","year":"1998","unstructured":"Rockafellar, R., Wets, R.: Variational Analysis. Springer, Berlin (1998)"},{"key":"1070_CR22","doi-asserted-by":"publisher","first-page":"14807","DOI":"10.1364\/OE.19.014807","volume":"19","author":"Y Shechtman","year":"2011","unstructured":"Shechtman, Y., Eldar, Y.C., Szameit, A., Segev, M.: Sparsity-based sub-wavelength imaging with partially spatially incoherent light via quadratic compressed sensing. Opt. Express 19, 14807\u201314822 (2011)","journal-title":"Opt. Express"},{"key":"1070_CR23","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-1897-9","volume-title":"Topological Aspects of Nonsmooth Optimization","author":"V Shikhman","year":"2012","unstructured":"Shikhman, V.: Topological Aspects of Nonsmooth Optimization. Springer, New York (2012)"},{"key":"1070_CR24","volume-title":"Algebraic Topology","author":"EH Spanier","year":"1966","unstructured":"Spanier, E.H.: Algebraic Topology. McGraw-Hill Book Company, New York (1966)"},{"key":"1070_CR25","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1111\/j.2517-6161.1996.tb02080.x","volume":"58","author":"R Tibshirani","year":"1996","unstructured":"Tibshirani, R.: Regression shrinkage and selection via the lasso. J. R. Stat. Soc. Ser. B 58, 267\u2013288 (1996)","journal-title":"J. R. Stat. Soc. Ser. B"}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-021-01070-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10898-021-01070-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-021-01070-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T01:54:06Z","timestamp":1725674046000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10898-021-01070-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,23]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,2]]}},"alternative-id":["1070"],"URL":"https:\/\/doi.org\/10.1007\/s10898-021-01070-7","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"value":"0925-5001","type":"print"},{"value":"1573-2916","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,8,23]]},"assertion":[{"value":"5 June 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 August 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 August 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}