On nondegenerate M-stationary points for sparsity constrained nonlinear optimization

Lämmel, S.; Shikhman, V. Article — Published Version On nondegenerate M-stationary points for sparsity constrained nonlinear optimization Journal of Global Optimization Provided in Cooperation with: Springer Nature Suggested Citation: Lämmel, S.; Shikhman, V. (2021) : On nondegenerate M-stationary points for sparsity constrained nonlinear optimization, Journal of Global Optimization, ISSN 1573-2916, Springer US, New York, NY, Vol. 82, Iss. 2, pp. 219-242, https://doi.org/10.1007/s10898-021-01070-7 This Version is available at: https://hdl.handle.net/10419/287145 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by/4.0/ Journal of Global Optimization (2022) 82:219–242 https://doi.org/10.1007/s10898-021-01070-7 On nondegenerate M-stationary points for sparsity constrained nonlinear optimization S. Lämmel1 ·V. Shikhman1 Received: 5 June 2020 / Accepted: 5 August 2021 / Published online: 23 August 2021 © The Author(s) 2021 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. (SIAM J Optim 26:397–425, 2016), also introduced as NC-stationary points in Pan et al. (J Oper Res Soc China 3:421–439, 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. Keywords Sparsity constraint ·M-stationarity, M-index ·Nondegeneracy ·Genericity · Morse theory ·Saddle points BV. Shikhman vladimir[email protected] S. Lämmel [email protected] 1Department of Mathematics, Chemnitz University of Technology, Reichenhainer Str. 41, 09126 Chemnitz, Germany 123 220 Journal of Global Optimization (2022) 82:219–242 1 Introduction We consider the sparsity constrained nonlinear optimization: SCNO: min x∈Rnf(x)s. t. x0≤s, where the so-called 0"norm" counts non-zero entries of x: x0=|{i∈{1,...,n}|xi= 0}| , the objective function f∈C2(Rn,R)is twice continuously differentiable, and s∈ {0,1,...,n−1}is an integer. The difficulty of solving SCNO comes from the combinatorial nature of the sparsity constraint x0≤s. The requirement of sparsity is however motivated by various applications, such as compressed sensing, model selection, image processing etc. We refer e.g. to [7,25], and [22] for further details on the relevant applications. In the seminal paper [1], necessary optimality conditions for SCNO have been stated. Namely, the notions of basic feasibility (BF-vector), L-stationarity and CW-minimality have been introduced and studied there. Note that the formulation of L-stationarity mimics the techniques from convex optimization by using the orthogonal projection on the SCNO feasible set. The notion of CW-minimum incorporates the coordinate-wise optimality along the axes. Based on both stationarity concepts, algorithms that find points satisfying these conditions have been developed. Those are the iterative hard thresholding method, as well as the greedy and partial sparse-simplex methods. In a series of subsequent papers [2,3] elaborated the algorithmic approach for SCNO which is based on L-stationarity and CW-minimality. Another line of research started with [5], where additionally smooth equality and inequality constraints have been incorporated into SCNO. For that, the authors coin the new term of mathematical programs with cardinality constraints (MPCC). The key idea in [5] is to provide a mixed-integer formulation whose standard relaxation still has the same solutions as MPCC. For the relaxation the notion of S-stationary points is proposed. S-stationarity corresponds to the standard Karush–Kuhn–Tucker condition for the relaxed program. The techniques applied follow mainly those for mathematical programs with complementarity constraints. In particular, an appropriate regularization method for solving MPCC is suggested. The latter is proved to converge towards so-called M-stationary points. M-stationarity corresponds to the standard Karush–Kuhn–Tucker condition of the tightened program, where zero entries of an MPCC feasible point remain locally vanishing. Further research in this direction is presented in a series of subsequent papers [4,6]. Finally, we would like to mention stationarity concepts for SCNO based on the normal cones of the sparsity constrained feasible set. In [20], the Bouligand and Clarke normal cones of the SCNO feasible set are used to derive NB-andNC-stationarity, respectively. Corresponding second-order necessary and sufficient optimality conditions are stated there. These findings were generalized for MPCC in [19]. In [16], the Fréchet and Mordukhovich normal cones of the SCNO feasible set are used to derive  N-andN-stationarity, respectively. These notions were generalized for the intersection of the sparsity constrained feasible set with a polyhedral set. In [17], a penalty decomposition method essentially based on the notion of N-stationarity is proposed for solving MPCC under the Robinson’s constraint qualification. The goal of this paper is the study of SCNO from a topological point of view. The topological approach to optimization has been pioneered by [12,13] for nonlinear programming problems, and successfully developed for mathematical programs with complementarity constraints, mathematical problems with vanishing constraints, general semi-infinite pro- 123 Journal of Global Optimization (2022) 82:219–242 221 gramming, bilevel optimization, semi-definite programming, disjunctive programming etc., see e.g. [23] and references therein. The main idea of the topological approach is to identify stationary points which roughly speaking induce the global structure of the underlying optimization problem. The stationary points include minimizers, but also all kinds of saddle points—just in analogy to the unconstrained case. It turns out that for SCNO the concept of M-stationarity from [5] —coinciding with NC-stationarity from [20]—is the adequate stationarity concept at least from the topological perspective. We outline our main findings and results: 1. We introduce nondegenerate M-stationary points along with their associated M-indices. The latter subsume as usual the quadratic part—the number of negative eigenvalues of the objective’s Hessian restricted to non-vanishing variables. As novelty, the sparsity constraint provides an addition to the M-index, namely, the difference between the bound and the current number of non-zero variables at a nondegenerate M-stationary point. We prove that all M-stationary points are generically nondegenerate. In particular, it follows that all local minimizers of SCNO are nondegenerate with vanishing M-index, hence, the sparsity constraint is active. Note that M-stationary points with non-vanishing M- index correspond to saddle points. The local structure of SCNO around a nondegenerate M-stationary point is fully described just by its M-index, at least up to a differentiable change of coordinates. 2. We thoroughly discuss the relation of M-stationarity to S-stationarity, basic feasibility, and CW-minimality for SCNO. It turns out that nondegenerate M-stationary points may cause degeneracies of S-stationary points viewed as Karush–Kuhn–Tucker-points for the relaxed problem. Moreover, even under the cardinality constrained second-order sufficient optimality condition from [4] assumed to hold at an S-stationary point, the corresponding M-stationary point does not need to be a nondegenerate local minimizer for SCNO. As for CW-minima, we show that they are not stable with respect to data perturbations in SCNO. After an arbitrarily small C2-perturbation of fa locally unique CW-minimum may bifurcate into multiple CW-minima. More importantly, this bifurcation unavoidably causes the emergence of M-stationary points, being different from the CW-minima. Despite of this instability phenomenon, if a BF-vector and, hence, CW-minimum, happens to be nondegenerate as an M-stationary point, then the sparsity constraint is necessarily active. 3. We use the concept of M-stationarity in order to describe the global structure of SCNO. To this aim the study of topological properties of its lower level sets is undertaken. As in the standard Morse theory, see e. g. [10,18], we focus on the topological changes of the lower level sets as their levels vary. Appropriate versions of deformation and cellattachment theorems are shown to hold for SCNO. Whereas the deformation is standard, the cell-attachment reveals an essentially new phenomenon not observed in nonsmooth optimization before. In SCNO, multiple cells of the same dimension need to be attached, see Theorem 5. To determine the number of these attached cells turns out to constitute a challenging combinatorial problem from algebraic topology, see Lemma 1. 4. As a consequence of proposed Morse theory, 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. As novelty for SCNO, a saddle point may lead to more than two different local minimizers. This is in strong contrast with other nonsmooth optimization problems studied before, see e.g. [23], where a saddle point leads to at most two of 123 222 Journal of Global Optimization (2022) 82:219–242 them. We conclude that the relatively involved structure of saddle points is the source of well-known difficulty if solving SCNO to global optimality. The paper is organized as follows. In Sect. 2we discuss the notion of M-stationarity for SCNO. Section 3is devoted to the relation of M-stationarity to other stationarity concepts from the literature. In Sect. 4the global structure of SCNO is described within the scope of Morse theory. Our notation is standard. The cardinality of a finite set Sis denoted by |S|.Thendimensional Euclidean space is denoted by Rnwith the coordinate vectors ei,i=1,...,n. For J⊂{1,...,n}we denote by conv ej,j∈Jand span ej,j∈Jthe convex and linear combination of the coordinate vectors ej,j∈J, respectively. Given a twice continuously differentiable function f:Rn→R,∇fdenotes its gradient, and D2fstands for its Hessian. 2 M-stationarity For 0 ≤k≤nwe use the notation Rn,k=x∈Rn| x0≤k. Using the latter, the feasible set of SCNO can be written as Rn,s=x∈Rn| x0≤s. For a feasible point x∈Rn,swe define the following complementary index sets: I0(x)={i∈{1,...,n}|xi=0},I1(x)={i∈{1,...,n}|xi= 0}. Without loss of generality, we assume throughout the whole paper that at the particular point of interest ¯x∈Rn,swith ¯x0=kit holds: I0(¯x)={1,...,n−k},I1(¯x)={n−k+1,...,n}. Using this convention, the following local description of SCNO feasible set can be deduced. Let ¯x∈Rn,sbe a feasible point for SCNO with ¯x0=k. Then, there exist neighborhoods U¯xand V0of ¯xand 0, respectively, such that under the linear coordinate transformation (x)=x−¯xwe have locally: Rn,s∩U¯x=Rn−k,s−k×Rk∩V0,(¯x)=0.(1) Definition 1 (M-stationarity, [5])A feasible point ¯x∈Rn,sis called M-stationary for SCNO if ∂f ∂xi (¯x)=0foralli∈I1(¯x). Obviously, a local minimizer of SCNO is an M-stationary point. Definition 2 (Nondegenerate M-stationarity) An M-stationary point ¯x∈Rn,swith ¯x0=k is called nondegenerate if the following conditions hold: ND1: if k<sthen ∂f ∂xi (¯x)= 0foralli∈I0(¯x), ND2: the matrix ∂2f ∂xi∂xj (¯x)i,j∈I1(¯x) is nonsingular. 123 Journal of Global Optimization (2022) 82:219–242 223 Otherwise, we call ¯xdegenerate. Definition 3 (M-Index) Let ¯x∈Rn,sbe a nondegenerate M-stationary point with ¯x0= k. The number of negative eigenvalues of the matrix ∂2f ∂xi∂xj (¯x)i,j∈I1(¯x) is called its quadratic index (QI). The number s−k+QI is called the M-index of ¯x. Theorem 1 (Morse-Lemma for SCNO) Suppose that ¯x is a nondegenerate M-stationary point for SCNO with ¯x0=k and quadratic index QI. Then, there exist neighborhoods U¯xand V0of ¯x and 0, respectively, and a local C1-coordinate system :U¯x→V0of Rnaround ¯x such that: f◦−1(y)=f(¯x)+ n−k  i=1 yi+ n  j=n−k+1 ±y2 j,(2) where y ∈Rn−k,s−k×Rk. Moreover, there are exactly Q I negative squares in (2). Proof Without loss of generality, we may assume f(¯x)=0. By using from (1), we put ¯ f:= f◦−1on the set Rn−k,s−k×Rk∩V0. At the origin we have: (i) if k<sthen ∂¯ f ∂yi = 0foralli=1,...,n−k, (ii) ∂¯ f ∂yi =0foralli=n−k+1,...,n, (iii) the matrix ∂2¯ f ∂yi∂yji,j=n−k+1,...,n is nonsingular. We denote ¯ fby fagain. Under the following coordinate transformations the set Rn−k,s−k× Rkwill be equivariantly transformed in itself. We put y=Yn−k,Yk,whereYn−k= (y1,...,yn−k)and Yk=(yn−k+1,...,yn). It holds: fYn−k,Yk=1 0 d dt ftYn−k,Ykdt +f0,Yk= n−k  i=1 yidi(y)+f0,Yk, where di(y)=1 0 ∂f ∂yitYn−k,Ykdt,i=1,...,n−k. Note that di∈C1,i=1,...,n−k. Due to (ii)-(iii), we may apply the standard Morse lemma on the C2-function f0,Ykwithout affecting the coordinates Yn−k, see e.g. [13]. The corresponding coordinate transformation is of class C1. Denoting the transformed functions again by fand di,weobtain f(y)= n−k  i=1 yidi(y)+ n  j=n−k+1 ±y2 j. In case k=s, we need to consider flocally around the origin on the set Rn−k,s−k×Rk=Rn−k,0×Rk={0}n−k×Rk. Hence, yi=0fori=1,...,n−k, and we immediately obtain the representation (2). 123 224 Journal of Global Optimization (2022) 82:219–242 In case k<s, (i) provides that di(0)=∂f ∂yi (0)= 0, i=1,...,n−k. Hence, we may take yidi(y), i=1,...,n−k,yj,j=n−k+1,...,n as new local C1-coordinates by a straightforward application of the inverse function theorem. Denoting the transformed function again by f,weobtain(2). Here, the coordinate transformation is understood as the composition of all previous ones.  Proposition 1 (Nondegenerate minimizers) Let ¯x be a nondegenerate M-stationary point for SCNO. Then, ¯x is a local minimizer for SCNO if and only if its M-index vanishes. Proof Let ¯xbe a nondegenerate M-stationary point for SCNO. The application of Morse Lemma from Theorem 1says that there exist neighborhoods U¯xand V0of ¯xand 0, respectively, and a local C1-coordinate system :U¯x→V0of Rnaround ¯xsuch that: f◦−1(y)=f(¯x)+ n−k  i=1 yi+ n  j=n−k+1 ±y2 j,(3) where y∈Rn−k,s−k×Rk. Therefore, ¯xis a local minimizer for SCNO if and only if 0 is a local minimizer of f◦−1on the set Rn−k,s−k×Rk∩V0. If the M-index of ¯xvanishes, we have k=sand QI =0, and (3) reads as f◦−1(y)=f(¯x)+ n  j=n−s+1 y2 j,(4) where y∈{0}n−s×Rs. Thus, 0 is a local minimizer for (4). Vice versa, if 0 is a local minimizer for (3), then obviously k=sand QI =0, hence, the M-index of ¯xvanishes.  Let C2(Rn,R)be endowed with the strong (or Whitney) C2-topology, denoted by Ck s(see e.g. [11]). The Ck s-topology is generated by allowing perturbations of the functions, their gradients and Hessians, which are controlled by means of continuous positive functions. We say that a set is C2 s-generic if it contains a countable intersection of C2 s-open and -dense subsets. Since C2(Rn,R)endowed with the C2 s-topology is a Baire space, generic sets are in particular dense. Theorem 2 (Genericity for SCNO) Let F⊂C2(Rn,R)denote the subset of objective functions in SCNO for which each M-stationary point is nondegenerate. Then, Fis C2 s-open and -dense. Proof Let us fix a number of non-zero entries k∈{0,...,s}, an index set of knon-zero entries D⊂{1,...,n},i.e.|D|=k, an index subset of zero entries E⊂{1,...,n}\D, and a rank r∈{0,...,k}. For this choice we consider the set k,D,E,rof xsuch that the following conditions are satisfied: (m1) xi= 0foralli∈D,andxi=0foralli∈{1,...,n}\D, (m2) ∂f ∂xi (x)=0foralli∈D, (m3) if k<sthen ∂f ∂xi (x)=0foralli∈E, (m4) the matrix ∂2f ∂xi∂xj (x)i,j∈D has rank r. 123 Journal of Global Optimization (2022) 82:219–242 225 Note that (m1) refers to feasibility, (m2) to M-stationarity, and (m3)-(m4) describe possible violations of ND1-ND2, respectively. Now, it suffices to show that all k,D,E,rare generically empty whenever Eis nonempty or the rank ris less than k. By setting I1(x)=Dand I0(x)={1,...,n}\D, this would mean, respectively, that at least one of the derivatives ∂f ∂xi (x)vanishes for i∈E⊂I0(x)in ND1 if k<s, or the matrix ∂2f ∂xi∂xj (x)i,j∈I1(x) is singular in ND2. In fact, the available degrees of freedom of the variables involved in each k,D,E,rare n. The loss of freedom caused by (m1) is n−k, and the loss of freedom caused by (m2) is k. Hence, the total loss of freedom is n. We conclude that a further nondegeneracy would exceed the total available degrees of freedom n. By virtue of the jet transversality theorem from [13], generically the sets k,D,E,rmust be empty. For the openness result, we argue in a standard way. Locally, M-stationarity can be written via stable equations. Then, the implicit function theorem for Banach spaces can be applied to follow M-stationary points with respect to (local) C2-perturbations of defining functions. Finally, a standard globalization procedure exploiting the specific properties of the strong C2 s-topology can be used to construct a (global) C2 s-neighborhood of problem data for which the nondegeneracy property is stable.  Theorem 3 (Genericity for minimizers) Generically, all minimizers of SCNO are nondegenerate with the vanishing M-index. Proof Note that every local minimizer of SCNO has to be M-stationary. Nondegenerate M-stationary points are generic by Theorem 2. Hence, generically, local minimizers are nondegenerate. Due to Proposition 1, they have vanishing M-index.  By recalling Definition 3of M-index, we deduce the following important Corollary 1on the structure of minimizers for SCNO. Corollary 1 (Sparsity constraint at minimizers) At each generic local minimizer ¯x∈Rn,sof SCNO the sparsity constraint is active, i.e. ¯x0=s. 3 Relation to other stationarity concepts We relate M-stationarity to other well-known stationarity concepts for SCNO from the literature. First, we focus on S-stationarity introduced in [5]. Then, the notions of basic feasibility and CW-minimality from [1] will be discussed. 3.1 S-stationarity In [5] the following observation has been made: ¯xsolves SCNO if and only if there exists ¯y such that (¯x,¯y)solves the following mixed-integer program: min x,yf(x)s. t. n  i=1 yi≥n−s,yi∈{0,1},xiyi=0,i=1,...,n.(5) 123 226 Journal of Global Optimization (2022) 82:219–242 Using the standard relaxation of the binary constraints yi∈{0,1}, the authors arrive at the following continuous optimization problem: min x,yf(x)s. t. n  i=1 yi≥n−s,yi∈[0,1],xiyi=0,i=1,...,n.(6) As pointed out in [5], SCNO and the optimization problem (6) are closely related: ¯xsolves SCNO if and only if there exists a vector ¯ysuch that (¯x,¯y)solves (6). Additionally, the concept of S-stationarity is proposed for (6). For its formulation the following index sets are needed: I±0(¯x,¯y)={i∈{1,...,n}|¯xi= 0,¯yi=0}, I00 (¯x,¯y)={i∈{1,...,n}|¯xi=0,¯yi=0}. Definition 4 (S-stationarity, [5])A feasible point (¯x,¯y)of (6) is called S-stationary if there exist real multipliers γ1,...,γ n, such that ∇f(¯x)+ n  i γiei=0,γ i=0foralli∈I±0(¯x,¯y),(7) and, additionally, it holds: γi=0foralli∈I00 (¯x,¯y). Remark 1 (M-stationarity) We point out that initially [5] defined the concept of M- stationarity for the relaxed optimization problem (6). Namely, a feasible point (¯x,¯y)of (6) is called M-stationary if just (7) is valid. Due to the feasibility of (¯x,¯y),wehave ¯yi=0 if ¯xi= 0foralli=1,...,n. Hence, it holds: I±0(¯x,¯y)=I1(¯x), and M-stationarity is independent from the auxiliary variable ¯y. Thus, already in [4]itis sometimes said that a feasible point ¯xof SCNO is M-stationary itself. We use M-stationarity exactly in this sense, cf. Definition 1. In order to relate M- and S-stationarity, we introduce the canonical choice of the auxiliary variables ¯yfor a feasible point ¯xof SCNO: ¯yi=0,if i∈I1(¯x), 1,if i∈I0(¯x).(8) The auxiliary variables ¯ycan be seen as counters of the zero elements of ¯x.Notethat(¯x,¯y) becomes feasible for (6). Proposition 2 (M- and S-stationarity) If (¯x,¯y)is S-stationary for (6)then ¯x is M-stationary for SCNO. Vice versa, for any M-stationary point ¯x the canonical choice (8) of auxiliary variables ¯y provides an S-stationary point (¯x,¯y)for (6). Proof Let (¯x,¯y)be S-stationary for (6). After a moment of reflection we see that I±0(¯x,¯y)= I1(¯x)is the support of ¯x,and(7) reads as the M-stationarity of ¯x: ∇if(¯x)=0foralli∈I1(¯x). 123 Journal of Global Optimization (2022) 82:219–242 233 Hence, it holds: LCC (¯x,¯y)=(dx,0)(dx)i=0foralli∈I0(¯x). Case 2: ¯x0<s. Then, we additionally have n  i=1 ¯yi>n−s. Recalling (9), dx,dy∈ LCC (¯x,¯y)if and only if ⎧ ⎨ ⎩dyi=0foralli∈I1(¯x), dyi≤0foralli∈I0(¯x), (dx)i=0foralli∈I0(¯x). Hence, it holds: LCC (¯x,¯y)=dx,dy(dx)i=0and dyi≤0foralli∈I0(¯x),dyi=0foralli∈I1(¯x). In both case, CC-SOSC is to say that the matrix ∂2f ∂xi∂xj (¯x)i,j∈I1(¯x) is positive definite. This is exactly what SOSC requires. In fact, Theorem 2.2 from [20] gives the explicit representation of the Clarke tangential cone of Rn,sat ¯x: TC Rn,s(¯x)=span {ei|i∈I1(¯x)}. Now, the assertion follows due to Proposition 2. We can easily relate the concepts of nondegeneracy and SOSC. Proposition 12 (Nondegeneracy and SOSC) Let ¯x be an M-stationary point for SCNO with ¯x0=s. Assume that SOSC holds at ¯x. Then, ¯x is a nondegenerate local minimizer for SCNO. Proof Due to Proposition 10,¯xis a local minimizer of fon the set Rn,s∩span {ei|i∈I1(¯x)}. Since ¯x0=s,wehaveforallx∈Rn,ssufficiently close to ¯xthat I1(x)=I1(¯x). Hence, ¯x is actually a local minimizer for SCNO. Moreover, it is nondegenerate, because SOSC means that the matrix ∂2f ∂xi∂xj (¯x)i,j∈I1(¯x) is positive definite.  If the sparsity constraint is not active for an M-stationary point ¯xof SCNO, i. e. ¯x0<s, the implication in Proposition 12 does not hold in general anymore. Namely, ¯xdoes not need to be a local minimizer for SCNO, even in presence of SOSC. We note that this observation has been already made in Example 2.12 from [20]. Let us reconsider this example by using the notion of nondegeneracy. Example 4 (Sparsity constraint and SOSC, [20])We consider the following SCNO with n=3ands=2: min x1,x2,x3 1 2(x1+1)2+(x2−1)2+(x3−1)2s. t. (x1,x2,x3)0≤2. It is easy to see that the feasible point ¯x=(0,0,1)is M-stationary. Note that the sparsity constraint is not active for ¯x,sincek=¯x0=1<2=s. Here, I1(¯x)={3}and, hence, TC R3,2(¯x)=span {ei|i∈I1(¯x)}=span {e3}. 123 234 Journal of Global Optimization (2022) 82:219–242 Overall, SOSC holds at ¯x,but ¯xis not a local minimizer. This is due to f(0,ε,1)< f(¯x) for all ε∈(0,1],and(0,ε,1)T∈R3,2. Actually, ¯xis a nondegenerate M-stationary point with the quadratic index QI =0. For its M-index we have s−k+QI =2−1+0=1. We conclude that ¯xis rather a saddle point for SCNO.  In [16], the Fréchet and Mordukhovich normal cones of the SCNO feasible set are used to derive corresponding stationarity concepts. Let  NRn,s(¯x)stand for the Fréchet and NRn,s(¯x) for the Mordukhovich normal cone of Rn,sat ¯x, see e.g. [21] for details. Definition 9 ( N- and N-stationarity, [16])A feasible point ¯x∈Rn,sis called  N-andN- stationary for SCNO if it respectively holds: 0∈∇f(¯x)+ NRn,s(¯x)and 0 ∈∇f(¯x)+NRn,s(¯x). Note that  N-andN-stationarity can be viewed as necessary optimality conditions for SCNO, see [16]. The relation of  N-andN-stationarity to the previously discussed concepts in the context of SCNO has been essentially elaborated in [16]. Proposition 13 The notions of basic feasibility and  N-stationarity coincide. Every N- stationary point for SCNO is also M-stationary. Proof Theorem 3.1 from [16] provides explicit formulas for the Fréchet and Mordukhovich normal cones of Rn,sat a SCNO feasible point ¯xwith ¯x0=k:  NRn,s(¯x)={0},if k<s, span {ei|i∈I0(¯x)},if k=s and NRn,s(¯x)=⎧ ⎨ ⎩ J∈J(¯x) span ej|j/∈J,if k<s, span {ei|i∈I0(¯x)},if k=s, where J(¯x)={J∈J|¯x∈SJ},J={J⊂{1,...,n}||J|=s},SJ=span ej|j∈J. The equivalence of basic feasibility and  N-stationarity follows immediately. For the second assertion, we assume that ¯xis N-stationary and let i∈I1(¯x)be arbitrarily, but fixed. Then, i∈Jfor every J∈J(¯x), and, hence, ∂f ∂xi (¯x)=0. Thus, ¯xis M-stationary.  Remark 2 (N-stationarity and instability) Proposition 13 says that M-stationarity is a weaker condition than N-stationarity. However, it turns out that N-stationary points need not to be stable with respect to data perturbations. Namely, after an arbitrarily small C2- perturbation of fa locally unique N-stationary point may bifurcate into multiple N-stationary points. More importantly, this bifurcation unavoidably causes the emergence of M-stationary points, not being N-stationary. This is in full analogy with CW-minima and BF-vectors. The same Example 3illustrates the instability phenomenon for N-stationary points as well. It is worth to mention that there bifurcation happens even though the N-stationary point under consideration fulfils SOSC.  123 Journal of Global Optimization (2022) 82:219–242 235 In order to better understand the relations of M-stationarity to other stationarity concepts discussed in Sect. 3, we provide the following diagram: NC−stationarity ⇐N−stationarity ⇑ M−stationarity ⇐BF −vector ⇐CW −minimality  NB−stationarity   N−stationarity 4 Global results Let us study the topological properties of lower level sets Ma=x∈Rn,s|f(x)≤a, where a∈Ris varying. For that, we define intermediate sets for a<b: Mb a=x∈Rn,s|a≤f(x)≤b. For the topological concepts used below we refer to [24]. Let us start with Assumption 1which is usual within the scope of Morse theory, cf. [10]. It prevents from considering asymptotic effects at infinity. Assumption 1 The restriction of the objective function f|Rn,son the SCNO feasible set is proper, i. e. f−1(K)∩Rn,sis compact for any compact set K⊂R. Theorem 4 (Deformation for SCNO) Let Assumption 1be fulfilled and Mb acontain no M- stationary points for SCNO. Then, Mais homeomorphic to Mb. Proof We apply Proposition 3.2 from Part I in [10]. The latter provides the deformation for general Whitney stratified sets with respect to critical points of proper maps. Note that the SCNO feasible set admits a Whitney stratification: Rn,s= I⊂{1,...,n} |I|≤s J⊂I ZI,J, where ZI,J=x∈RnxIc=0,xJ>0,xI\J<0. The notion of criticality used in [10] can be stated for SCNO as follows. A point ¯x∈Rn,sis called critical for f|Rn,sif it holds: ∇f(¯x)|T¯xZ=0, where Zis the stratum of Rn,swhich contains ¯x,andT¯xZis the tangent space of Zat ¯x.By identifying I=I1(¯x)and, hence, Ic=I0(¯x), we see that the concepts of criticality and M-stationarity coincide. This concludes the assertion.  123 236 Journal of Global Optimization (2022) 82:219–242 Let us now turn our attention to the topological changes of lower level sets when passing an M-stationary level. Traditionally, they are described by means of the so-called cellattachment. We first consider a special case of cell-attachment. For that, let Ndenote the lower level set of a special linear function on Rp,q,i.e. N=x∈Rp,q p  i=1 xi≤, where ∈R,andtheintegersq<pare nonnegative. Lemma 1 (Normal Morse data) For any >0the set Nis homotopy-equivalent to N− with p−1 qcells of dimension q attached. The latter cells are the q-dimensional simplices from the collection conv ej,j∈JJ⊂{1,...,p},1∈J,|J|=q+1. Proof Let Ndenote the upper level set of a special linear function on Rp,q,i.e. N=x∈Rp,q p  i=1 xi≥. In terms of upper level sets Lemma 1can be obviously reformulated as follows: For any >0thesetN−is homotopy-equivalent to Nwith p−1 qcells of dimension qattached. Let us show the latter assertion. First, we note that the sets N0and N−are contractible. The contraction is performed via the mapping (x,t)→ (1−t)·x,t∈[0,1]. For the lower level set Nwe have the representation N= J⊂{1,..., p} |J|=q N,J, where N,J=x∈Rp,qxJc=0, i∈J xi≥. Note that N,Jis homotopy-equivalent to the set NJ,where NJ=x∈Rp,qxJc=0, i∈J xi=1 is the (|J|−1)-dimensional simplex conv ej,j∈Jof Rp. In fact, the map (x,t)→ t·x p  i=1 xi +(1−t)·x,t∈[0,1] 123 Journal of Global Optimization (2022) 82:219–242 237 can be used for all NJ. Altogether, Nis homotopy-equivalent to  J⊂{1,..., p} |J|=q conv ej,j∈J.(13) Note that the set in (13)isthe(q−1)-skeleton of the (p−1)-dimensional simplex of Rp. The (q−1)-skeleton of the (p−1)-dimensional simplex is the union of its simplices up to dimension q−1, see e.g. [9]. Within the (q−1)-skeleton (13), we close all q-dimensional holes by attaching qdimensional cells from the collection of simplices conv ej,j∈JJ⊂{1,...,p},|J|=q+1. The attachment should result in a contractible set, as it is actually N0. We note that the union of the subdivision conv ej,j∈JJ⊂{1,...,p},1∈J,|J|=q+1(14) is also contractible, namely, to e1.Toseethis,wemayusethemap (x,t)→ t·e1+(1−t)·x,t∈[0,1]. Furthermore, none of the relative interiors of the simplices in (14) can be deleted. In fact, deleting gives rise to the boundary of aq-dimensional simplex and the latter is not contractible. On the other hand, for any J∗⊂{1,...,p}\{1}with |J∗|=q+1 the union conv ej,j∈J∗∪ J∗∗ ⊂J∗ J∗∗=q conv ej,j∈J∗∗ ∪{1}(15) forms the boundary of the (q+1)-dimensional simplex conv ej,j∈J∗∪{1}. Hence, the set in (15) is not contractible. Altogether, precisely the q-dimensional cells in (14) can be attached to the (q−1)-skeleton (13) in order to obtain a contractible set. Its number obviously equals p−1 q. This completes the proof.  Theorem 5 (Cell-Attachment for SCNO) Let Assumption 1be fulfilled and Mb acontain exactly one M-stationary point ¯x for SCNO with ¯x0=k and the M-index equal to s−k+QI. If a <f(¯x)<b, then Mbis homotopy-equivalent to Mawith n−k−1 s−kcells of dimension s−k+QI attached, namely:  J⊂{1,...,n−k} 1∈J,|J|=s−k+1 conv ej,j∈J×[0,1]QI. Proof Theorem 4allows deformations up to an arbitrarily small neighborhood of the M- stationary point ¯x. In such a neighborhood, we may assume without loss of generality that ¯x=0and fhas the following form as from Theorem 1: f(x)=f(¯x)+ n−k  i=1 xi+ n  j=n−k+1 ±x2 j,(16) where x∈Rn−k,s−k×Rk, and the number of negative squares in (16) equals QI. In terms of [10]thesetRn−k,s−k×Rkcan be interpreted as the product of the tangential part Rk 123 238 Journal of Global Optimization (2022) 82:219–242 and the normal part Rn−k,s−k. The cell-attachment along the tangential part is standard. Analogously to the unconstrained case, one QI-dimensional cell has to be attached on Rk. The cell-attachment along the normal part is more involved. Due to Lemma 1, we need to attach n−k−1 s−kcells on Rn−k,s−k, each of dimension s−k. Finally, we apply Theorem 3.7 from Part I in [10], which says that the local Morse data is the product of tangential and normal Morse data. Hence, the dimensions of the attached cells add together. Here, we have then to attach n−k−1 s−kcells on Rn−k,s−k×Rk, each of dimension s−k+QI. Let us put Theorem 5into the context of Morse theory as developed in the literature for other nonsmooth optimization problems. The new issue for SCNO is the multiplicity of attached cells. Remark 3 (Multiplicity of attached cells) We recall that for nonlinear programming problems (NLP) the dimension of the cell to be attached while passing a critical point equals to its quadratic index, see e.g. [13]. The situation changes if we consider mathematical programs with complementarity constraints (MPCC). Here, the dimension of attached cells equals to the so-called C-index of C-stationary points, see [14]. In addition to quadratic, the C-index also has a bi-active part. The latter counts negative pairs of Lagrange multipliers corresponding to the bi-active complementarity constraints. The cell-attachment for mathematical programs with vanishing constraints (MPVC) is similar, see [8]. The dimension of attached cells equals here to the so-called T-index of T-stationary points. The T-index consists again of quadratic and bi-active parts. We emphasize that the cell-attachment for SCNO considerably differs from the described cases of NLP, MPCC, and MPVC. The main difference is that multiple cells are involved into the cell-attachment procedure for SCNO. The multiplicity of attached cells is a novel and striking phenomenon in nonsmooth optimization not observed in the literature before. From the technical point of view, this makes the cell-attachment result for SCNO to appear rather challenging. Note that the determination of the number of attached cells becomes an involved combinatorial problem from algebraic topology, see Lemma 1. Let us present a global interpretation of our results for SCNO. For that, we need to state another assumption. Following Assumption 2is standard in the context of SCNO, cf. [1], and gives a necessary condition for its solvability. Assumption 2 The restriction of the objective function f|Rn,son the SCNO feasible set is lower bounded. Now, we consider M-stationary points ¯xfor SCNO with ¯x0=kand the M-index equal to one, thus, fulfilling s−k+QI =1. These so-called saddle points can be of two types: (I) with active sparsity constraint and quadratic index equal to one, i.e. k=s,QI =1, (II) with exactly s−1 non-zero entries and vanishing quadratic index, i.e. k=s−1,QI =0. Theorem 6 (Morse relation for SCNO) Let Assumptions 1and 2be fulfilled, and all M- stationary points of SCNO be nondegenerate. Additionally, we assume that there exists a connected lower level set which contains all M-stationary points. Then, it holds: rI+(n−s)rII ≥r−1,(17) where r is the number of local minimizers of SCNO, rIand rII are the numbers of M- stationary points with M-index equal to one, which correspond to the types (I) and (II), respectively. 123 Journal of Global Optimization (2022) 82:219–242 239 Proof We assume without loss of generality that the objective function fhas pairwise different values at all M-stationarity points of SCNO. If it is not the case, we may enforce this property by sufficiently small perturbations of the objective function. Due to the openness part in Theorem 2, all M-stationarity points of such a perturbed SCNO remain nondegenerate. Moreover, the formula (17) is still valid since it does not depend on the functional values of f. Further, let qadenote the number of connected components of the lower level set Ma. We focus on how qachanges as a∈Rincreases. Due to Theorem 4,qacan change only if passing through a value corresponding to an M-stationary point ¯x,i.e.a=f(¯x). In fact, Theorem 4allows homeomorphic deformations of lower level sets up to an arbitrarily small neighborhood of the M-stationary point ¯x. Then, we have to estimate the difference between qaand qa−ε,whereε>0 is arbitrarily, but sufficiently small, and a=f(¯x). This is done by a local argument. For that, let the M-index of ¯xbe s−k+QI with ¯x0=k.Weuse Theorem 5which says that Mais homotopy-equivalent to Ma−εwith a cell-attachment of  J⊂{1,...,n−k} 1∈J,|J|=s−k+1 conv ej,j∈J×[0,1]QI.(18) Let us distinguish the following cases: 1) ¯xis a local minimizer with vanishing M-index, i.e. k=sand QI =0. Then, by (18) we attach to Ma−εthe cell conv (e1)of dimension zero. Consequently, a new connected component is created, and it holds: qa=qa−ε+1. 2) ¯xis of type (I) with M-index equal to one, i.e. k=sand QI =1. Then, by (18)we attach to Ma−εthe cell conv (e1)×[0,1]of dimension one. Consequently, at most one connected component disappears, and it holds: qa−ε−1≤qa≤qa−ε. This case is well known from nonlinear programming, see e.g. [13]. 3) ¯xis of type (II) with M-index equal to one, i.e. k=s−1andQI =0. Then, by (18) we attach to Ma−εas many as n−scells of dimension one, namely:  j=2,...,n−s+1 conv e1,ej. Consequently, at most n−sconnected components disappear, and it holds: qa−ε−(n−s)≤qa≤qa−ε. For illustration we refer to Fig. 1. Case 3) is new and characteristic for SCNO. 4) ¯xis M-stationary with M-index greater than one, i.e. s−k+QI >1. The boundary of the cell-attachment in (18)is  J⊂{1,...,n−k} 1∈J,|J|=s−k+1∂conv ej,j∈J×[0,1]QI∪conv ej,j∈J×{0,1}QI. The latter set is connected if s−k+QI >1. Consequently, the number of connected components of Maremains unchanged, and it holds: qa=qa−ε. 123 240 Journal of Global Optimization (2022) 82:219–242 Fig. 1 Cell-attachment for type (II) x3 xn−s+1 x1 ... x2 Now, we proceed with the global argument. Assumption 2implies that there exists c∈R such that Mcis empty, thus, qc=0. Additionally, there exists d∈Rsuch that Mdis connected and contains all M-stationary points, thus, qd=1. Due to Assumption 1,Md cis compact, moreover, it contains all M-stationary points. Since nondegenerate M-stationary points are in particular isolated, we conclude that there must be finitely many of them. Let us now increase the level afrom cto dand describe how the number qaof connected components of the lower level sets Machanges. It follows from the local argument that rnew connected components are created, where ris the number of local minimizers for SCNO. Let qIand qII denote the actual number of disappearing connected components if passing the levels corresponding to M-stationary points of types (I) and (II), respectively. The local argument provides that at most rIand (n−s)rII connected components might disappear while doing so, i.e. qI≤rI,qII ≤(n−s)rII. Altogether, we have: r−rI−(n−s)rII ≤r−qI−qII =qd−qc. By recalling that qd=1andqc=0, we get Morse relation (17).  We illustrate Theorem 6by discussing the same SCNO as in Example 1. Example 5 (Saddle point) We consider the following SCNO with n=2ands=1: min x1,x2 (x1−1)2+(x2−1)2s. t. (x1,x2)0≤1. As we have seen in Example 1, both M-stationary points (1,0)and (0,1)are nondegenerate minimizers. Thus, we have r=2. Morse relation (17) from Theorem 6provides: rI+rII ≥1. Hence, there should exist an additional M-stationary point with M-index one. In fact, (0,0) is this nondegenerate M-stationary point of type (II), cf. Example 1. Note that, due to rI=0 and rII =1, Morse relation (17) holds with equality here.  Let us briefly comment on the applicability of deformation and cell-attachment results in Theorems 4and 5, respectively, for the least squares loss function. 123 Journal of Global Optimization (2022) 82:219–242 241 Remark 4 (Least squares loss function) We take the least squares as the objective function in SCNO, i.e. f(x)=Ax −b2 2, where A∈Rm×ncan be viewed as a sensing matrix and b∈Rmas a measurement vector. Then, SCNO corresponds to the problem of sparse recovery from compressed sensing, see e.g. [1]. Here, it is convenient to assume that the bound on the number of non-zero entries of the signal does not exceed the number of measurements, i.e. s≤m. Let us examine whether Assumption 1is fulfilled for the least squares loss function. It turns out that the so-called s-regularity of Ais sufficient for the latter. Recall from [1] that a matrix A∈Rm×nis called s-regular if for every index set I⊂{1,...,n}with |I|=sit holds: rank (AI)=s, where AIdenotes the submatrix of Awith the columns corresponding to the set I,and rank (AI)stands for its rank. In presence of s-regularity of A, it is shown in [15] that the lower level sets Ma=x∈Rn,sAx −b2 2≤a are bounded for all a∈R. Hence, the restriction of the least squares loss function on Rn,s is in this case proper, i. e. Assumption 1is satisfied. Note that Assumption 2trivially holds for the least squares loss function, since it is nonnegative. Finally, we refer to [15]forthe detailed exposition of the topological approach as applied to sparse recovery.  Data sharing not applicable to this article as no datasets were generated or analysed during the current study. Acknowledgements The authors would like to thank Hubertus Th. Jongen for fruitful discussions, as well as the anonymous referee for the precise and constructive remarks. Funding Open Access funding enabled and organized by Projekt DEAL. Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/. References 1. Beck, A., Eldar, Y.C.: Sparsity constrained nonlinear optimization: optimality conditions and algorithms. SIAM J. Optim. 24, 1480–1509 (2013) 2. Beck, A., Hallak, N.: On the minimization over sparse symmetric sets: projections, optimality conditions, and algorithms. Math. Oper. Res. 41, 196–223 (2016) 3. Beck, A., Hallak, N.: Proximal mapping for symmetric penalty and sparsity. SIAM J. Optim. 28, 496–527 (2018) 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) 123 242 Journal of Global Optimization (2022) 82:219–242 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) 6. ˇ Cervinka, M., Kanzow, C., Schwartz, A.: Constraint qualifications and optimality conditions for optimization problems with cardinality constraints. Math. Progr. 160, 353–377 (2016) 7. Donoho, D.L.: Compressed sensing. IEEE Trans. Inf. Theory 52, 1289–1306 (2006) 8. Dorsch, D., Shikhman, V., Stein, O.: Mathematical programs with vanishing constraints: critical point theory. J. Glob. Optim. 52, 591–605 (2012) 9. Goerss, P.G., Jardine, J.F.: Simplicial Homotopy Theory. Birkhäuser, Basel (2009) 10. Goresky, M., MacPherson, R.: Stratified Morse Theory. Springer, New York (1988) 11. Hirsch, M.W.: Differential Topology. Springer, Berlin-Heidelberg-New York (1976) 12. Jongen, H.T.: On non-convex optimization. Dissertation, University of Twente, The Netherlands (1977) 13. Jongen, H.T., Jonker, P., Twilt, F.: Nonlinear Optimization in Finite Dimensions. Kluwer Academic Publishers, Dordrecht (2000) 14. Jongen, H.T., Shikhman, V., Ruckmann, J.-J.: MPCC: critical point theory. SIAM J. Optim. 20, 473–484 (2009) 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) 17. Lu, Z., Zhang, Y.: Sparse approximation via penalty decomposition methods. SIAM J. Optim. 23, 2448– 2478 (2013) 18. Milnor, J.: Morse Theory. Princeton University Press, Princeton (1963) 19. Pan, L., Xiu, N., Fan, J.: Optimality conditions for sparse nonlinear programming. Sci. China Math. 5, 1–18 (2017) 20. Pan, L., Xiu, N., Zhou, S.: On solutions of sparsity constrained optimization. J. Oper. Res. Soc. China 3, 421–439 (2015) 21. Rockafellar, R., Wets, R.: Variational Analysis. Springer, Berlin (1998) 22. 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–14822 (2011) 23. Shikhman, V.: Topological Aspects of Nonsmooth Optimization. Springer, New York (2012) 24. Spanier, E.H.: Algebraic Topology. McGraw-Hill Book Company, New York (1966) 25. Tibshirani, R.: Regression shrinkage and selection via the lasso. J. R. Stat. Soc. Ser. B 58, 267–288 (1996) Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. 123