The sparse(st) optimization problem: reformulations, optimality, stationarity, and numerical results
Abstract
EconStor is a publication server for scholarly economic literature, provided as a non-commercial public service by the ZBW.
Full text
Kanzow, Christian; Schwartz, Alexandra; Weiß, Felix Article — Published Version The sparse(st) optimization problem: reformulations, optimality, stationarity, and numerical results Computational Optimization and Applications Provided in Cooperation with: Springer Nature Suggested Citation: Kanzow, Christian; Schwartz, Alexandra; Weiß, Felix (2024) : The sparse(st) optimization problem: reformulations, optimality, stationarity, and numerical results, Computational Optimization and Applications, ISSN 1573-2894, Springer US, New York, NY, Vol. 90, Iss. 1, pp. 77-112, https://doi.org/10.1007/s10589-024-00625-0 This Version is available at: https://hdl.handle.net/10419/315246 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. http://creativecommons.org/licenses/by/4.0/
Computational Optimization and Applications (2025) 90:77–112 https://doi.org/10.1007/s10589-024-00625-0 The sparse(st) optimization problem: reformulations, optimality, stationarity, and numerical results Christian Kanzow1 ·Alexandra Schwartz2 ·Felix Weiß1 Received: 6 August 2023 / Accepted: 5 November 2024 / Published online: 28 November 2024 © The Author(s) 2024 Abstract We consider the sparse optimization problem with nonlinear constraints and an objective function, which is given by the sum of a general smooth mapping and an additional term defined by the 0-quasi-norm. This term is used to obtain sparse solutions, but difficult to handle due to its nonconvexity and nonsmoothness (the sparsity-improving term is even discontinuous). The aim of this paper is to present two reformulations of this program as a smooth nonlinear program with complementarity-type constraints. We show that these programs are equivalent in terms of local and global minima and introduce a problem-tailored stationarity concept, which turns out to coincide with the standard KKT conditions of the two reformulated problems. In addition, a suitable constraint qualification as well as second-order conditions for the sparse optimization problem are investigated. These are then used to show that three Lagrange–Newtontype methods are locally fast convergent. Numerical results on different classes of test problems indicate that these methods can be used to drastically improve sparse solutions obtained by some other (globally convergent) methods for sparse optimization problems. Keywords Sparse optimization ·Global minima ·Local minima ·Strong stationarity ·Lagrange–Newton method ·Quadratic convergence ·B-subdifferential BChristian Kanzow [email protected] Alexandra Schwartz alexandra.schw[email protected] Felix Weiß [email protected] 1Institute of Mathematics, University of Würzburg, Campus Hubland Nord, Emil-Fischer-Str. 30, 97074 Würzburg, Germany 2Faculty of Mathematics, Technical University of Dresden, Zellescher Weg 25, 01069 Dresden, Germany 123
78 C. Kanzow et al. 1 Introduction The sparse(st) optimization problem considered in this paper is the constrained problem min xf(x)+ρx0s.t. x∈X,(SPO) with a parameter ρ>0, a feasible set X(usually) given by X={x∈Rn|g(x)≤0,h(x)=0} with (at least) continuous functions f:Rn→R,g:Rn→Rm,h:Rn→Rpand x0being the number of nonzero components xiof the vector x. Following standard terminology, we call x0the 0-norm throughout this manuscript though it is not a norm. Typical applications, where sparse solutions of a given optimization problem are required, include compressed sensing for sparse representation of signals or image data, sparse portfolio selection problems, feature selection in classification learning, sparse regression or the sparse principal component analysis, see [34, Section 2] for an overview and references. Following [23], the solution methods for problems like SPO can be divided into the following three categories: (a) convex approximations, (b) nonconvex approximations, and (c) nonconvex exact reformulations. The most common convex approximation technique uses the 1-norm instead of the 0-norm in SPO. An overview on such 1-surrogate models, their advantages and solution approaches can be found in [34, Section 4.1]. Provided that fand Xthemselves are convex, the resulting optimization problem is convex (though nonsmooth) and can therefore be solved by a variety of methods for convex optimization, see [1]. This approach is very popular, for example, in solving compressed sensing problems. On the other hand, there exist prominent applications, where the 1-norm provides absolutely no sparsity (like the portfolio optimization problem used in our numerical section). This drawback leads to other sparsity improving terms that result in nonconvex approximation schemes. A natural choice is to use the p-quasi-norm for some p∈(0,1), which is no longer convex, but still continuous, see [19]. Despite its nonconvexity, if there are no constraints (i.e., X=Rn), the resulting problem can still be solved relatively efficiently by a proximal-type method. For additional constraints, one can apply an augmented Lagrangian-type method and use the proximal-type approach to solve the resulting (unconstrained) subproblems, see [10,26]. In principle, these techniques can also be used for the 0-norm, but the discontinuity still causes some trouble and typically leads to slowly convergent (proximal-type) gradient methods, see [26]. Another method belonging to the class of nonconvex approximations is the penalty decomposition method [25], which introduces an additional variable and solves the resulting problem by an alternating minimization technique. Also the DCtype methods (DC = difference of convex) described in [23] result in a nonconvex approximation which is shown to be exact under some additional assumptions, see also the DC-reformulation of the 0-norm from [20] (this reformulation, however, is 123
The sparse(st) optimization problem: reformulations... 79 applied to cardinality-constrained problems where the 0-term is not in the objective function but in the constraints, see below for a more detailed discussion). Finally, regarding the class (c) of exact nonconvex reformulations, there are, to the best of our knowledge, still just a very few papers providing such reformulations. A natural choice is to use a mixed-integer program, cf. reformulation MIP.Thisis useful for finding sparse solutions of – often quadratic – problems, whose dimension is not too large, and allows, in principle, to compute a global minimum, see e.g. [2]. By modifying the objective function with a suitable regularizing term, c.f. [3], also larger problem dimensions can be handled. For nonlinear programs or large-scale problems, however, this typically leads to an intractable reformulation. One alternative approach is the complementarity-type reformulation suggested in [16], see also [4]for a similar approach in the context of low-rank matrix recovery, which can be shown to be completely equivalent to the original sparse optimization problem SPO. The focus of the paper [16], however, is slightly different. More precisely, in this paper, we present two reformulations of the general sparse optimization problem SPO. These reformulations are introduced in Sect. 2, and partially motivated by a related approach from [6,8] for cardinality-constrained optimization problems, cf. the corresponding discussion in Sect.2. One of the two reformulations is exactly the one from [16] that we already mentioned previously. Note that the subsequent results shown for our two reformulated problems are even new for the approach from [16]. In particular, we verify in Sect.3that problem SPO and our two reformulations are equivalent in terms of both local and global minima an observation not stated in [16]. We further stress that the related approaches for cardinality-constrained problems [6,8] yield a complete equivalence with respect to global minima only, not with respect to local minima. The full equivalence between both global nad local minima in the case of SPO is therefore a quite surprising and impressive observation. Section3introduces a problem-tailored strong stationarity concept and a corresponding constraint qualification and shows that these correspond to the standard KKT conditions and a standard constraint qualification of the two reformulated problems. We then discuss suitably adapted second-order conditions in Sect.5. Though the main goal of this paper is to lay the foundations of two exact nonconvex reformulations of the sparse optimization problem SPO, the corresponding discussion leads, in a very natural way, to Lagrange–Newton-type methods for the solution of SPO, see Sect.6. Like all Newton-type methods, this is primarily a locally (fast) convergent algorithm, whereas a central difficulty for the solution of sparse optimization problems is to design suitable globally convergent methods. Nevertheless, the corresponding numerical results in Sect.7indicate that the Lagrange–Newton-type methods can be used to obtain significant improvements over solutions calculated by other (globally convergent) sparse solvers. We close with some final remarks in Sect.8. Notation: Throughout this manuscript, ei∈Rndenotes the i-th unit vector, whereas e:= (1,...,1)T∈Rnis the all-one vector. Given x∈Rnand x∗∈X, we define the index sets I0(x):= {i|xi=0}and Ig(x∗):= {i|gi(x∗)=0} 123
80 C. Kanzow et al. of zero components of xand active inequality constraints at x∗, respectively. For an arbitrary vector x, we write diag(x)for the corresponding diagonal matrix, whose diagonal entries are given by the elements of x. Given two vectors x,y∈Rn,the Hadamard (elementwise) product is denoted by x◦y, i.e., the elements of this vector are given by xi·yifor all i=1,...,n. 2 Two smooth reformulations of SPO In this section we derive two smooth reformulations of SPO and show that the local and global minima of these reformulated problems coincide with the local and global minima of the original sparse optimization problem SPO. One of these reformulations is already known from [16], whereas the other one is new and will be more suited for our numerical experiments later on. Note that the results stated in this manuscript for the known formulation from [16] are still new and not contained in that reference. Throughout this section, we only require f,g,hto be continuous. Let us consider the sparse optimization problem from SPO with an arbitrary set X⊆Rn. For any x∈Rn, define a corresponding binary variable y∈{0,1}nby setting yi:= 0forxi= 0 and yi:= 1forxi=0. Using this y, we can calculate the 0-norm of xas x0= xi=0 1= n i=1 (1−yi)=n−eTy. Thus, we could rewrite problem SPO by the following mixed-integer problem min x,yf(x)+ρ(n−eTy)s.t. x∈X,x◦y=0,y∈{0,1}n.(MIP) In order to move to a continuous optimization problem, we discard the binary constraints on y. We need to retain the constraint y≤e, because otherwise the objective function of (MIP) does not admit a minimum. This leads us to the reformulation min (x,y)f(x)+ρ(n−eTy)s.t. x∈X,x◦y=0,y≤e.(SPOlin) Since the auxiliary variable yenters the objective function linearly, we denote this problem SPOlin. This is in contrast to our second formulation min (x,y)f(x)+ρ 2 n i=1 yi(yi−2)s.t. x∈X,x◦y=0 (SPOsq) called SPOsq, since we add a quadratic term to the objective function. Note that this quadratic term is designed in such a way that it vanishes, whenever xi= 0 (due to the complementarity-type constraint), and that it attains its minimum at yi=1 whenever this variable is unconstrained, i.e., for all iwith xi=0., see Fig. 1. 123
The sparse(st) optimization problem: reformulations... 81 -1 0 1 2 yi -1 1 −yi -1 0 1 2 yi -1 1yi(yi−2) Fig. 1 Comparison of the terms −yiused in SPOlin and yi(yi−2)used in SPOsq Problem SPOlin corresponds to the reformulation already introduced in [16], whereas SPOsq seems to be new. Observe that, if the feasible set Xcontains no inequality constraints, then the new formulation SPOsq boils down to an equalityconstrained optimization problem, in contrast to SPOlin, which still includes the inequalities y≤e. This observation is particularly useful in our setting since, later, we will apply a Lagrange–Newton-type method in order to solve the sparse optimization problem. Before we take a closer look at the relaxed problems SPOlin and SPOsq, we would like to briefly discuss the relation of the sparse problem SPO and its relaxations to the two closely related problem classes of cardinality-constrained problems min xf(x)s.t. x∈X,x0≤κ and cardinality minimization problems min xx0s.t. x∈X,f(x)≤δ, where κ∈Nand δ∈Rare given constants. Using the same ideas as above, these problems can be relaxed to the continuous problems min x,yf(x)s.t. x∈X,x◦y=0,y≤e,n−eTy≤κ, min x,yn−eTys.t. x∈X,x◦y=0,y≤e,f(x)≤δ, respectively. As we show below, for problem SPO the two relaxations are equivalent to the original problem in terms of global and local minima. Using the same arguments, it is also possible to show this equivalence for the cardinality minimization problem. However, for the cardinality-constrained problem it is known, see [6], that only the global minima of the original problem and its relaxation coincide, but the relaxation may have additional local minima. Furthermore, one may be tempted to view problem SPO as a penalty reformulation of either of the other two problems. However, while a solution x∗of SPO is always a solution of the other two problems with κ:= x∗0or δ:= f(x∗), respectively, the opposite implication is in general not true. This means that solutions of the cardinalityconstrained problem or cardinality minimization problem cannot always be recovered 123
82 C. Kanzow et al. as solutions of SPO. More details on these relations can be found in [34, Proposition 1.1]. 3 Properties of reformulations In the moment, it is not clear why we can view the programs SPOlin and SPOsq as reformulations of the given nonsmooth and discontinuous sparse optimization problem SPO. But, as we show below, these three programs are completely equivalent in terms of both global and local minima. Even their corresponding stationary points coincide, see Sect. 4for details on this. Some of statements presented in Sect. 3can be proven in an elementary and straightforward manner. For the sake of completion they have thus been moved to the appendix. In order to verify these statements, we first need some preliminary results. Note that xis obviously feasible for the given problem SPO if and only if there exists a suitable vector y∈Rnsuch that (x,y)is feasible for SPOlin or SPOsq. Furthermore, we have the following relations for feasible points of these two programs. Lemma 3.1 The following statements hold: (i) Let (x,y)be feasible for SPOlin. Then x0≤n−eTy,with equality if and only if yi=1for all i ∈I0(x). (ii) Let (x,y)be feasible for SPOsq. Then x0−n≤n i=1yi(yi−2), with equality if and only if yi=1for all i ∈I0(x). Proof cf. appendix. The following result shows that the constellation yi=1fori∈I0(x)is indeed the most preferable one. Lemma 3.2 Let (x∗,y∗)be a local minimum of SPOlin or SPOsq. Then we have y∗ i=1for all i ∈I0(x∗). Proof cf. appendix. Next, we show that the set of local minima of the sparse optimization problem SPO is independent of the particular choice of the penalty parameter. Note that, this is due to the discontinuity of the 0-norm and that a similar result for sparse optimization problems involving the 1-norm, e.g., does not hold. This observation may actually be viewed as an advantage of the 0-norm, since this implies that a suitable choice of the penalty parameter is much less critical for the 0-formulation of the sparse optimization problem than other (continuous) formulations like the one based on the 1-norm or the q-quasi-norm for q∈(0,1). Proposition 3.3 Let x∗be a local minimum of SPO with penalty parameter ρ1>0. Then x∗is also a local minimum of SPO for any other penalty parameter ρ2>0. Proof cf. appendix. 123
The sparse(st) optimization problem: reformulations... 83 The previous statement also holds for the two reformulated programs SPOlin and SPOsq. This is a consequence, e.g., of the following result, which states that x∗is a local minimum of the sparse optimization problem SPO if and only if there exists a vector y∗such that the pair (x∗,y∗)is a local minimum of either SPOlin or SPOsq. Theorem 3.4 (Equivalence of Local Minima) The following statements are equivalent: (i) x∗is a local optimum of SPO. (ii) There exists y∗such that (x∗,y∗)is a local optimum of SPOlin. (iii) There exists y∗such that (x∗,y∗)is a local optimum of SPOsq. Proof Notice that, by Lemma 3.2,y∗has to be of the form y∗ i=1fori∈I0(x∗), 0 otherwise, (*) in order for (x∗,y∗)to be a local minimum of SPOlin or SPOsq. (i)⇒ (ii):Letx∗be a local minimum of SPO and let y∗be defined as in (*). Then f(x∗)+ρn−eTy∗=f(x∗)+ρ x∗ 0≤f(x)+ρx0≤f(x)+ρn−eTy for all feasible (x,y)with xsufficiently close to x∗, where the first equality and the last inequality follow from Lemma 3.1(i). (ii)⇒ (i):Let(x∗,y∗)be the local minimum of SPOlin with y∗as in (*). Assume that x∗is not a local minimum of SPO. Then there exists a sequence {xk}⊆Xsuch that xk→x∗and f(xk)+ρ xk 0<f(x∗)+ρ x∗ 0∀k∈N.(1) Recall that xk 0≥x∗0holds for all ksufficiently large. Hence we either have a subsequence {xk}Ksuch that xk 0=x∗0holds for all k∈K,orx∗0+1≤ xk 0is true for almost all k∈N. In the former case, it follows that (xk,y∗)is feasible for SPOlin, hence we obtain from Lemma 3.1(i)and the minimality of (x∗,y∗) for SPOlin that f(xk)+ρ xk 0=f(xk)+ρ x∗ 0 =f(xk)+ρ(n−eTy∗)≥f(x∗)+ρ(n−eTy∗) =f(x∗)+ρ x∗ 0, which contradicts (1). Otherwise, we have x∗0+1≤ xk 0and, by continuity, also f(x∗)≤f(xk)+ρfor all k∈Nsufficiently large, which, in turn, gives f(xk)+ρ xk 0≥f(xk)+ρ+ρ x∗ 0≥f(x∗)+ρ x∗ 0. 123
84 C. Kanzow et al. Hence, also in this situation, we have a contradiction to (1). (i)⇒ (iii):Letx∗be a local minimum of SPO. Then x∗is also a local minimum of the optimization problem min f(x)+ρ 2x0−ns.t. x∈X,(2) since, by Proposition 3.3, we can modify the penalty parameter, and since adding a constant to the objective function does not change the location of the local minima. Now, let y∗be defined as in statement (*). Then f(x∗)+ρ 2 n i=1 y∗ iy∗ i−2=f(x∗)+ρ 2 x∗ 0−n≤f(x)+ρ 2x0−n ≤f(x)+ρ 2 n i=1 yiyi−2, for all feasible (x,y)with xsufficiently close to x∗, where the first equality and the last inequality follow from Lemma 3.1(ii). (iii)⇒ (i):Let(x∗,y∗)be a local minimum of SPOsq with y∗as in (*). Assume that x∗is not a local minimum of SPO. Then x∗is not a local minimum of (2). Hence, there exists a sequence {xk}⊆Xsuch that xk→x∗and f(xk)+ρ 2 xk 0−n<f(x∗)+ρ 2 x∗ 0−n∀k∈N.(3) Recall that xk 0≥x∗0holds for all ksufficiently large. Thus, once again, we either have a subsequence {xk}Ksuch that xk 0=x∗0holds for all k∈K, or x∗0+1≤ xk 0is true for almost all k∈N. In the former case, it follows that (xk,y∗)is feasible for SPOsq, hence we obtain from Lemma 3.1(ii)and the minimality of (x∗,y∗)for SPOsq that f(xk)+ρ 2 xk 0−n=f(xk)+ρ 2 x∗ 0−n=f(xk)+ρ 2 n k=1 y∗ iy∗ i−2 ≥f(x∗)+ρ 2 n k=1 y∗ iy∗ i−2=f(x∗)+ρ 2 x∗ 0−n, which contradicts (3). Otherwise, we have x∗0+1≤ xk 0and, by continuity, also f(x∗)≤f(xk)+ρ 2for all k∈Nsufficiently large, which, in turn, gives f(xk)+ρ 2 xk 0−n≥f(xk)+ρ 2+ρ 2 x∗ 0−n≥f(x∗)+ρ 2 x∗ 0−n. Hence, also in this situation, we have a contradiction to (3). 123
The sparse(st) optimization problem: reformulations... 91 Theorem 5.3 (Second-Order Sufficiency Conditions) Let (x∗,λ ∗,μ ∗)be an Sstationary point such that (strong) SP-SOSC holds in x∗. Then the following statements hold: (i) (Strong) SOSC for SPOlin holds at (x∗,y∗,λ ∗,μ ∗,γ∗,σ∗)with (y∗,γ∗,σ∗) defined in Proposition 4.1. (ii) (Strong) SOSC for SPOsq holds at (x∗,y∗,λ ∗,μ ∗,γ∗)with (y∗,γ∗)defined in Proposition 4.1. (iii) x∗is a local minimizer of SPO. Proof For a given S-stationary point (x∗,λ ∗,μ ∗)let y∗,γ∗, and σ∗be chosen as in Proposition 4.1 and define z:= (x,y). The Hessian matrices of the Lagrangians of problems SPOlin and SPOsq with respect to zare given by ∇2 zzLlin(x∗,y∗,λ ∗,μ ∗,γ∗,σ∗)=∇2 xxLSP(x∗,λ ∗,μ ∗)diag(γ ∗) diag(γ ∗)0and ∇2 zzLsq(x∗,y∗,λ ∗,μ ∗,γ∗)=∇2 xxLSP(x∗,λ ∗,μ ∗)diag(γ ∗) diag(γ ∗)ρIn, respectively, where Indenotes the identity matrix in Rn×n. Since y∗ i=1 and σ∗ i= ρ>0 for all i∈I0(x∗), we obtain the following critical cones for the smooth problems SPOlin and SPOsq, respectively: Clin(z∗,λ ∗)={d=(dx,dy)T|∇gi(x∗)Tdx=0∀i∈Ig(x∗), λ∗ i>0, ∇gi(x∗)Tdx≤0∀i∈Ig(x∗), λ∗ i=0, ∇h(x∗)Tdx=0, (dx)i=0∀i∈I0(x∗), dy=0}, Csq(z∗,λ ∗)={d=(dx,dy)T|∇gi(x∗)Tdx=0∀i∈Ig(x∗), λ∗ i>0, ∇gi(x∗)Tdx≤0∀i∈Ig(x∗), λ∗ i=0, ∇h(x∗)Tdx=0, (dx)i=0∀i∈I0(x∗), (dy)i=0∀i/∈I0(x∗)} and, similarly, the critical subspaces SClin(z∗,λ ∗):= {d=(dx,dy)T|∇gi(x∗)Tdx=0∀i∈Ig(x∗), λ∗ i>0, ∇h(x∗)Tdx=0, (dx)i=0∀i∈I0(x∗), dy=0}, 123
92 C. Kanzow et al. SCsq(z∗,λ ∗):= {d=(dx,dy)T|∇gi(x∗)Tdx=0∀i∈Ig(x∗), λ∗ i>0, ∇h(x∗)Tdx=0, (dx)i=0∀i∈I0(x∗), (dy)i=0∀i/∈I0(x∗)}. For a vector d=(dx,dy)T, we obtain dx dyT ∇2 zzLsq dx dy=dx dyT ∇2 zzLlin dx dy+ρ dy 2 2 =dxT∇2 xxLSP(x∗,λ ∗,μ ∗)dx +2(γ ∗)T(dx◦dy)+ρ dy 2 2.(22) Assume d=(dx,dy)T∈Clin(x∗,λ ∗)is a nonzero vector. Then we have dx∈CSPO(x∗,λ ∗), dy=0. In particular, this implies dx= 0. According to (22), the SP-SOSC immediately implies claim (i). The proof for strong SOSC is analogous. Assume d=(dx,dy)T∈Csq(x∗,λ ∗)is a nontrivial vector. It holds dx∈CSPO(x∗,λ ∗), (dy)i=0,i/∈I0(x∗). At least one of the two vectors dx,dyis nonzero and we know dx◦dy=0. Hence SPSOSC implies (ii), according to inequality (22). Strong SOSC can again be verified analogously. Finally, the validity of SOSC for either SPOlin or SPOsq immediately yields (iii) due to the equivalence of local minima. We next state a second-order necessary optimality condition for the sparse optimization problem SPO, which can be derived via the relation to the corresponding secondorder conditions of one of the two smooth reformulations SPOlin or SPOsq.Note that this necessary condition will not be used later, but is stated here for the sake of completeness. Theorem 5.4 (Second-Order Necessary Condition) Let x∗be a local minimum of SPO satisfying SP-LICQ. Then there exist unique multipliers (λ∗,μ ∗)such that (x∗,λ ∗,μ ∗) is an S-stationary point of SPO satisfying the second-order necessary condition dT∇xxLSP(x∗,λ ∗,μ ∗)d≥0,∀d∈CSPO(x∗,λ ∗). Proof The existence and uniqueness of the multipliers (λ∗,μ ∗)such that the triple (x∗,λ ∗,μ ∗)satisfies the S-stationarity conditions is an immediate consequence of Theorems 4.3 and 4.5. 123
The sparse(st) optimization problem: reformulations... 93 Furthermore, we know from these results that there exist (uniquely defined) vectors y∗and σ∗such that (x∗,y∗,λ ∗,μ ∗,σ∗)is a KKT point of SPOsq satisfying standard LICQ, and with (x∗,y∗)being a local minimizer of SPOsq, cf. Theorem 3.4. Hence the standard second-order necessary optimality condition holds for SPOsq, i.e., we have dx dyT∇2 xxLSP(x∗,μ ∗,λ ∗)diag(γ ∗) diag(γ ∗)ρIndx dy≥0,∀dx dy∈Csq(x∗,λ ∗). This is equivalent to (dx)T∇2 xxLSP(x∗,μ ∗,λ ∗)dx+ρ dy 2 2≥0,∀dx dy∈Csq(x∗,λ ∗), (23) where we used the fact that (dx)i·(dy)i=0, cf. the previous proof. Now it is easy to see that any vector d=(dx,dy)Twith dx∈CSPO(x∗,λ ∗)and dy=0 is contained in Csq(x∗,λ ∗).Inviewof(23), this directly yields (dx)T∇2 xxLSP(x∗,μ ∗,λ ∗)dx≥0,∀dx∈CSPO(x∗,λ ∗). This completes the proof. Note that there exist more general second-order conditions for standard nonlinear programs, see, e.g., [5]. In principle, it is possible to translate these conditions also to problem-tailored second-order optimality conditions for the sparse optimization problem SPO due to its relation to the standard second-order optimality conditions to one of the reformulated smooth problems SPOlin or SPOsq. We omit the corresponding details. 6 Lagrange–Newton-type methods The aim of this section is to present some Lagrange–Newton-type methods for the (local) solution of the sparse optimization problem SPO. The idea is to use one of our smooth reformulations and to apply a Newton-type method to the corresponding KKT conditions. In principle, we could take either the reformulation SPOlin or the one from SPOsq. Here we decide to consider the reformulation SPOsq which, in particular, has the advantage that the corresponding KKT conditions consist of nonlinear equations only, if the original problem SPO contains not inequalities. This observation might be useful for Lagrange–Newton-type approaches. Nevertheless, the theory also covers the case where inequality constraints are present. More precisely, we consider three different Newton-type methods: First, we take the full KKT system of SPOsq and investigate the local convergence properties of a corresponding nonsmooth Newton method applied to this system. Second, we consider a reduced variant of this method which eliminates the y-variables and show that it converges under the same set of assumptions as the previous approach. Third, we deal 123
94 C. Kanzow et al. with a method which tries to overcome some singularity problems for some classes of sparse optimization problems, which include nonnegativity constraints. But before we get into the details, let us briefly recall the central ideas behind a nonsmooth version of the Newton method. Remark 6.1 (Nonsmooth Newton’s method in a nutshell) Given a mapping T:Rn→ Rn, we can try to compute a root of Twith a Newton-type iteration scheme zk+1=zk−H−1 kT(zk)∀k=0,1,2,..., where Hk∈Rn×nis a matrix typically related to the derivative of Tat zk. If we want to apply this to the KKT system of SPOsq,wefirsthavetoreformulate the conditions λi≥0,gi(x)≤0,λ igi(x)=0∀i=1,...,m into mequality constraints. This can be achieved by using a suitable NCP-function ϕ:R2→R, which is defined by the property φ(a,b)=0⇐⇒ a≥0,b≥0,ab =0. Two prominent examples are the minimum function and the Fischer-Burmeister function φm(a,b):= min{a,b}and φFB(a,b):= a2+b2−a−b. Defining the function g:Rn×Rm→Rmcomponentwise as (g)i(x,λ)=φ(−gi(x), λi), we can thus replace the conditions on gand λby the equation system g(x,λ)=0. However, most NCP functions are (by design) nonsmooth at least in the origin. We thus cannot use the Jacobian Hk=T(zk)as in the classical Newton’s method, but instead need some tools from nonsmooth analysis. If the mapping Tis a locally Lipschitz continuous mapping, then Rademacher’s Theorem implies that Tis almost everywhere differentiable. Hence the set ∂BT(z):= H∃{zk}⊆DT:zk→zand T(zk)→H is nonempty and bounded, where DTdenotes the set of differentiable points of T. The set ∂BT(z)is called the B-subdifferential of Tin zand its convex hull gives the generalized Jacobian ∂T(z)by Clarke [11]. A point zis called BD-regular,ifall elements in ∂BT(z)are nonsingular. If we use a matrix Hk∈∂BT(zk)in the Newton-type iteration scheme, the resulting nonsmooth Newton’s method is known to be locally superlinearly or even quadratically convergent to a root z∗, if this root z∗is BD-regular and Tsatisfies an additional 123
The sparse(st) optimization problem: reformulations... 95 smoothness property called semismoothness and strong semismoothness, respectively. For the precise definitions and proofs of the previous statements, the interested reader is referred to the papers [30,31] and the monograph [14]. Throughout this section, we assume that all functions f,g,hare twice continuously differentiable. Furthermore, φdenotes either the minimum or the Fischer-Burmeister function, unless we state something else explicitly. Then it is known that the three operators Tused below are semismooth. They are strongly semismooth if, in addition, the second-order derivatives of f,g,hare locally Lipschitz continuous. In order to verify the local fast convergence of the nonsmooth Newton method applied to T(z)= 0, it thus suffices to prove BD-regularity in the root z∗. For more details on this, we refer the reader, for instance, to [15]. The first Newton-type method presented in this section uses the operator T(x,y,λ,μ,γ):= ⎛ ⎜ ⎜ ⎜ ⎜ ⎝ ∇xLSP(x,λ,μ)+γ◦y ρ(y−e)+γ◦x g(x,λ) h(x) x◦y ⎞ ⎟ ⎟ ⎟ ⎟ ⎠ , where gis defined as in Remark 6.1. Due to the defining property of an NCPfunction, it follows that (x∗,y∗,λ ∗,μ ∗,γ∗)is a KKT point of the reformulated problem SPOsq if and only if it solves the (in general nonsmooth) system of equations T(x,y,λ,μ,γ)=0. In order to ensure fast local convergence of the nonsmooth Newton method applied to the system T(z)=0, it suffices to show that a solution z∗=(x∗,y∗,λ ∗,μ ∗,γ∗) thereof is BD-regular under suitable assumptions. Theorem 6.2 Let z∗=(x∗,y∗,λ ∗,μ ∗,γ∗)be a solution of T (z)=0such that the following assumptions hold: (i) SP-LICQ is satisfied at x∗. (ii) Strong SP-SOSC is satisfied at (x∗,λ ∗,μ ∗). Then z∗is a BD-regular point of T . Proof Based on our previous result, the statement can be traced back to existing results in the literature. Since z∗is a KKT point of SPOsq, we know that the bi-active set {i|x∗ i=0=y∗ i}is empty. Therefore, it follows from assumption (i)and Theorem 4.5 that ordinary LICQ holds for SPOsq at z∗. Similarly, assumption (ii)and Theorem 5.3 imply that the strong second-order sufficiency conditions holds for SPOsq at z∗. Standard results on the local convergence of nonsmooth Newton methods then imply that all elements H∈∂BT(z∗)are nonsingular, see, e.g., [13,14,17]. We next consider a reduced formulation of the system T(z)=0. To this end, note that T(z)=0 immediately gives y=e−γ◦x ρ,(24) 123
96 C. Kanzow et al. cf. (15). Hence, eliminating the variable yin the definition of Tby replacing it with the above expression, we obtain the reduced operator Tred(x,λ,μ,γ)=⎛ ⎜ ⎜ ⎝ ∇xLSP(x,λ,μ)+γ◦(e−γ◦x ρ) (−g(x), λ) h(x) x◦(e−γ◦x ρ) ⎞ ⎟ ⎟ ⎠ , which is independent of y. In view of its derivation, it still holds that any zero of Tred yields a KKT point of SPOsq and vice versa, whenever the variable yis defined as above. In order to locally solve the KKT system of SPOsq, we can therefore, alternatively, apply a nonsmooth Newton method to the system Tred(w) =0, where w=(x,λ,μ,γ). The central point for the local fast convergence of this approach is again the BD-regularity of a solution w∗. Theorem 6.3 T is BD-regular in (x,y,λ,μ,γ)with y =(e−γ◦x/ρ) if and only if Tred is BD-regular in (x,λ,μ,γ). Proof Let w=(x,λ,μ,γ) and z=(x,y,λ,μ,γ) with y=e−γ◦x/ρ.The definition of the B-subdifferential then yields H∈∂BT(z)⇐⇒ H=⎛ ⎜ ⎜ ⎜ ⎜ ⎝ ∇2 xxLSP(x,λ,μ) diag(γ ) g(x)Th(x)Tdiag(y) diag(γ ) ρIn0 0 diag(x) J1g0J2g00 h(x)0000 diag(y)diag(x)00 0 ⎞ ⎟ ⎟ ⎟ ⎟ ⎠ , and, similarly, Hred ∈∂BTred(w) if and only if Hred =⎛ ⎜ ⎜ ⎜ ⎝ ∇2 xxLSP(x,λ,μ)−diag(γ )2 ρg(x)Th(x)Tdiag(e−2γ◦x ρ) J1gJ2g00 h(x)00 0 diag(e−2γ◦x ρ)00−diag(x)2 ρ ⎞ ⎟ ⎟ ⎟ ⎠ , with (J1g,J2g)∈∂Bg(x,λ). Assume wis BD-regular for Tred.LetH∈∂BT(z) and consider the system Hd =0 with appropriately partitioned d=(dx,dy,dλ,dμ,dγ). (25) 123
The sparse(st) optimization problem: reformulations... 97 Solving for dyexplicitly and plugging in y=e−γ◦x/ρ yields 1 ρ(−γ◦dx−x◦dγ)−dy=0, ⎛ ⎜ ⎜ ⎜ ⎝ ∇2 xxLSP(x,λ,μ)−diag(γ )2 ρg(x)Th(x)Tdiag(e−2γ◦x ρ) J1gJ2g00 h(x)00 0 diag(e−2γ◦x ρ)00−diag(x)2 ρ ⎞ ⎟ ⎟ ⎟ ⎠ ⎛ ⎜ ⎜ ⎝ dx dλ dμ dγ ⎞ ⎟ ⎟ ⎠=0. (26) BD-regularity of Tred implies (dx,dλ,dμ,dγ)=(0,0,0,0)and therefore also dy= 0. Hence His nonsingular. Since this holds for arbitrary H∈∂BT(z),theBDregularity of Tin zfollows. The proof of the converse statement is similar: Assume Tred is not BD-regular in w. Then there is a singular matrix H∗ red ∈∂BTred(w∗), i.e., there exists (J1∗ g,J2∗ g)∈ ∂Bg(x∗,λ ∗)such that the corresponding element H∗ red is singular. This means that there is a nontrivial element d0=(d1 0,d3 0,d4 0,d5 0)T∈ker(H∗ red). Setting d2 0:= 1 ρ(−γ◦d1 0−x◦d5 0)and reversing the previous arguments, we obtain a singular element in ∂BT(z). Note that the assumption y=(e−γ◦x/ρ) used in Theorem 6.3 holds automatically at any KKT point. Theorem 6.3 therefore allows to translate the result from Theorem 6.2 directly to the reduced operator Tred. A potential disadvantage of the reduced formulation is the fact that the replacement of the variable yby the expression (24) increases the nonlinearity of the resulting operator Tred. Finally, we turn to a third Newton-type method for the solution of sparse optimization problems SPO, whose feasible set Xcontains nonnegativity constraints for some or all variables. For notational simplicity, we consider only the fully nonnegative case x≥0. In our general approach, we have to view these constraints as part of the inequalities g(x)≤0, which causes problems with the constraint qualification. SP-LICQ would require the linear independence of the gradient vectors −ei(resulting from the constraint xi≥0 as an inequality) and ei(resulting from the sparsity in the definition of SP-LICQ) for all i∈I0(x∗), which is obviously impossible. We can overcome this situation in the following way: In any local minimum of SPOsq,wehavey≥0 according to Lemma 3.2. Together with the constraint x◦y= 0 and the nonnegativity constraint x≥0 we thus obtain the full complementarity conditions x≥0,y≥0,x◦y=0, which we can replace by an additional NCPfunction (x,y)=0 with i(x,y)=φ(xi,yi)for all i=1,...,n. The constraints x≥0 then do not need to be considered as a part of the standard inequality constraints 123
98 C. Kanzow et al. g(x)≤0 any more. This motivates to consider the nonlinear system of equations TC(x,y,λ,μ,γ)=0 with TC(x,y,λ,μ,γ):= ⎛ ⎜ ⎜ ⎜ ⎜ ⎝ ∇xLSP(x,λ,μ)+γ◦y ρ(y−e)+γ◦x g(x,λ) h(x) (x,y) ⎞ ⎟ ⎟ ⎟ ⎟ ⎠ , with two NCP-functions g,. Then SP-LICQ is a reasonable assumption for this reformulation, and the following result holds. Theorem 6.4 Let z∗=(x∗,y∗,λ ∗,μ ∗,γ∗)be a solution of TC(z)=0such that the assumptions of Theorem 6.2 hold. Then z∗is a BD-regular point of TC. Proof First observe that TC(z∗)=0 implies T(z∗)=0, hence z∗is a KKT point of SPOsq. In view of Proposition 4.1, we therefore have that the bi-active set {i|x∗ i= y∗ i=0}is empty. This implies that is continuously differentiable in a neighborhood of (x∗,y∗), with componentwise derivatives given by (recall that is defined either by the Fischer-Burmeister function or by the minimum function) ∇φFB(x∗ i,0)=(0,−1)Tand ∇φm(x∗ i,0)=(0,1)T, ∇φFB(0,y∗ i)=(−1,0)Tand ∇φm(0,y∗ i)=(1,0)T. Thus, each element HC∈∂BTC(z∗)can be written as: HC=⎛ ⎜ ⎜ ⎜ ⎜ ⎝ ∇2 xxLSP(x∗,λ ∗,μ ∗)diag(γ ∗)g(x∗)Th(x∗)Tdiag(y∗) diag(γ ∗)ρIn0 0 diag(x∗) J1g0J2g00 h(x∗)0000 diag(cx)diag(cy)00 0 ⎞ ⎟ ⎟ ⎟ ⎟ ⎠ , with cx,cysuch that ((cx)i,(cy)i)∈{−1,1}×{0}if i∈I0(x∗), {0}×{−1,1}otherwise, and arbitrary (J1g,J2g)∈∂Bg(x∗,λ ∗). Define A:= I2n+m+p0 0diag (cx+cy)◦(x∗+y∗), and observe that Ais nonsingular. Then a simple calculation shows that A·HC∈ ∂BT(z∗). Since Ais nonsingular and all elements in ∂BT(z∗)are nonsingular by Theorem 6.2, it follows that HCis nonsingular. This completes the proof. 123
The sparse(st) optimization problem: reformulations... 99 Though the third formulation using the operator TCis mainly designed for problems having additional nonnegativity constraints, we can also apply this idea also to problems without these nonnegativity constraints, by splitting the variables x=x+−x− into their positive and negative parts x+x−≥0. Since this is a pretty standard approach also used in [16], we skip the corresponding details. Some additional remarks on the choice of the NCP-function are in order. Assume that problem SPO has a feasible set described by inequality constraints and we choose g(x,λ)=min{−g(x), λ}, to be understood componentwisely. Then the lower part of ∂BT(z)reads −diag(cx)g(x)0diag(cy)0 diag(y)diag(x)00 such that the matrix diag(cx), diag(cy)belongs to the subdifferential ∂Bmin{a,b}. Then, in particular, if g(x)>0, we always have diag(cy)=0. Depending on the values of x,yand g(x)we may encounter a singularity. The situation is even worse for the operator TC. To this end, consider the minimum-function min{x,y}as surrogate for x◦yand assume we have an iterate (xk,yk)with yk i>xk i(which is, for instance, the case in the portfolio setting, since, in general, we initialize y0 i=1 for all i=1,...,n). Then, with any equality constraints hin place, the lower part of ∂BTC(zk)reads h(x)000 En000 , and we immediately encounter a singularity. In our subsequent implementation, we therefore prefer to use the Fischer-Burmeister approach simply because the (generalized) partial derivatives of the minimum function have 0-1-entries, whereas the corresponding partial derivatives of the Fischer-Burmeister-function are usually both different from zero (unless we are in a KKT point). 7 Numerical results In this section we present some numerical results obtained by applying the previously developed Lagrange–Newton-type methods to some commonly known fields of sparse optimization problems. We start with some preliminaries regarding our implementation. 7.1 Implementation Initial values Lagrange–Newton-type methods are mainly locally convergent approaches. Our aim is to show these methods can be used to improve solutions obtained by globally 123
100 C. Kanzow et al. convergent techniques. Therefore, we pre-process the problem by first solving the 1-surrogate problem min xf(x)+ρx1s.t. x∈X, with f,Xas in SPO. We then use the solution x1of the 1-surrogate problem as initial point x0for the Lagrange–Newton-type methods, which we consider post-processing of the 1-surrogate problem. Accumulation points x∗of our Lagrange–Newton-type methods should (hopefully) be preferable for SPO over the 1-solution. Note that it is, in general, not useful to have x0=0 as the initial guess. In fact, in cases where constraints do not exist, the initial guess x0=0 does already yield an S-stationary point. The starting point x0=x1, obtained by the pre-preprocessing phase, may also have many zero components, but should, nonetheless, be a much better choice than the zero vector. Furthermore, we found it beneficial to initialize y0:= esince we want to see a majority of 0-entries in the accumulation point x∗of the algorithm, which would correlate with a y∗consisting of mainly 1-entries. For any of the Lagrangian multipliers (λ,μ,γ)we worked with the canonical choice: λ0=0, μ0=0, γ0=0, in the respective dimensions. Note that any choice of γ0might be arbitrarily bad since, for an accumulation point x∗with an entry 10−4≈|x∗ i| = 0, one has to expect γ∗ i≈ρsign(x∗)104. In our numerical test, we were able to improve upon the 1-solution x0in terms of the target value of the respective SPO and also in terms of the initial sparsity. Dealing with the B-subdifferential We only consider the Fischer-Burmeister function, whenever an NCP-function is required in our computations. The method to obtain an element in the B-subdifferential of the Fischer-Burmeister function is widely known, compare [12]. We fix a point z=(x,y,λ,μ,γ)and consider the operator TCwith the components: φFB(xi,yi), (i=1,...,n), φFB(−gj(x), λj), ( j=1,...,m), and Ixy := {i|xi=yi=0},Igλ:= {j|gj(x)=λj=0}. Define: (xt,yt,λ t):= (x−te(n), y−te(n), λ −te(p)), for t>0, with e=(1,1,...,1)Tof the appropriate dimension. Passing to the limit t0 yields lim t0∇(xi,yi)φFB(xt i,yt i)T=⎧ ⎪ ⎨ ⎪ ⎩ xi x2 i+y2 i−1,yi x2 i+y2 i−1,i/∈Ixy, −1 √2−1,−1 √2−1,i∈Ixy, (27) 123
The sparse(st) optimization problem: reformulations... 107 Fig. 4 Average target value of f(x)+ρx0and 0-Norm for successful compressive sensing runs early, as the error in the Newton-step with respect to the 2-norm went past the safety threshold of 100. For all values of ρ, the resulting average value f(x)+ρx0of all successful runs is shown in Fig. 4. Again, we observe a significant improvement of the objective function value for all operators T,Tred,TC, but now with less pronounced differences between the three operators. 7.4 Logistic regression Consider the following sparse optimization problem min w m i=1 log(1+exp(−yi·wTxi)) +ρw0,(35) which we refer to as the penalized maximum log-likelihood function. This estimator is applied to match a sigmoid-function to a set of measurements x1,...,xmand corresponding Bernoulli-variables y1,...,yn∈{−1,1}m, where additionally sparsity is promoted in the parameters wi. Replacing ·0by ·1in (35), we obtain a convex composite optimization problem, which can be tackled by FISTA or proximal BFGS methods, compare [24]. In our numerical test, we consider the problem gisette from the NIPS 2003 feature selection challenge, which was acquired from the LIBSVM-website.7The classification problem is high-dimensional (n=5000,m=6000)and was scaled to [−1,1]. Recall that applying either of the Newton-type methods with TC,Tor Tred to the gisette problem leads to a drastic increase in the dimensionality (in the case of TC: n=30,000). Computation was therefore outsourced to a faster PC and handled in Python. We computed an initial point x0by solving the 1-surrogate problem to (35) with FISTA. Running the three Newton-type methods with this initial point then lead to the results in Fig.5. The abbreviations TCx, Tx, Rx show the solutions found by the respective operators TC,Tand Tred. As one can see, all three of the operators lead to 7https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/. 123
108 C. Kanzow et al. Fig. 5 Comparison of target value f(x)+x0and sparsity x0for logistic regression. TCx, Tx and Rx show the solutions found by the operators TC,Tand Tred, respectively an improved sparsity x0and an improved function value f(x)+x0, meaning a better solution of the original problem (35). 8 Final remarks The aim of this paper was mainly to lay the theoretical foundation for two reformulations of the highly difficult sparse optimization problem SPO. In particular, it was shown that we get full equivalence of problem SPO with these two reformulations in terms of global and local minima. Moreover, the corresponding stationary conditions also coincide and corresponding second-order conditions are closely related. These results can be used to develop and investigate Lagrange–Newton-type methods for the numerical solution of problem SPO and the numerical results indicate that one can use these methods in order to get significant improvements of solutions obtained by some other techniques. The Lagrange–Newton-type methods, of course, are local in nature, but result quite naturally as a direct consequence of our theoretical considerations.8Our future research, however, will concentrate on the development of globally convergent methods based on our reformulations. Some preliminary results in this direction can already be found in [32]. 8https://pypi.org/project/yfinance/. 123
The sparse(st) optimization problem: reformulations... 109 Appendix: Proofs for Section 3 Proof of Lemma 3.1 (i) The definition of the index set I0(x)and the assumed feasibility of (x,y)implies n−eTy=n− i∈I0(x) yi− i/∈I0(x) yi=n− i∈I0(x) yi≥n− i∈I0(x) 1=x0. This also shows that equality holds if and only if yi=1 for all i∈I0(x). (ii) Recall that the function yi→ yi(yi−2)attains its (unique) minimum at yi=1 with corresponding minimal function value −1. The definition of the index set I0(x)and the feasibility of (x,y)therefore yield n i=1 yi(yi−2)= i∈I0(x) yi(yi−2)≥ i∈I0(x)−1=n− i∈I0(x) 1−n=x0−n, and equality holds if and only if yi=1 for all i∈I0(x). Proof of Lemma 3.2 Let (x∗,y∗)be a local minimum of SPOlin. We can fix x=x∗ and know that y∗solves max yeTys.t. yi=0,i/∈I0(x∗), y≤e. Similarly, let (x∗,y∗)be a local minimum of SPOsq. We can fix x=x∗and know that y∗solves min y n i=1 yi(yi−2)s.t. yi=0,i/∈I0(x∗). In both cases the statement follows. Proof of Proposition 3.3 Let ρ1and ρ2be two penalty parameters, and let x∗be a local minimum of min xf(x)+ρ1x0s.t. x∈X.(36) Assume that x∗is not a local minimum of min xf(x)+ρ2x0s.t. x∈X. Then there exists a sequence {xk}⊆Xwith xk→x∗such that f(xk)+ρ2 xk 0<f(x∗)+ρ2 x∗ 0∀k∈N.(37) 123
110 C. Kanzow et al. Note that xk 0≥x∗0holds for all ksufficiently large. First consider the case that there exists a subsequence such that xk 0=x∗0holds for all k∈K. Then we obtain f(xk)+ρ1 xk 0=f(xk)+ρ2 xk 0+(ρ1−ρ2) xk 0 <f(x∗)+ρ2 x∗ 0+(ρ1−ρ2) xk 0 =f(x∗)+ρ2 x∗ 0+(ρ1−ρ2) x∗ 0=f(x∗)+ρ1 x∗ 0 for all k∈K, contradicting the assumption that x∗is a local minimum of (36). In the other case, we have xk 0>x∗0and, therefore, x∗0+1≤ xk 0for almost all k∈N. Furthermore, by continuity of f, it follows that f(x∗)≤f(xk)+ρ2for all k sufficiently large. This implies f(x∗)+ρ2 x∗ 0≤f(xk)+ρ2+ρ2x∗0=f(xk)+ρ21+x∗0 ≤f(xk)+ρ2 xk 0, a contradiction to (37). Altogether, this completes the proof. Funding Open Access funding enabled and organized by Projekt DEAL. Data availability The data which was used to create the results within this manuscript is composed of 1. mixed-integer portfolio optimization problems by Frangioni and Gentile. At the moment of writing, they are publicly available (c.f. page 22, footnote 2). To our knowledge, the test instance are randomly generated. The specific instance for this manuscript lies with the authors and is available on request. 2. financial data collected with the yfinance python-package9. The acquired data was solely used to create values for the numerical experiment in Sect. 7.2.2. The data lies with the authors and is available on request. 3. compressive sensing test sets, which have been generated procedurally and randomly by MATLAB from a random seed. 4. the gisette classification problem, which originates from the NIPS 2003 feature selection challenge. The specific data used in section 7.4 is publicly available with the LIBSVM-library (c.f. page 26, footnote 8). Declarations Conflict of interest There are no conflict of interest to report. 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.: First-order methods in optimization. SIAM (2017) 123
The sparse(st) optimization problem: reformulations... 111 2. Ben Mhenni, R., Bourguignon, S., Ninin, J.: Global optimization for sparse solution of least squares problems. Optim. Methods Software 37(5), 1740–1769 (2021) 3. Bertsimas, D., Van Parys, B.: Sparse high-dimensional regression: exact scalable algorithms and phase transitions. Ann. Stat. 48(1), 300–323 (2020) 4. Bi, S., Pan, S., Sun, D.: A multi-stage convex relaxation approach to noisy structured low-rank matrix recovery. Math. Program. Comput. 12(4), 569–602 (2020) 5. Bonnans, J.F., Shapiro, A.: Perturbation Analysis of Optimization Problems. Springer, New York (2000) 6. Burdakov, O.P., Kanzow, C., Schwartz, A.: Mathematical programs with cardinality constraints: reformulation by complementarity-type conditions and a regularization method. SIAM J. Optim. 26(1), 397–425 (2016) 7. Candes, E., Tao, T.: Decoding by linear programming. IEEE Trans. Inf. Theory 51(12), 4203–4215 (2005) 8. ˇ Cervinka, M., Kanzow, C., Schwartz, A.: Constraint qualifications and optimality conditions for optimization problems with cardinality constraints. Math. Program. 160(1), 353–377 (2016) 9. Chen, S.S., Donoho, D.L., Saunders, M.A.: Atomic decomposition by basis pursuit. SIAM J. Sci. Comput. 20(1), 33–61 (1998) 10. Chen, X., Guo, L., Lu, Z., Ye, J.J.: An augmented Lagrangian method for non-Lipschitz nonconvex programming. SIAM J. Numer. Anal. 55(1), 168–193 (2017) 11. Clarke, F.H.: Optimization and nonsmooth analysis. SIAM (1990) 12. De Luca, T., Facchinei, F., Kanzow, C.: A semismooth equation approach to the solution of nonlinear complementarity problems. Math. Program. 75, 407–439 (1996) 13. Facchinei, F., Fischer, A., Kanzow, C.: Regularity properties of a semismooth reformulation of variational inequalities. SIAM J. Optim. 8(3), 850–869 (1998) 14. Facchinei, F., Pang, J.-S.: Finite-Dimensional Variational Inequalities and Complementarity Problems (Volume I). Springer, New York (2004) 15. Facchinei, F., Pang, J.-S. (eds.): Finite-Dimensional Variational Inequalities and Complementarity Problems (Volume II). Springer, New York (2004) 16. Feng, M., Mitchell, J.E., Pang, J.-S., Shen, X., Wächter, A.: Complementarity formulations of 0-norm optimization problems. Pac. J. Optim. 14(2), 273–305 (2018) 17. Fischer, A.: A special Newton-type optimization method. Optimization 24(3–4), 269–284 (1992) 18. Gaines, B.R., Kim, J., Zhou, H.: Algorithms for fitting the constrained lasso. J. Comput. Graph. Stat. 27(4), 861–871 (2018) 19. Ghilli, D., Kunisch, K.: A monotone scheme for sparsity optimization in pwith p∈(0,1].IFACPapersOnLine 50(1), 494–499 (2017) 20. Gotoh, J.-Y., Takeda, A., Tono, K.: DC formulations and algorithms for sparse optimization problems. Math. Program. 169(1), 141–176 (2018) 21. Hoheisel, T., Kanzow, C.: Stationary conditions for mathematical programs with vanishing constraints using weak constraint qualifications. J. Math. Anal. Appl. 337(1), 292–310 (2008) 22. Hoheisel, T., Kanzow, C., Schwartz, A.: Theoretical and numerical comparison of relaxation methods for mathematical programs with complementarity constraints. Math. Program. 137(1), 257–288 (2013) 23. Le Thi, H.A., Pham Dinh, T., Le, HM., Vo, X.T.: DC approximation approaches for sparse optimization. Technical report, (2014) 24. Lee, J.D., Sun, Y., Saunders, M.A.: Proximal Newton-type methods for minimizing composite functions. SIAM J. Optim. 24(3), 1420–1443 (2014) 25. Lu, Z., Zhang, Y.: Penalty decomposition methods for l0-norm minimization. Technical report (2012) 26. Marchi, A.D., Jia, X., Kanzow, C., Mehlitz, P.: Constrained composite optimization and augmented Lagrangian methods. Math. Program. (2023) 27. Markowitz, H.: Portfolio selection. J. Finance 7(1), 77–91 (1952) 28. Mehlitz, P.: Stationarity conditions and constraint qualifications for mathematical programs with switching constraints. Math. Program. 181(1), 149–186 (2020) 29. Nocedal, J., Wright, S.J.: Numerical Optimization, 2e edn. Springer, New York, NY (2006) 30. Qi, L.: Convergence analysis of some algorithms for solving nonsmooth equations. Math. Oper. Res. 18(1), 227–244 (1993) 31. Qi, L., Sun, J.: A nonsmooth version of Newton’s method. Math. Program. 58(1), 353–367 (1993) 32. Raharja, A.B.: Optimisation Problems with Sparsity Terms: Theory and Algorithms. PhD Thesis, Julius-Maximilians-Universität Würzburg (2020) 123
112 C. Kanzow et al. 33. Sharpe, W.F.: The sharpe ratio. J. Portf. Manag. 21(1), 49–58 (1994) 34. Tillmann, A.M., Bienstock, D., Lodi, A., Schwartz, A.: Cardinality minimization, constraints, and regularization: a survey. Technical report (2021) 35. Wang, L., Wang, J., Xiang, J., Yue, H.: A re-weighted smoothed 0-norm regularized sparse reconstructed algorithm for linear inverse problems. J. Phys. Commun. 3(7), 075004 (2019) 36. Yin, P., Lou, Y., He, Q., Xin, J.: Minimization of 1−2for compressed sensing. SIAM J. Sci. Comput. 37(1), A536–A563 (2015) 37. Zhao, C., Xiu, N., Qi, H., Luo, Z.: A Lagrange-Newton algorithm for sparse nonlinear programming. Math. Program. 195(1–2), 903–928 (2021) Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. 123