On nondegenerate M-stationary points for sparsity constrained nonlinear optimization

DOI10.1007/S10898-021-01070-7zbMATH Open1486.90191arXiv1912.04087OpenAlexW3193729844MaRDI QIDQ2114575FDOQ2114575

Yanyan Li

Publication date: 15 March 2022

Published in: Journal of Global Optimization (Search for Journal in Brave)

Abstract: 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. (2016). 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.

Full work available at URL: https://arxiv.org/abs/1912.04087

zbMATH Keywords

genericityMorse theorysaddle pointsnondegeneracysparsity constraintM-stationarityM-index

Mathematics Subject Classification ID

Nonlinear programming (90C30)

Cites Work

• Title not available (Why is that?)
• Variational Analysis
• Compressed sensing
• Sparsity constrained nonlinear optimization: optimality conditions and algorithms
• Morse Theory. (AM-51)
• Differential Topology
• Second-order optimality conditions and improved convergence results for regularization methods for cardinality-constrained optimization problems
• On solutions of sparsity constrained optimization
• The first-order necessary conditions for sparsity constrained optimization
• On the minimization over sparse symmetric sets: projections, optimality conditions, and algorithms
• Sparse Approximation via Penalty Decomposition Methods
• Title not available (Why is that?)
• Title not available (Why is that?)
• Nonlinear optimization in finite dimensions. Morse theory, Chebyshev approximation, transversality, flows, parametric aspects
• Constraint qualifications and optimality conditions for optimization problems with cardinality constraints
• Mathematical programs with vanishing constraints: critical point theory
• Topological aspects of nonsmooth optimization.
• Mathematical Programs with Cardinality Constraints: Reformulation by Complementarity-Type Conditions and a Regularization Method
• MPCC: Critical Point Theory
• Simplicial homotopy theory
• Optimality conditions for sparse nonlinear programming
• Proximal Mapping for Symmetric Penalty and Sparsity

Cited In (4)

• Inexact penalty decomposition methods for optimization problems with geometric constraints
• Title not available (Why is that?)
• Critical point theory for sparse recovery
• Optimality conditions for mathematical programs with orthogonality type constraints

   Recommendations

• Lifted stationary points of sparse optimization with complementarity constraints 👍 👎
• Sparsity constrained nonlinear optimization: optimality conditions and algorithms 👍 👎
• Nonsmooth sparsity constrained optimization problems: optimality conditions 👍 👎
• Several Classes of Stationary Points for Rank Regularized Minimization Problems 👍 👎
• Nonsmooth Optimization Method and Sparsity 👍 👎
• On the complexity of finding stationary points of nonconvex quadratic programs 👍 👎
• On solutions of sparsity constrained optimization 👍 👎
• Sparsity in convex quadratic programming with interior point methods 👍 👎
• Optimality conditions for sparse nonlinear programming 👍 👎
• An efficient algorithm for non-convex sparse optimization 👍 👎

This page was built for publication: On nondegenerate M-stationary points for sparsity constrained nonlinear optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2114575)