×

On nondegenerate M-stationary points for sparsity constrained nonlinear optimization. (English) Zbl 1486.90191

Summary: We study sparsity constrained nonlinear optimization (SCNO) from a topological point of view. Special focus will be on M-stationary points from [O. P. Burdakov et al., SIAM J. Optim. 26, No. 1, 397–425 (2016; Zbl 1332.90220)], also introduced as \(N^C\)-stationary points in [L.-L. Pan et al., J. Oper. Res. Soc. China 3, No. 4, 421–439 (2015; Zbl 1332.90216)]. 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.

MSC:

90C30 Nonlinear programming
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Beck, A.; Eldar, YC, Sparsity constrained nonlinear optimization: optimality conditions and algorithms, SIAM J. Optim., 24, 1480-1509 (2013) · Zbl 1295.90051
[2] Beck, A.; Hallak, N., On the minimization over sparse symmetric sets: projections, optimality conditions, and algorithms, Math. Oper. Res., 41, 196-223 (2016) · Zbl 1334.90129
[3] Beck, A.; Hallak, N., Proximal mapping for symmetric penalty and sparsity, SIAM J. Optim., 28, 496-527 (2018) · Zbl 1390.90438
[4] 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-410 (2018) · Zbl 1394.90475
[5] 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-425 (2016) · Zbl 1332.90220
[6] Červinka, M.; Kanzow, C.; Schwartz, A., Constraint qualifications and optimality conditions for optimization problems with cardinality constraints, Math. Progr., 160, 353-377 (2016) · Zbl 1356.90146
[7] Donoho, DL, Compressed sensing, IEEE Trans. Inf. Theory, 52, 1289-1306 (2006) · Zbl 1288.94016
[8] Dorsch, D.; Shikhman, V.; Stein, O., Mathematical programs with vanishing constraints: critical point theory, J. Glob. Optim., 52, 591-605 (2012) · Zbl 1254.90224
[9] Goerss, PG; Jardine, JF, Simplicial Homotopy Theory (2009), Basel: Birkhäuser, Basel · Zbl 1195.55001
[10] Goresky, M.; MacPherson, R., Stratified Morse Theory (1988), New York: Springer, New York · Zbl 0639.14012
[11] Hirsch, MW, Differential Topology (1976), Berlin-Heidelberg-New York: Springer, Berlin-Heidelberg-New York · Zbl 0356.57001
[12] Jongen, H.T.: On non-convex optimization. Dissertation, University of Twente, The Netherlands (1977)
[13] Jongen, HT; Jonker, P.; Twilt, F., Nonlinear Optimization in Finite Dimensions (2000), Dordrecht: Kluwer Academic Publishers, Dordrecht · Zbl 0985.90083
[14] Jongen, HT; Shikhman, V.; Ruckmann, J-J, MPCC: critical point theory, SIAM J. Optim., 20, 473-484 (2009) · Zbl 1229.90139
[15] Lämmel, S., Shikhman, V.: Critical point theory for sparse recovery. arXiv:2002.10913 (2020)
[16] Li, X.; Song, W., The first-order necessary conditions for sparsity constrained optimization, J. Oper. Res. Soc. China, 3, 521-535 (2015) · Zbl 1332.90209
[17] Lu, Z.; Zhang, Y., Sparse approximation via penalty decomposition methods, SIAM J. Optim., 23, 2448-2478 (2013) · Zbl 1295.90056
[18] Milnor, J., Morse Theory (1963), Princeton: Princeton University Press, Princeton · Zbl 0108.10401
[19] Pan, L.; Xiu, N.; Fan, J., Optimality conditions for sparse nonlinear programming, Sci. China Math., 5, 1-18 (2017) · Zbl 1365.90220
[20] Pan, L.; Xiu, N.; Zhou, S., On solutions of sparsity constrained optimization, J. Oper. Res. Soc. China, 3, 421-439 (2015) · Zbl 1332.90216
[21] Rockafellar, R.; Wets, R., Variational Analysis (1998), Berlin: Springer, Berlin · Zbl 0888.49001
[22] Shechtman, Y.; Eldar, YC; Szameit, A.; Segev, M., Sparsity-based sub-wavelength imaging with partially spatially incoherent light via quadratic compressed sensing, Opt. Express, 19, 14807-14822 (2011)
[23] Shikhman, V., Topological Aspects of Nonsmooth Optimization (2012), New York: Springer, New York · Zbl 1234.90001
[24] Spanier, EH, Algebraic Topology (1966), New York: McGraw-Hill Book Company, New York · Zbl 0145.43303
[25] Tibshirani, R., Regression shrinkage and selection via the lasso, J. R. Stat. Soc. Ser. B, 58, 267-288 (1996) · Zbl 0850.62538
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.