The sparse(st) optimization problem: reformulations, optimality, stationarity, and numerical results

Kanzow, Ch is ian; Schwa z, Alexand a; Weiß, Felix
A icle — Published Ve sion
The spa se(s ) op imiza ion p oblem: e o mula ions,
op imali y, s a iona i y, and nume ical esul s
Compu a ional Op imiza ion and Applica ions
P o ided in Coope a ion wi h:
Sp inge Na u e
Sugges ed Ci a ion: Kanzow, Ch is ian; Schwa z, Alexand a; Weiß, Felix (2024) : The spa se(s )
op imiza ion p oblem: e o mula ions, op imali y, s a iona i y, and nume ical esul s,
Compu a ional Op imiza ion and Applica ions, ISSN 1573-2894, Sp inge US, New Yo k, NY, Vol. 90,
Iss. 1, pp. 77-112,
h ps://doi.o g/10.1007/s10589-024-00625-0
This Ve sion is a ailable a :
h ps://hdl.handle.ne /10419/315246
S anda d-Nu zungsbedingungen:
Die Dokumen e au EconS o dü en zu eigenen wissenscha lichen
Zwecken und zum P i a geb auch gespeiche und kopie we den.
Sie dü en die Dokumen e nich ü ö en liche ode komme zielle
Zwecke e iel äl igen, ö en lich auss ellen, ö en lich zugänglich
machen, e eiben ode ande wei ig nu zen.
So e n die Ve asse die Dokumen e un e Open-Con en -Lizenzen
(insbesonde e CC-Lizenzen) zu Ve ügung ges ell haben soll en,
gel en abweichend on diesen Nu zungsbedingungen die in de do
genann en Lizenz gewäh en Nu zungs ech e.
Te ms o use:
Documen s in EconS o may be sa ed and copied o you pe sonal
and schola ly pu poses.
You a e no o copy documen s o public o comme cial pu poses, o
exhibi he documen s publicly, o make hem publicly a ailable on he
in e ne , o o dis ibu e o o he wise use he documen s in public.
I he documen s ha e been made a ailable unde an Open Con en
Licence (especially C ea i e Commons Licences), you may exe cise
u he usage igh s as speci ied in he indica ed licence.
h p://c ea i ecommons.o g/licenses/by/4.0/
Compu a ional Op imiza ion and Applica ions (2025) 90:77–112
h ps://doi.o g/10.1007/s10589-024-00625-0
The spa se(s ) op imiza ion p oblem: e o mula ions,
op imali y, s a iona i y, and nume ical esul s
Ch is ian Kanzow1
·Alexand a Schwa z2
·Felix Weiß1
Recei ed: 6 Augus 2023 / Accep ed: 5 No embe 2024 / Published online: 28 No embe 2024
© The Au ho (s) 2024
Abs ac
We conside he spa se op imiza ion p oblem wi h nonlinea cons ain s and an objec-
i e unc ion, which is gi en by he sum o a gene al smoo h mapping and an addi ional
e m de ined by he 0-quasi-no m. This e m is used o ob ain spa se solu ions, bu
di icul o handle due o i s noncon exi y and nonsmoo hness ( he spa si y-imp o ing
e m is e en discon inuous). The aim o his pape is o p esen wo e o mula ions o
his p og am as a smoo h nonlinea p og am wi h complemen a i y- ype cons ain s.
We show ha hese p og ams a e equi alen in e ms o local and global minima and
in oduce a p oblem- ailo ed s a iona i y concep , which u ns ou o coincide wi h he
s anda d KKT condi ions o he wo e o mula ed p oblems. In addi ion, a sui able
cons ain quali ica ion as well as second-o de condi ions o he spa se op imiza ion
p oblem a e in es iga ed. These a e hen used o show ha h ee Lag ange–New on-
ype me hods a e locally as con e gen . Nume ical esul s on di e en classes o es
p oblems indica e ha hese me hods can be used o d as ically imp o e spa se solu-
ions ob ained by some o he (globally con e gen ) me hods o spa se op imiza ion
p oblems.
Keywo ds Spa se op imiza ion ·Global minima ·Local minima ·S ong
s a iona i y ·Lag ange–New on me hod ·Quad a ic con e gence ·B-subdi e en ial
BCh is ian Kanzow
ch is ian.kanzow@uni-wue zbu g.de
Alexand a Schwa z
alexand a.schw[email p o ec ed]
Felix Weiß
elix.weiss@uni-wue zbu g.de
1Ins i u e o Ma hema ics, Uni e si y o Wü zbu g, Campus Hubland No d, Emil-Fische -S . 30,
97074 Wü zbu g, Ge many
2Facul y o Ma hema ics, Technical Uni e si y o D esden, Zellesche Weg 25, 01069 D esden,
Ge many
123
78 C. Kanzow e al.
1 In oduc ion
The spa se(s ) op imiza ion p oblem conside ed in his pape is he cons ained p ob-
lem
min
x (x)+ρx0s. . x∈X,(SPO)
wi h a pa ame e ρ>0, a easible se X(usually) gi en by
X={x∈Rn|g(x)≤0,h(x)=0}
wi h (a leas ) con inuous unc ions :Rn→R,g:Rn→Rm,h:Rn→Rpand
x0being he numbe o nonze o componen s xio he ec o x. Following s anda d
e minology, we call x0 he 0-no m h oughou his manusc ip hough i is no a
no m. Typical applica ions, whe e spa se solu ions o a gi en op imiza ion p oblem
a e equi ed, include comp essed sensing o spa se ep esen a ion o signals o image
da a, spa se po olio selec ion p oblems, ea u e selec ion in classi ica ion lea ning,
spa se eg ession o he spa se p incipal componen analysis, see [34, Sec ion 2] o
an o e iew and e e ences.
Following [23], he solu ion me hods o p oblems like SPO can be di ided in o he
ollowing h ee ca ego ies: (a) con ex app oxima ions, (b) noncon ex app oxima ions,
and (c) noncon ex exac e o mula ions.
The mos common con ex app oxima ion echnique uses he 1-no m ins ead o
he 0-no m in SPO. An o e iew on such 1-su oga e models, hei ad an ages and
solu ion app oaches can be ound in [34, Sec ion 4.1]. P o ided ha and X hem-
sel es a e con ex, he esul ing op imiza ion p oblem is con ex ( hough nonsmoo h)
and can he e o e be sol ed by a a ie y o me hods o con ex op imiza ion, see [1].
This app oach is e y popula , o example, in sol ing comp essed sensing p oblems.
On he o he hand, he e exis p ominen applica ions, whe e he 1-no m p o ides
absolu ely no spa si y (like he po olio op imiza ion p oblem used in ou nume ical
sec ion).
This d awback leads o o he spa si y imp o ing e ms ha esul in noncon-
ex app oxima ion schemes. A na u al choice is o use he p-quasi-no m o some
p∈(0,1), which is no longe con ex, bu s ill con inuous, see [19]. Despi e i s non-
con exi y, i he e a e no cons ain s (i.e., X=Rn), he esul ing p oblem can s ill be
sol ed ela i ely e icien ly by a p oximal- ype me hod. Fo addi ional cons ain s, one
can apply an augmen ed Lag angian- ype me hod and use he p oximal- ype app oach
o sol e he esul ing (uncons ained) subp oblems, see [10,26]. In p inciple, hese
echniques can also be used o he 0-no m, bu he discon inui y s ill causes some
ouble and ypically leads o slowly con e gen (p oximal- ype) g adien me hods,
see [26]. Ano he me hod belonging o he class o noncon ex app oxima ions is
he penal y decomposi ion me hod [25], which in oduces an addi ional a iable and
sol es he esul ing p oblem by an al e na ing minimiza ion echnique. Also he DC-
ype me hods (DC = di e ence o con ex) desc ibed in [23] esul in a noncon ex
app oxima ion which is shown o be exac unde some addi ional assump ions, see
also he DC- e o mula ion o he 0-no m om [20] ( his e o mula ion, howe e , is
123
The spa se(s ) op imiza ion p oblem: e o mula ions... 79
applied o ca dinali y-cons ained p oblems whe e he 0- e m is no in he objec i e
unc ion bu in he cons ain s, see below o a mo e de ailed discussion).
Finally, ega ding he class (c) o exac noncon ex e o mula ions, he e a e, o
he bes o ou knowledge, s ill jus a e y ew pape s p o iding such e o mula ions.
A na u al choice is o use a mixed-in ege p og am, c . e o mula ion MIP.Thisis
use ul o inding spa se solu ions o – o en quad a ic – p oblems, whose dimension
is no oo la ge, and allows, in p inciple, o compu e a global minimum, see e.g.
[2]. By modi ying he objec i e unc ion wi h a sui able egula izing e m, c. . [3],
also la ge p oblem dimensions can be handled. Fo nonlinea p og ams o la ge-scale
p oblems, howe e , his ypically leads o an in ac able e o mula ion. One al e na i e
app oach is he complemen a i y- ype e o mula ion sugges ed in [16], see also [4] o
a simila app oach in he con ex o low- ank ma ix eco e y, which can be shown o
be comple ely equi alen o he o iginal spa se op imiza ion p oblem SPO. The ocus
o he pape [16], howe e , is sligh ly di e en .
Mo e p ecisely, in his pape , we p esen wo e o mula ions o he gene al spa se
op imiza ion p oblem SPO. These e o mula ions a e in oduced in Sec . 2, and
pa ially mo i a ed by a ela ed app oach om [6,8] o ca dinali y-cons ained
op imiza ion p oblems, c . he co esponding discussion in Sec .2. One o he wo
e o mula ions is exac ly he one om [16] ha we al eady men ioned p e iously.
No e ha he subsequen esul s shown o ou wo e o mula ed p oblems a e e en
new o he app oach om [16]. In pa icula , we e i y in Sec .3 ha p oblem SPO
and ou wo e o mula ions a e equi alen in e ms o bo h local and global minima
an obse a ion no s a ed in [16]. We u he s ess ha he ela ed app oaches o
ca dinali y-cons ained p oblems [6,8] yield a comple e equi alence wi h espec o
global minima only, no wi h espec o local minima. The ull equi alence be ween
bo h global nad local minima in he case o SPO is he e o e a qui e su p ising and
imp essi e obse a ion. Sec ion3in oduces a p oblem- ailo ed s ong s a iona i y
concep and a co esponding cons ain quali ica ion and shows ha hese co espond
o he s anda d KKT condi ions and a s anda d cons ain quali ica ion o he wo
e o mula ed p oblems. We hen discuss sui ably adap ed second-o de condi ions in
Sec .5.
Though he main goal o his pape is o lay he ounda ions o wo exac non-
con ex e o mula ions o he spa se op imiza ion p oblem SPO, he co esponding
discussion leads, in a e y na u al way, o Lag ange–New on- ype me hods o he
solu ion o SPO, see Sec .6. Like all New on- ype me hods, his is p ima ily a locally
( as ) con e gen algo i hm, whe eas a cen al di icul y o he solu ion o spa se op i-
miza ion p oblems is o design sui able globally con e gen me hods. Ne e heless,
he co esponding nume ical esul s in Sec .7indica e ha he Lag ange–New on- ype
me hods can be used o ob ain signi ican imp o emen s o e solu ions calcula ed by
o he (globally con e gen ) spa se sol e s. We close wi h some inal ema ks in Sec .8.
No a ion: Th oughou his manusc ip , ei∈Rndeno es he i- h uni ec o , whe eas
e:= (1,...,1)T∈Rnis he all-one ec o . Gi en x∈Rnand x∗∈X, we de ine he
index se s
I0(x):= {i|xi=0}and Ig(x∗):= {i|gi(x∗)=0}
123
80 C. Kanzow e al.
o ze o componen s o xand ac i e inequali y cons ain s a x∗, espec i ely. Fo an
a bi a y ec o x, we w i e diag(x) o he co esponding diagonal ma ix, whose
diagonal en ies a e gi en by he elemen s o x. Gi en wo ec o s x,y∈Rn, he
Hadama d (elemen wise) p oduc is deno ed by x◦y, i.e., he elemen s o his ec o
a e gi en by xi·yi o all i=1,...,n.
2 Two smoo h e o mula ions o SPO
In his sec ion we de i e wo smoo h e o mula ions o SPO and show ha he local
and global minima o hese e o mula ed p oblems coincide wi h he local and global
minima o he o iginal spa se op imiza ion p oblem SPO. One o hese e o mula ions
is al eady known om [16], whe eas he o he one is new and will be mo e sui ed
o ou nume ical expe imen s la e on. No e ha he esul s s a ed in his manusc ip
o he known o mula ion om [16] a e s ill new and no con ained in ha e e ence.
Th oughou his sec ion, we only equi e ,g,h o be con inuous.
Le us conside he spa se op imiza ion p oblem om SPO wi h an a bi a y se
X⊆Rn. Fo any x∈Rn, de ine a co esponding bina y a iable y∈{0,1}nby
se ing yi:= 0 o xi= 0 and yi:= 1 o xi=0. Using his y, we can calcula e he
0-no m o xas
x0=
xi=0
1=
n

i=1
(1−yi)=n−eTy.
Thus, we could ew i e p oblem SPO by he ollowing mixed-in ege p oblem
min
x,y (x)+ρ(n−eTy)s. . x∈X,x◦y=0,y∈{0,1}n.(MIP)
In o de o mo e o a con inuous op imiza ion p oblem, we disca d he bina y con-
s ain s on y. We need o e ain he cons ain y≤e, because o he wise he objec i e
unc ion o (MIP) does no admi a minimum. This leads us o he e o mula ion
min
(x,y) (x)+ρ(n−eTy)s. . x∈X,x◦y=0,y≤e.(SPOlin)
Since he auxilia y a iable yen e s he objec i e unc ion linea ly, we deno e his
p oblem SPOlin. This is in con as o ou second o mula ion
min
(x,y) (x)+ρ
2
n

i=1
yi(yi−2)s. . x∈X,x◦y=0 (SPOsq)
called SPOsq, since we add a quad a ic e m o he objec i e unc ion. No e ha his
quad a ic e m is designed in such a way ha i anishes, whene e xi= 0 (due o he
complemen a i y- ype cons ain ), and ha i a ains i s minimum a yi=1 whene e
his a iable is uncons ained, i.e., o all iwi h xi=0., see Fig. 1.
123

The spa se(s ) op imiza ion p oblem: e o mula ions... 81
-1 0 1 2 yi
-1
1
−yi
-1 0 1 2 yi
-1
1yi(yi−2)
Fig. 1 Compa ison o he e ms −yiused in SPOlin and yi(yi−2)used in SPOsq
P oblem SPOlin co esponds o he e o mula ion al eady in oduced in [16],
whe eas SPOsq seems o be new. Obse e ha , i he easible se Xcon ains no
inequali y cons ain s, hen he new o mula ion SPOsq boils down o an equali y-
cons ained op imiza ion p oblem, in con as o SPOlin, which s ill includes he
inequali ies y≤e. This obse a ion is pa icula ly use ul in ou se ing since, la e , we
will apply a Lag ange–New on- ype me hod in o de o sol e he spa se op imiza ion
p oblem.
Be o e we ake a close look a he elaxed p oblems SPOlin and SPOsq, we would
like o b ie ly discuss he ela ion o he spa se p oblem SPO and i s elaxa ions o he
wo closely ela ed p oblem classes o ca dinali y-cons ained p oblems
min
x (x)s. . x∈X,x0≤κ
and ca dinali y minimiza ion p oblems
min
xx0s. . x∈X, (x)≤δ,
whe e κ∈Nand δ∈Ra e gi en cons an s. Using he same ideas as abo e, hese
p oblems can be elaxed o he con inuous p oblems
min
x,y (x)s. . x∈X,x◦y=0,y≤e,n−eTy≤κ,
min
x,yn−eTys. . x∈X,x◦y=0,y≤e, (x)≤δ,
espec i ely. As we show below, o p oblem SPO he wo elaxa ions a e equi alen o
he o iginal p oblem in e ms o global and local minima. Using he same a gumen s,
i is also possible o show his equi alence o he ca dinali y minimiza ion p oblem.
Howe e , o he ca dinali y-cons ained p oblem i is known, see [6], ha only he
global minima o he o iginal p oblem and i s elaxa ion coincide, bu he elaxa ion
may ha e addi ional local minima.
Fu he mo e, one may be emp ed o iew p oblem SPO as a penal y e o mula ion
o ei he o he o he wo p oblems. Howe e , while a solu ion x∗o SPO is always a
solu ion o he o he wo p oblems wi h κ:= x∗0o δ:= (x∗), espec i ely, he
opposi e implica ion is in gene al no ue. This means ha solu ions o he ca dinali y-
cons ained p oblem o ca dinali y minimiza ion p oblem canno always be eco e ed
123
82 C. Kanzow e al.
as solu ions o SPO. Mo e de ails on hese ela ions can be ound in [34, P oposi ion
1.1].
3 P ope ies o e o mula ions
In he momen , i is no clea why we can iew he p og ams SPOlin and SPOsq as
e o mula ions o he gi en nonsmoo h and discon inuous spa se op imiza ion p ob-
lem SPO. Bu , as we show below, hese h ee p og ams a e comple ely equi alen in
e ms o bo h global and local minima. E en hei co esponding s a iona y poin s
coincide, see Sec . 4 o de ails on his. Some o s a emen s p esen ed in Sec . 3can
be p o en in an elemen a y and s aigh o wa d manne . Fo he sake o comple ion
hey ha e hus been mo ed o he appendix.
In o de o e i y hese s a emen s, we i s need some p elimina y esul s. No e
ha xis ob iously easible o he gi en p oblem SPO i and only i he e exis s a
sui able ec o y∈Rnsuch ha (x,y)is easible o SPOlin o SPOsq. Fu he mo e,
we ha e he ollowing ela ions o easible poin s o hese wo p og ams.
Lemma 3.1 The ollowing s a emen s hold:
(i) Le (x,y)be easible o SPOlin. Then x0≤n−eTy,wi h equali y i and
only i yi=1 o all i ∈I0(x).
(ii) Le (x,y)be easible o SPOsq. Then x0−n≤n
i=1yi(yi−2), wi h equali y
i and only i yi=1 o all i ∈I0(x).
P oo c . appendix. 
The ollowing esul shows ha he cons ella ion yi=1 o i∈I0(x)is indeed he
mos p e e able one.
Lemma 3.2 Le (x∗,y∗)be a local minimum o SPOlin o SPOsq. Then we ha e
y∗
i=1 o all i ∈I0(x∗).
P oo c . appendix. 
Nex , we show ha he se o local minima o he spa se op imiza ion p oblem SPO
is independen o he pa icula choice o he penal y pa ame e . No e ha , his is due
o he discon inui y o he 0-no m and ha a simila esul o spa se op imiza ion
p oblems in ol ing he 1-no m, e.g., does no hold. This obse a ion may ac ually
be iewed as an ad an age o he 0-no m, since his implies ha a sui able choice
o he penal y pa ame e is much less c i ical o he 0- o mula ion o he spa se
op imiza ion p oblem han o he (con inuous) o mula ions like he one based on he
1-no m o he q-quasi-no m o q∈(0,1).
P oposi ion 3.3 Le x∗be a local minimum o SPO wi h penal y pa ame e ρ1>0.
Then x∗is also a local minimum o SPO o any o he penal y pa ame e ρ2>0.
P oo c . appendix. 
123
The spa se(s ) op imiza ion p oblem: e o mula ions... 83
The p e ious s a emen also holds o he wo e o mula ed p og ams SPOlin and
SPOsq. This is a consequence, e.g., o he ollowing esul , which s a es ha x∗is a
local minimum o he spa se op imiza ion p oblem SPO i and only i he e exis s a
ec o y∗such ha he pai (x∗,y∗)is a local minimum o ei he SPOlin o SPOsq.
Theo em 3.4 (Equi alence o Local Minima) The ollowing s a emen s a e equi alen :
(i) x∗is a local op imum o SPO.
(ii) The e exis s y∗such ha (x∗,y∗)is a local op imum o SPOlin.
(iii) The e exis s y∗such ha (x∗,y∗)is a local op imum o SPOsq.
P oo No ice ha , by Lemma 3.2,y∗has o be o he o m
y∗
i=1 o i∈I0(x∗),
0 o he wise, (*)
in o de o (x∗,y∗) o be a local minimum o SPOlin o SPOsq.
(i)⇒ (ii):Le x∗be a local minimum o SPO and le y∗be de ined as in (*). Then
(x∗)+ρn−eTy∗= (x∗)+ρ
x∗
0≤ (x)+ρx0≤ (x)+ρn−eTy
o all easible (x,y)wi h xsu icien ly close o x∗, whe e he i s equali y and he
las inequali y ollow om Lemma 3.1(i).
(ii)⇒ (i):Le (x∗,y∗)be he local minimum o SPOlin wi h y∗as in (*). Assume
ha x∗is no a local minimum o SPO. Then he e exis s a sequence {xk}⊆Xsuch
ha xk→x∗and
(xk)+ρ

xk

0< (x∗)+ρ
x∗
0∀k∈N.(1)
Recall ha 
xk
0≥x∗0holds o all ksu icien ly la ge. Hence we ei he ha e a
subsequence {xk}Ksuch ha 
xk
0=x∗0holds o all k∈K,o x∗0+1≤

xk
0is ue o almos all k∈N. In he o me case, i ollows ha (xk,y∗)is
easible o SPOlin, hence we ob ain om Lemma 3.1(i)and he minimali y o (x∗,y∗)
o SPOlin ha
(xk)+ρ

xk

0= (xk)+ρ
x∗
0
= (xk)+ρ(n−eTy∗)≥ (x∗)+ρ(n−eTy∗)
= (x∗)+ρ
x∗
0,
which con adic s (1). O he wise, we ha e x∗0+1≤
xk
0and, by con inui y,
also (x∗)≤ (xk)+ρ o all k∈Nsu icien ly la ge, which, in u n, gi es
(xk)+ρ

xk

0≥ (xk)+ρ+ρ
x∗
0≥ (x∗)+ρ
x∗
0.
123
84 C. Kanzow e al.
Hence, also in his si ua ion, we ha e a con adic ion o (1).
(i)⇒ (iii):Le x∗be a local minimum o SPO. Then x∗is also a local minimum
o he op imiza ion p oblem
min (x)+ρ
2x0−ns. . x∈X,(2)
since, by P oposi ion 3.3, we can modi y he penal y pa ame e , and since adding a
cons an o he objec i e unc ion does no change he loca ion o he local minima.
Now, le y∗be de ined as in s a emen (*). Then
(x∗)+ρ
2
n

i=1
y∗
iy∗
i−2= (x∗)+ρ
2
x∗
0−n≤ (x)+ρ
2x0−n
≤ (x)+ρ
2
n

i=1
yiyi−2,
o all easible (x,y)wi h xsu icien ly close o x∗, whe e he i s equali y and he
las inequali y ollow om Lemma 3.1(ii).
(iii)⇒ (i):Le (x∗,y∗)be a local minimum o SPOsq wi h y∗as in (*). Assume
ha x∗is no a local minimum o SPO. Then x∗is no a local minimum o (2). Hence,
he e exis s a sequence {xk}⊆Xsuch ha xk→x∗and
(xk)+ρ
2

xk

0−n< (x∗)+ρ
2
x∗
0−n∀k∈N.(3)
Recall ha 
xk
0≥x∗0holds o all ksu icien ly la ge. Thus, once again, we
ei he ha e a subsequence {xk}Ksuch ha 
xk
0=x∗0holds o all k∈K,
o x∗0+1≤
xk
0is ue o almos all k∈N. In he o me case, i ollows
ha (xk,y∗)is easible o SPOsq, hence we ob ain om Lemma 3.1(ii)and he
minimali y o (x∗,y∗) o SPOsq ha
(xk)+ρ
2

xk

0−n= (xk)+ρ
2
x∗
0−n= (xk)+ρ
2
n

k=1
y∗
iy∗
i−2
≥ (x∗)+ρ
2
n

k=1
y∗
iy∗
i−2= (x∗)+ρ
2
x∗
0−n,
which con adic s (3). O he wise, we ha e x∗0+1≤
xk
0and, by con inui y,
also (x∗)≤ (xk)+ρ
2 o all k∈Nsu icien ly la ge, which, in u n, gi es
(xk)+ρ
2

xk

0−n≥ (xk)+ρ
2+ρ
2
x∗
0−n≥ (x∗)+ρ
2
x∗
0−n.
Hence, also in his si ua ion, we ha e a con adic ion o (3). 
123
The spa se(s ) op imiza ion p oblem: e o mula ions... 91
Theo em 5.3 (Second-O de Su iciency Condi ions) Le (x∗,λ
∗,μ
∗)be an S-
s a iona y poin such ha (s ong) SP-SOSC holds in x∗. Then he ollowing s a emen s
hold:
(i) (S ong) SOSC o SPOlin holds a (x∗,y∗,λ
∗,μ
∗,γ∗,σ∗)wi h (y∗,γ∗,σ∗)
de ined in P oposi ion 4.1.
(ii) (S ong) SOSC o SPOsq holds a (x∗,y∗,λ
∗,μ
∗,γ∗)wi h (y∗,γ∗)de ined in
P oposi ion 4.1.
(iii) x∗is a local minimize o SPO.
P oo Fo a gi en S-s a iona y poin (x∗,λ
∗,μ
∗)le y∗,γ∗, and σ∗be chosen as in
P oposi ion 4.1 and de ine z:= (x,y). The Hessian ma ices o he Lag angians o
p oblems SPOlin and SPOsq wi h espec o za e gi en by
∇2
zzLlin(x∗,y∗,λ
∗,μ
∗,γ∗,σ∗)=∇2
xxLSP(x∗,λ
∗,μ
∗)diag(γ ∗)
diag(γ ∗)0and
∇2
zzLsq(x∗,y∗,λ
∗,μ
∗,γ∗)=∇2
xxLSP(x∗,λ
∗,μ
∗)diag(γ ∗)
diag(γ ∗)ρIn,
espec i ely, whe e Indeno es he iden i y ma ix in Rn×n. Since y∗
i=1 and σ∗
i=
ρ>0 o all i∈I0(x∗), we ob ain he ollowing c i ical cones o he smoo h
p oblems SPOlin and SPOsq, espec i ely:
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, simila ly, he c i ical 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 e 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∗)}.
Fo a ec o d=(dx,dy)T, we ob ain
dx
dyT
∇2
zzLsq dx
dy=dx
dyT
∇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 nonze o ec o . Then we ha e
dx∈CSPO(x∗,λ
∗), dy=0.
In pa icula , his implies dx= 0. Acco ding o (22), he SP-SOSC immedia ely
implies claim (i). The p oo o s ong SOSC is analogous.
Assume d=(dx,dy)T∈Csq(x∗,λ
∗)is a non i ial ec o . I holds
dx∈CSPO(x∗,λ
∗), (dy)i=0,i/∈I0(x∗).
A leas one o he wo ec o s dx,dyis nonze o and we know dx◦dy=0. Hence SP-
SOSC implies (ii), acco ding o inequali y (22). S ong SOSC can again be e i ied
analogously.
Finally, he alidi y o SOSC o ei he SPOlin o SPOsq immedia ely yields (iii)
due o he equi alence o local minima. 
We nex s a e a second-o de necessa y op imali y condi ion o he spa se op imiza ion
p oblem SPO, which can be de i ed ia he ela ion o he co esponding second-
o de condi ions o one o he wo smoo h e o mula ions SPOlin o SPOsq.No e
ha his necessa y condi ion will no be used la e , bu is s a ed he e o he sake o
comple eness.
Theo em 5.4 (Second-O de Necessa y Condi ion) Le x∗be a local minimum o SPO
sa is ying SP-LICQ. Then he e exis unique mul iplie s (λ∗,μ
∗)such ha (x∗,λ
∗,μ
∗)
is an S-s a iona y poin o SPO sa is ying he second-o de necessa y condi ion
dT∇xxLSP(x∗,λ
∗,μ
∗)d≥0,∀d∈CSPO(x∗,λ
∗).
P oo The exis ence and uniqueness o he mul iplie s (λ∗,μ
∗)such ha he iple
(x∗,λ
∗,μ
∗)sa is ies he S-s a iona i y condi ions is an immedia e consequence o
Theo ems 4.3 and 4.5.
123
The spa se(s ) op imiza ion p oblem: e o mula ions... 93
Fu he mo e, we know om hese esul s ha he e exis (uniquely de ined) ec o s
y∗and σ∗such ha (x∗,y∗,λ
∗,μ
∗,σ∗)is a KKT poin o SPOsq sa is ying s anda d
LICQ, and wi h (x∗,y∗)being a local minimize o SPOsq, c . Theo em 3.4. Hence
he s anda d second-o de necessa y op imali y condi ion holds o SPOsq, i.e., we
ha e
dx
dyT∇2
xxLSP(x∗,μ
∗,λ
∗)diag(γ ∗)
diag(γ ∗)ρIndx
dy≥0,∀dx
dy∈Csq(x∗,λ
∗).
This is equi alen o
(dx)T∇2
xxLSP(x∗,μ
∗,λ
∗)dx+ρ
dy

2
2≥0,∀dx
dy∈Csq(x∗,λ
∗), (23)
whe e we used he ac ha (dx)i·(dy)i=0, c . he p e ious p oo . Now i is easy o
see ha any ec o d=(dx,dy)Twi h dx∈CSPO(x∗,λ
∗)and dy=0 is con ained
in Csq(x∗,λ
∗).In iewo (23), his di ec ly yields
(dx)T∇2
xxLSP(x∗,μ
∗,λ
∗)dx≥0,∀dx∈CSPO(x∗,λ
∗).
This comple es he p oo . 
No e ha he e exis mo e gene al second-o de condi ions o s anda d nonlinea
p og ams, see, e.g., [5]. In p inciple, i is possible o ansla e hese condi ions also
o p oblem- ailo ed second-o de op imali y condi ions o he spa se op imiza ion
p oblem SPO due o i s ela ion o he s anda d second-o de op imali y condi ions o
one o he e o mula ed smoo h p oblems SPOlin o SPOsq. We omi he co esponding
de ails.
6 Lag ange–New on- ype me hods
The aim o his sec ion is o p esen some Lag ange–New on- ype me hods o he
(local) solu ion o he spa se op imiza ion p oblem SPO. The idea is o use one o
ou smoo h e o mula ions and o apply a New on- ype me hod o he co esponding
KKT condi ions. In p inciple, we could ake ei he he e o mula ion SPOlin o he
one om SPOsq. He e we decide o conside he e o mula ion SPOsq which, in pa -
icula , has he ad an age ha he co esponding KKT condi ions consis o nonlinea
equa ions only, i he o iginal p oblem SPO con ains no inequali ies. This obse a ion
migh be use ul o Lag ange–New on- ype app oaches. Ne e heless, he heo y also
co e s he case whe e inequali y cons ain s a e p esen .
Mo e p ecisely, we conside h ee di e en New on- ype me hods: Fi s , we ake
he ull KKT sys em o SPOsq and in es iga e he local con e gence p ope ies o a
co esponding nonsmoo h New on me hod applied o his sys em. Second, we conside
a educed a ian o his me hod which elimina es he y- a iables and show ha i
con e ges unde he same se o assump ions as he p e ious app oach. Thi d, we deal
123
94 C. Kanzow e al.
wi h a me hod which ies o o e come some singula i y p oblems o some classes o
spa se op imiza ion p oblems, which include nonnega i i y cons ain s.
Bu be o e we ge in o he de ails, le us b ie ly ecall he cen al ideas behind a
nonsmoo h e sion o he New on me hod.
Rema k 6.1 (Nonsmoo h New on’s me hod in a nu shell) Gi en a mapping T:Rn→
Rn, we can y o compu e a oo o Twi h a New on- ype i e a ion scheme
zk+1=zk−H−1
kT(zk)∀k=0,1,2,...,
whe e Hk∈Rn×nis a ma ix ypically ela ed o he de i a i e o Ta zk.
I we wan o apply his o he KKT sys em o SPOsq,we i s ha e o e o mula e
he condi ions
λi≥0,gi(x)≤0,λ
igi(x)=0∀i=1,...,m
in o mequali y cons ain s. This can be achie ed by using a sui able NCP- unc ion
ϕ:R2→R, which is de ined by he p ope y
φ(a,b)=0⇐⇒ a≥0,b≥0,ab =0.
Two p ominen examples a e he minimum unc ion and he Fische -Bu meis e unc-
ion
φm(a,b):= min{a,b}and φFB(a,b):= a2+b2−a−b.
De ining he unc ion g:Rn×Rm→Rmcomponen wise as
(g)i(x,λ)=φ(−gi(x), λi),
we can hus eplace he condi ions on gand λby he equa ion sys em g(x,λ)=0.
Howe e , mos NCP unc ions a e (by design) nonsmoo h a leas in he o igin.
We hus canno use he Jacobian Hk=T(zk)as in he classical New on’s me hod,
bu ins ead need some ools om nonsmoo h analysis. I he mapping Tis a locally
Lipschi z con inuous mapping, hen Rademache ’s Theo em implies ha Tis almos
e e ywhe e di e en iable. Hence he se
∂BT(z):= H∃{zk}⊆DT:zk→zand T(zk)→H
is nonemp y and bounded, whe e DTdeno es he se o di e en iable poin s o T.
The se ∂BT(z)is called he B-subdi e en ial o Tin zand i s con ex hull gi es
he gene alized Jacobian ∂T(z)by Cla ke [11]. A poin zis called BD- egula ,i all
elemen s in ∂BT(z)a e nonsingula .
I we use a ma ix Hk∈∂BT(zk)in he New on- ype i e a ion scheme, he esul ing
nonsmoo h New on’s me hod is known o be locally supe linea ly o e en quad a ically
con e gen o a oo z∗, i his oo z∗is BD- egula and Tsa is ies an addi ional
123
The spa se(s ) op imiza ion p oblem: e o mula ions... 95
smoo hness p ope y called semismoo hness and s ong semismoo hness, espec i ely.
Fo he p ecise de ini ions and p oo s o he p e ious s a emen s, he in e es ed eade
is e e ed o he pape s [30,31] and he monog aph [14].
Th oughou his sec ion, we assume ha all unc ions ,g,ha e wice con inuously
di e en iable. Fu he mo e, φdeno es ei he he minimum o he Fische -Bu meis e
unc ion, unless we s a e some hing else explici ly. Then i is known ha he h ee
ope a o s Tused below a e semismoo h. They a e s ongly semismoo h i , in addi ion,
he second-o de de i a i es o ,g,ha e locally Lipschi z con inuous. In o de o
e i y he local as con e gence o he nonsmoo h New on me hod applied o T(z)=
0, i hus su ices o p o e BD- egula i y in he oo z∗. Fo mo e de ails on his, we
e e he eade , o ins ance, o [15].
The i s New on- ype me hod p esen ed in his sec ion uses he ope a o
T(x,y,λ,μ,γ):= ⎛
⎜
⎜
⎜
⎜
⎝
∇xLSP(x,λ,μ)+γ◦y
ρ(y−e)+γ◦x
g(x,λ)
h(x)
x◦y
⎞
⎟
⎟
⎟
⎟
⎠
,
whe e gis de ined as in Rema k 6.1. Due o he de ining p ope y o an NCP-
unc ion, i ollows ha (x∗,y∗,λ
∗,μ
∗,γ∗)is a KKT poin o he e o mula ed
p oblem SPOsq i and only i i sol es he (in gene al nonsmoo h) sys em o equa ions
T(x,y,λ,μ,γ)=0.
In o de o ensu e as local con e gence o he nonsmoo h New on me hod applied
o he sys em T(z)=0, i su ices o show ha a solu ion z∗=(x∗,y∗,λ
∗,μ
∗,γ∗)
he eo is BD- egula unde sui able assump ions.
Theo em 6.2 Le z∗=(x∗,y∗,λ
∗,μ
∗,γ∗)be a solu ion o T (z)=0such ha he
ollowing assump ions hold:
(i) SP-LICQ is sa is ied a x∗.
(ii) S ong SP-SOSC is sa is ied a (x∗,λ
∗,μ
∗).
Then z∗is a BD- egula poin o T .
P oo Based on ou p e ious esul , he s a emen can be aced back o exis ing esul s
in he li e a u e. Since z∗is a KKT poin o SPOsq, we know ha he bi-ac i e se
{i|x∗
i=0=y∗
i}is emp y. The e o e, i ollows om assump ion (i)and Theo em 4.5
ha o dina y LICQ holds o SPOsq a z∗. Simila ly, assump ion (ii)and Theo em 5.3
imply ha he s ong second-o de su iciency condi ions holds o SPOsq a z∗. S an-
da d esul s on he local con e gence o nonsmoo h New on me hods hen imply ha
all elemen s H∈∂BT(z∗)a e nonsingula , see, e.g., [13,14,17]. 
We nex conside a educed o mula ion o he sys em T(z)=0. To his end, no e ha
T(z)=0 immedia ely gi es
y=e−γ◦x
ρ,(24)
123
96 C. Kanzow e al.
c . (15). Hence, elimina ing he a iable yin he de ini ion o Tby eplacing i wi h
he abo e exp ession, we ob ain he educed ope a o
T ed(x,λ,μ,γ)=⎛
⎜
⎜
⎝
∇xLSP(x,λ,μ)+γ◦(e−γ◦x
ρ)
(−g(x), λ)
h(x)
x◦(e−γ◦x
ρ)
⎞
⎟
⎟
⎠
,
which is independen o y. In iew o i s de i a ion, i s ill holds ha any ze o o
T ed yields a KKT poin o SPOsq and ice e sa, whene e he a iable yis de ined
as abo e. In o de o locally sol e he KKT sys em o SPOsq, we can he e o e,
al e na i ely, apply a nonsmoo h New on me hod o he sys em T ed(w) =0, whe e
w=(x,λ,μ,γ). The cen al poin o he local as con e gence o his app oach is
again he BD- egula i y o a solu ion w∗.
Theo em 6.3 T is BD- egula in (x,y,λ,μ,γ)wi h y =(e−γ◦x/ρ) i and only i
T ed is BD- egula in (x,λ,μ,γ).
P oo Le w=(x,λ,μ,γ) and z=(x,y,λ,μ,γ) wi h y=e−γ◦x/ρ.The
de ini ion o he B-subdi e en ial hen yields
H∈∂BT(z)⇐⇒ H=⎛
⎜
⎜
⎜
⎜
⎝
∇2
xxLSP(x,λ,μ) diag(γ ) g(x)Th(x)Tdiag(y)
diag(γ ) ρIn0 0 diag(x)
J1g0J2g00
h(x)0000
diag(y)diag(x)00 0
⎞
⎟
⎟
⎟
⎟
⎠
,
and, simila ly, H ed ∈∂BT ed(w) i and only i
H ed =⎛
⎜
⎜
⎜
⎝
∇2
xxLSP(x,λ,μ)−diag(γ )2
ρg(x)Th(x)Tdiag(e−2γ◦x
ρ)
J1gJ2g00
h(x)00 0
diag(e−2γ◦x
ρ)00−diag(x)2
ρ
⎞
⎟
⎟
⎟
⎠
,
wi h (J1g,J2g)∈∂Bg(x,λ). Assume wis BD- egula o T ed.Le H∈∂BT(z)
and conside he sys em
Hd =0 wi h app op ia ely pa i ioned d=(dx,dy,dλ,dμ,dγ). (25)
123

The spa se(s ) op imiza ion p oblem: e o mula ions... 97
Sol ing o dyexplici ly 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
ρ)
J1gJ2g00
h(x)00 0
diag(e−2γ◦x
ρ)00−diag(x)2
ρ
⎞
⎟
⎟
⎟
⎠
⎛
⎜
⎜
⎝
dx
dλ
dμ
dγ
⎞
⎟
⎟
⎠=0.
(26)
BD- egula i y o T ed implies (dx,dλ,dμ,dγ)=(0,0,0,0)and he e o e also dy=
0. Hence His nonsingula . Since his holds o a bi a y H∈∂BT(z), heBD-
egula i y o Tin z ollows.
The p oo o he con e se s a emen is simila : Assume T ed is no BD- egula in w.
Then he e is a singula ma ix H∗
ed ∈∂BT ed(w∗), i.e., he e exis s (J1∗
g,J2∗
g)∈
∂Bg(x∗,λ
∗)such ha he co esponding elemen H∗
ed is singula . This means ha
he e is a non i ial elemen d0=(d1
0,d3
0,d4
0,d5
0)T∈ke (H∗
ed). Se ing d2
0:=
1
ρ(−γ◦d1
0−x◦d5
0)and e e sing he p e ious a gumen s, we ob ain a singula
elemen in ∂BT(z).
No e ha he assump ion y=(e−γ◦x/ρ) used in Theo em 6.3 holds au oma ically
a any KKT poin . Theo em 6.3 he e o e allows o ansla e he esul om Theo-
em 6.2 di ec ly o he educed ope a o T ed. A po en ial disad an age o he educed
o mula ion is he ac ha he eplacemen o he a iable yby he exp ession (24)
inc eases he nonlinea i y o he esul ing ope a o T ed.
Finally, we u n o a hi d New on- ype me hod o he solu ion o spa se op imiza-
ion p oblems SPO, whose easible se Xcon ains nonnega i i y cons ain s o some
o all a iables. Fo no a ional simplici y, we conside only he ully nonnega i e case
x≥0.
In ou gene al app oach, we ha e o iew hese cons ain s as pa o he inequali ies
g(x)≤0, which causes p oblems wi h he cons ain quali ica ion. SP-LICQ would
equi e he linea independence o he g adien ec o s −ei( esul ing om he con-
s ain xi≥0 as an inequali y) and ei( esul ing om he spa si y in he de ini ion o
SP-LICQ) o all i∈I0(x∗), which is ob iously impossible.
We can o e come his si ua ion in he ollowing way: In any local minimum o
SPOsq,weha ey≥0 acco ding o Lemma 3.2. Toge he wi h he cons ain x◦y=
0 and he nonnega i i y cons ain x≥0 we hus ob ain he ull complemen a i y
condi ions x≥0,y≥0,x◦y=0, which we can eplace by an addi ional NCP-
unc ion (x,y)=0 wi h i(x,y)=φ(xi,yi) o all i=1,...,n. The cons ain s
x≥0 hen do no need o be conside ed as a pa o he s anda d inequali y cons ain s
123
98 C. Kanzow e al.
g(x)≤0 any mo e. This mo i a es o conside he nonlinea sys em o equa ions
TC(x,y,λ,μ,γ)=0 wi h TC(x,y,λ,μ,γ):= ⎛
⎜
⎜
⎜
⎜
⎝
∇xLSP(x,λ,μ)+γ◦y
ρ(y−e)+γ◦x
g(x,λ)
h(x)
(x,y)
⎞
⎟
⎟
⎟
⎟
⎠
,
wi h wo NCP- unc ions g,. Then SP-LICQ is a easonable assump ion o his
e o mula ion, and he ollowing esul holds.
Theo em 6.4 Le z∗=(x∗,y∗,λ
∗,μ
∗,γ∗)be a solu ion o TC(z)=0such ha he
assump ions o Theo em 6.2 hold. Then z∗is a BD- egula poin o TC.
P oo Fi s obse e ha TC(z∗)=0 implies T(z∗)=0, hence z∗is a KKT poin
o SPOsq. In iew o P oposi ion 4.1, we he e o e ha e ha he bi-ac i e se {i|x∗
i=
y∗
i=0}is emp y. This implies ha is con inuously di e en iable in a neighbo hood
o (x∗,y∗), wi h componen wise de i a i es gi en by ( ecall ha is de ined ei he
by he Fische -Bu meis e unc ion o by he minimum unc ion)
∇φ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 elemen HC∈∂BTC(z∗)can be w i en as:
HC=⎛
⎜
⎜
⎜
⎜
⎝
∇2
xxLSP(x∗,λ
∗,μ
∗)diag(γ ∗)g(x∗)Th(x∗)Tdiag(y∗)
diag(γ ∗)ρIn0 0 diag(x∗)
J1g0J2g00
h(x∗)0000
diag(cx)diag(cy)00 0
⎞
⎟
⎟
⎟
⎟
⎠
,
wi h cx,cysuch ha
((cx)i,(cy)i)∈{−1,1}×{0}i i∈I0(x∗),
{0}×{−1,1}o he wise,
and a bi a y (J1g,J2g)∈∂Bg(x∗,λ
∗). De ine
A:= I2n+m+p0
0diag
(cx+cy)◦(x∗+y∗),
and obse e ha Ais nonsingula . Then a simple calcula ion shows ha A·HC∈
∂BT(z∗). Since Ais nonsingula and all elemen s in ∂BT(z∗)a e nonsingula by
Theo em 6.2, i ollows ha HCis nonsingula . This comple es he p oo . 
123
The spa se(s ) op imiza ion p oblem: e o mula ions... 99
Though he hi d o mula ion using he ope a o TCis mainly designed o p oblems
ha ing addi ional nonnega i i y cons ain s, we can also apply his idea also o p ob-
lems wi hou hese nonnega i i y cons ain s, by spli ing he a iables x=x+−x−
in o hei posi i e and nega i e pa s x+x−≥0. Since his is a p e y s anda d app oach
also used in [16], we skip he co esponding de ails.
Some addi ional ema ks on he choice o he NCP- unc ion a e in o de . Assume
ha p oblem SPO has a easible se desc ibed by inequali y cons ain s and we choose
g(x,λ)=min{−g(x), λ},
o be unde s ood componen wisely. Then he lowe pa o ∂BT(z) eads
−diag(cx)g(x)0diag(cy)0
diag(y)diag(x)00

such ha he ma ix diag(cx), diag(cy)belongs o he subdi e en ial ∂Bmin{a,b}.
Then, in pa icula , i g(x)>0, we always ha e diag(cy)=0. Depending on he alues
o x,yand g(x)we may encoun e a singula i y. The si ua ion is e en wo se o he
ope a o TC. To his end, conside he minimum- unc ion min{x,y}as su oga e o
x◦yand assume we ha e an i e a e (xk,yk)wi h yk
i>xk
i(which is, o ins ance, he
case in he po olio se ing, since, in gene al, we ini ialize y0
i=1 o all i=1,...,n).
Then, wi h any equali y cons ain s hin place, he lowe pa o ∂BTC(zk) eads
h(x)000
En000
,
and we immedia ely encoun e a singula i y. In ou subsequen implemen a ion, we
he e o e p e e o use he Fische -Bu meis e app oach simply because he (gen-
e alized) pa ial de i a i es o he minimum unc ion ha e 0-1-en ies, whe eas he
co esponding pa ial de i a i es o he Fische -Bu meis e - unc ion a e usually bo h
di e en om ze o (unless we a e in a KKT poin ).
7 Nume ical esul s
In his sec ion we p esen some nume ical esul s ob ained by applying he p e iously
de eloped Lag ange–New on- ype me hods o some commonly known ields o spa se
op imiza ion p oblems. We s a wi h some p elimina ies ega ding ou implemen a-
ion.
7.1 Implemen a ion
Ini ial alues
Lag ange–New on- ype me hods a e mainly locally con e gen app oaches. Ou
aim is o show hese me hods can be used o imp o e solu ions ob ained by globally
123
100 C. Kanzow e al.
con e gen echniques. The e o e, we p e-p ocess he p oblem by i s sol ing he
1-su oga e p oblem
min
x (x)+ρx1s. . x∈X,
wi h ,Xas in SPO. We hen use he solu ion x1o he 1-su oga e p oblem as ini ial
poin x0 o he Lag ange–New on- ype me hods, which we conside pos -p ocessing
o he 1-su oga e p oblem. Accumula ion poin s x∗o ou Lag ange–New on- ype
me hods should (hope ully) be p e e able o SPO o e he 1-solu ion.
No e ha i is, in gene al, no use ul o ha e x0=0 as he ini ial guess. In ac ,
in cases whe e cons ain s do no exis , he ini ial guess x0=0 does al eady yield
an S-s a iona y poin . The s a ing poin x0=x1, ob ained by he p e-p ep ocessing
phase, may also ha e many ze o componen s, bu should, none heless, be a much
be e choice han he ze o ec o . Fu he mo e, we ound i bene icial o ini ialize
y0:= esince we wan o see a majo i y o 0-en ies in he accumula ion poin x∗o
he algo i hm, which would co ela e wi h a y∗consis ing o mainly 1-en ies. Fo any
o he Lag angian mul iplie s (λ,μ,γ)we wo ked wi h he canonical choice: λ0=0,
μ0=0, γ0=0, in he espec i e dimensions. No e ha any choice o γ0migh be
a bi a ily bad since, o an accumula ion poin x∗wi h an en y 10−4≈|x∗
i| = 0,
one has o expec γ∗
i≈ρsign(x∗)104.
In ou nume ical es , we we e able o imp o e upon he 1-solu ion x0in e ms o
he a ge alue o he espec i e SPO and also in e ms o he ini ial spa si y.
Dealing wi h he B-subdi e en ial
We only conside he Fische -Bu meis e unc ion, whene e an NCP- unc ion is
equi ed in ou compu a ions. The me hod o ob ain an elemen in he B-subdi e en ial
o he Fische -Bu meis e unc ion is widely known, compa e [12]. We ix a poin
z=(x,y,λ,μ,γ)and conside he ope a o TCwi h he componen s:
φ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}.
De ine:
(x ,y ,λ
):= (x− e(n), y− e(n), λ − e(p)), o >0,
wi h e=(1,1,...,1)To he app op ia e dimension. Passing o he limi 0
yields
lim
0∇(xi,yi)φFB(x
i,y
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 spa se(s ) op imiza ion p oblem: e o mula ions... 107
Fig. 4 A e age a ge alue o (x)+ρx0and 0-No m o success ul comp essi e sensing uns
ea ly, as he e o in he New on-s ep wi h espec o he 2-no m wen pas he sa e y
h eshold o 100. Fo all alues o ρ, he esul ing a e age alue (x)+ρx0o all
success ul uns is shown in Fig. 4. Again, we obse e a signi ican imp o emen o he
objec i e unc ion alue o all ope a o s T,T ed,TC, bu now wi h less p onounced
di e ences be ween he h ee ope a o s.
7.4 Logis ic eg ession
Conside he ollowing spa se op imiza ion p oblem
min
w
m

i=1
log(1+exp(−yi·wTxi)) +ρw0,(35)
which we e e o as he penalized maximum log-likelihood unc ion. This es ima o
is applied o ma ch a sigmoid- unc ion o a se o measu emen s x1,...,xmand co -
esponding Be noulli- a iables y1,...,yn∈{−1,1}m, whe e addi ionally spa si y is
p omo ed in he pa ame e s wi. Replacing ·0by ·1in (35), we ob ain a con ex
composi e op imiza ion p oblem, which can be ackled by FISTA o p oximal BFGS
me hods, compa e [24].
In ou nume ical es , we conside he p oblem gise e om he NIPS 2003 ea u e
selec ion challenge, which was acqui ed om he LIBSVM-websi e.7The classi ica ion
p oblem is high-dimensional (n=5000,m=6000)and was scaled o [−1,1].
Recall ha applying ei he o he New on- ype me hods wi h TC,To T ed o he
gise e p oblem leads o a d as ic inc ease in he dimensionali y (in he case o TC:
n=30,000). Compu a ion was he e o e ou sou ced o a as e PC and handled in
Py hon.
We compu ed an ini ial poin x0by sol ing he 1-su oga e p oblem o (35) wi h
FISTA. Running he h ee New on- ype me hods wi h his ini ial poin hen lead o
he esul s in Fig.5. The abb e ia ions TCx, Tx, Rx show he solu ions ound by he
espec i e ope a o s TC,Tand T ed. As one can see, all h ee o he ope a o s lead o
7h ps://www.csie.n u.edu. w/~cjlin/libs m ools/da ase s/.
123

108 C. Kanzow e al.
Fig. 5 Compa ison o a ge alue (x)+x0and spa si y x0 o logis ic eg ession. TCx, Tx and Rx
show he solu ions ound by he ope a o s TC,Tand T ed, espec i ely
an imp o ed spa si y x0and an imp o ed unc ion alue (x)+x0, meaning a
be e solu ion o he o iginal p oblem (35).
8 Final ema ks
The aim o his pape was mainly o lay he heo e ical ounda ion o wo e o mu-
la ions o he highly di icul spa se op imiza ion p oblem SPO. In pa icula , i was
shown ha we ge ull equi alence o p oblem SPO wi h hese wo e o mula ions in
e ms o global and local minima. Mo eo e , he co esponding s a iona y condi ions
also coincide and co esponding second-o de condi ions a e closely ela ed. These
esul s can be used o de elop and in es iga e Lag ange–New on- ype me hods o he
nume ical solu ion o p oblem SPO and he nume ical esul s indica e ha one can
use hese me hods in o de o ge signi ican imp o emen s o solu ions ob ained by
some o he echniques.
The Lag ange–New on- ype me hods, o cou se, a e local in na u e, bu esul
qui e na u ally as a di ec consequence o ou heo e ical conside a ions.8Ou u u e
esea ch, howe e , will concen a e on he de elopmen o globally con e gen me h-
ods based on ou e o mula ions. Some p elimina y esul s in his di ec ion can al eady
be ound in [32].
8h ps://pypi.o g/p ojec /y inance/.
123
The spa se(s ) op imiza ion p oblem: e o mula ions... 109
Appendix: P oo s o Sec ion 3
P oo o Lemma 3.1 (i) The de ini ion o he index se I0(x)and he assumed easi-
bili y o (x,y)implies
n−eTy=n−
i∈I0(x)
yi−
i/∈I0(x)
yi=n−
i∈I0(x)
yi≥n−
i∈I0(x)
1=x0.
This also shows ha equali y holds i and only i yi=1 o all i∈I0(x).
(ii) Recall ha he unc ion yi→ yi(yi−2)a ains i s (unique) minimum a yi=1
wi h co esponding minimal unc ion alue −1. The de ini ion o he index se
I0(x)and he easibili y o (x,y) he e o e yield
n

i=1
yi(yi−2)=
i∈I0(x)
yi(yi−2)≥
i∈I0(x)−1=n−
i∈I0(x)
1−n=x0−n,
and equali y holds i and only i yi=1 o all i∈I0(x).

P oo o Lemma 3.2 Le (x∗,y∗)be a local minimum o SPOlin. We can ix x=x∗
and know ha y∗sol es
max
yeTys. . yi=0,i/∈I0(x∗), y≤e.
Simila ly, le (x∗,y∗)be a local minimum o SPOsq. We can ix x=x∗and know
ha y∗sol es
min
y
n

i=1
yi(yi−2)s. . yi=0,i/∈I0(x∗).
In bo h cases he s a emen ollows. 
P oo o P oposi ion 3.3 Le ρ1and ρ2be wo penal y pa ame e s, and le x∗be a local
minimum o
min
x (x)+ρ1x0s. . x∈X.(36)
Assume ha x∗is no a local minimum o
min
x (x)+ρ2x0s. . x∈X.
Then he e exis s a sequence {xk}⊆Xwi h xk→x∗such ha
(xk)+ρ2

xk

0< (x∗)+ρ2
x∗
0∀k∈N.(37)
123
110 C. Kanzow e al.
No e ha 
xk
0≥x∗0holds o all ksu icien ly la ge. Fi s conside he case ha
he e exis s a subsequence such ha 
xk
0=x∗0holds o all k∈K. Then we
ob ain
(xk)+ρ1

xk

0= (xk)+ρ2

xk

0+(ρ1−ρ2)

xk

0
< (x∗)+ρ2
x∗
0+(ρ1−ρ2)

xk

0
= (x∗)+ρ2
x∗
0+(ρ1−ρ2)
x∗
0= (x∗)+ρ1
x∗
0
o all k∈K, con adic ing he assump ion ha x∗is a local minimum o (36). In he
o he case, we ha e 
xk
0>x∗0and, he e o e, x∗0+1≤
xk
0 o almos all
k∈N. Fu he mo e, by con inui y o , i ollows ha (x∗)≤ (xk)+ρ2 o all k
su icien ly la ge. This implies
(x∗)+ρ2
x∗
0≤ (xk)+ρ2+ρ2x∗0= (xk)+ρ21+x∗0
≤ (xk)+ρ2
xk
0,
a con adic ion o (37). Al oge he , his comple es he p oo . 
Funding Open Access unding enabled and o ganized by P ojek DEAL.
Da a a ailabili y The da a which was used o c ea e he esul s wi hin his manusc ip is composed o 1.
mixed-in ege po olio op imiza ion p oblems by F angioni and Gen ile. A he momen o w i ing, hey
a e publicly a ailable (c. . page 22, oo no e 2). To ou knowledge, he es ins ance a e andomly gene a ed.
The speci ic ins ance o his manusc ip lies wi h he au ho s and is a ailable on eques . 2. inancial da a
collec ed wi h he y inance py hon-package9. The acqui ed da a was solely used o c ea e alues o he
nume ical expe imen in Sec . 7.2.2. The da a lies wi h he au ho s and is a ailable on eques . 3. comp essi e
sensing es se s, which ha e been gene a ed p ocedu ally and andomly by MATLAB om a andom seed.
4. he gise e classi ica ion p oblem, which o igina es om he NIPS 2003 ea u e selec ion challenge. The
speci ic da a used in sec ion 7.4 is publicly a ailable wi h he LIBSVM-lib a y (c. . page 26, oo no e 8).
Decla a ions
Con lic o in e es The e a e no con lic o in e es o epo .
Open Access This a icle is licensed unde a C ea i e Commons A ibu ion 4.0 In e na ional License, which
pe mi s use, sha ing, adap a ion, dis ibu ion and ep oduc ion in any medium o o ma , as long as you gi e
app op ia e c edi o he o iginal au ho (s) and he sou ce, p o ide a link o he C ea i e Commons licence,
and indica e i changes we e made. The images o o he hi d pa y ma e ial in his a icle a e included
in he a icle’s C ea i e Commons licence, unless indica ed o he wise in a c edi line o he ma e ial. I
ma e ial is no included in he a icle’s C ea i e Commons licence and you in ended use is no pe mi ed
by s a u o y egula ion o exceeds he pe mi ed use, you will need o ob ain pe mission di ec ly om he
copy igh holde . To iew a copy o his licence, isi h p://c ea i ecommons.o g/licenses/by/4.0/.
Re e ences
1. Beck, A.: Fi s -o de me hods in op imiza ion. SIAM (2017)
123
The spa se(s ) op imiza ion p oblem: e o mula ions... 111
2. Ben Mhenni, R., Bou guignon, S., Ninin, J.: Global op imiza ion o spa se solu ion o leas squa es
p oblems. Op im. Me hods So wa e 37(5), 1740–1769 (2021)
3. Be simas, D., Van Pa ys, B.: Spa se high-dimensional eg ession: exac scalable algo i hms and phase
ansi ions. Ann. S a . 48(1), 300–323 (2020)
4. Bi, S., Pan, S., Sun, D.: A mul i-s age con ex elaxa ion app oach o noisy s uc u ed low- ank ma ix
eco e y. Ma h. P og am. Compu . 12(4), 569–602 (2020)
5. Bonnans, J.F., Shapi o, A.: Pe u ba ion Analysis o Op imiza ion P oblems. Sp inge , New Yo k
(2000)
6. Bu dako , O.P., Kanzow, C., Schwa z, A.: Ma hema ical p og ams wi h ca dinali y cons ain s: e o -
mula ion by complemen a i y- ype condi ions and a egula iza ion me hod. SIAM J. Op im. 26(1),
397–425 (2016)
7. Candes, E., Tao, T.: Decoding by linea p og amming. IEEE T ans. In . Theo y 51(12), 4203–4215
(2005)
8. ˇ
Ce inka, M., Kanzow, C., Schwa z, A.: Cons ain quali ica ions and op imali y condi ions o op i-
miza ion p oblems wi h ca dinali y cons ain s. Ma h. P og am. 160(1), 353–377 (2016)
9. Chen, S.S., Donoho, D.L., Saunde s, M.A.: A omic decomposi ion by basis pu sui . SIAM J. Sci.
Compu . 20(1), 33–61 (1998)
10. Chen, X., Guo, L., Lu, Z., Ye, J.J.: An augmen ed Lag angian me hod o non-Lipschi z noncon ex
p og amming. SIAM J. Nume . Anal. 55(1), 168–193 (2017)
11. Cla ke, F.H.: Op imiza ion and nonsmoo h analysis. SIAM (1990)
12. De Luca, T., Facchinei, F., Kanzow, C.: A semismoo h equa ion app oach o he solu ion o nonlinea
complemen a i y p oblems. Ma h. P og am. 75, 407–439 (1996)
13. Facchinei, F., Fische , A., Kanzow, C.: Regula i y p ope ies o a semismoo h e o mula ion o a ia-
ional inequali ies. SIAM J. Op im. 8(3), 850–869 (1998)
14. Facchinei, F., Pang, J.-S.: Fini e-Dimensional Va ia ional Inequali ies and Complemen a i y P oblems
(Volume I). Sp inge , New Yo k (2004)
15. Facchinei, F., Pang, J.-S. (eds.): Fini e-Dimensional Va ia ional Inequali ies and Complemen a i y
P oblems (Volume II). Sp inge , New Yo k (2004)
16. Feng, M., Mi chell, J.E., Pang, J.-S., Shen, X., Wäch e , A.: Complemen a i y o mula ions o 0-no m
op imiza ion p oblems. Pac. J. Op im. 14(2), 273–305 (2018)
17. Fische , A.: A special New on- ype op imiza ion me hod. Op imiza ion 24(3–4), 269–284 (1992)
18. Gaines, B.R., Kim, J., Zhou, H.: Algo i hms o i ing he cons ained lasso. J. Compu . G aph. S a .
27(4), 861–871 (2018)
19. Ghilli, D., Kunisch, K.: A mono one scheme o spa si y op imiza ion in pwi h p∈(0,1].IFAC-
Pape sOnLine 50(1), 494–499 (2017)
20. Go oh, J.-Y., Takeda, A., Tono, K.: DC o mula ions and algo i hms o spa se op imiza ion p oblems.
Ma h. P og am. 169(1), 141–176 (2018)
21. Hoheisel, T., Kanzow, C.: S a iona y condi ions o ma hema ical p og ams wi h anishing cons ain s
using weak cons ain quali ica ions. J. Ma h. Anal. Appl. 337(1), 292–310 (2008)
22. Hoheisel, T., Kanzow, C., Schwa z, A.: Theo e ical and nume ical compa ison o elaxa ion me hods
o ma hema ical p og ams wi h complemen a i y cons ain s. Ma h. P og am. 137(1), 257–288 (2013)
23. Le Thi, H.A., Pham Dinh, T., Le, HM., Vo, X.T.: DC app oxima ion app oaches o spa se op imiza ion.
Technical epo , (2014)
24. Lee, J.D., Sun, Y., Saunde s, M.A.: P oximal New on- ype me hods o minimizing composi e unc-
ions. SIAM J. Op im. 24(3), 1420–1443 (2014)
25. Lu, Z., Zhang, Y.: Penal y decomposi ion me hods o l0-no m minimiza ion. Technical epo (2012)
26. Ma chi, A.D., Jia, X., Kanzow, C., Mehli z, P.: Cons ained composi e op imiza ion and augmen ed
Lag angian me hods. Ma h. P og am. (2023)
27. Ma kowi z, H.: Po olio selec ion. J. Finance 7(1), 77–91 (1952)
28. Mehli z, P.: S a iona i y condi ions and cons ain quali ica ions o ma hema ical p og ams wi h
swi ching cons ain s. Ma h. P og am. 181(1), 149–186 (2020)
29. Nocedal, J., W igh , S.J.: Nume ical Op imiza ion, 2e edn. Sp inge , New Yo k, NY (2006)
30. Qi, L.: Con e gence analysis o some algo i hms o sol ing nonsmoo h equa ions. Ma h. Ope . Res.
18(1), 227–244 (1993)
31. Qi, L., Sun, J.: A nonsmoo h e sion o New on’s me hod. Ma h. P og am. 58(1), 353–367 (1993)
32. Raha ja, A.B.: Op imisa ion P oblems wi h Spa si y Te ms: Theo y and Algo i hms. PhD Thesis,
Julius-Maximilians-Uni e si ä Wü zbu g (2020)
123
112 C. Kanzow e al.
33. Sha pe, W.F.: The sha pe a io. J. Po . Manag. 21(1), 49–58 (1994)
34. Tillmann, A.M., Biens ock, D., Lodi, A., Schwa z, A.: Ca dinali y minimiza ion, cons ain s, and
egula iza ion: a su ey. Technical epo (2021)
35. Wang, L., Wang, J., Xiang, J., Yue, H.: A e-weigh ed smoo hed 0-no m egula ized spa se econ-
s uc ed algo i hm o linea in e se p oblems. J. Phys. Commun. 3(7), 075004 (2019)
36. Yin, P., Lou, Y., He, Q., Xin, J.: Minimiza ion o 1−2 o comp essed sensing. SIAM J. Sci. Compu .
37(1), A536–A563 (2015)
37. Zhao, C., Xiu, N., Qi, H., Luo, Z.: A Lag ange-New on algo i hm o spa se nonlinea p og amming.
Ma h. P og am. 195(1–2), 903–928 (2021)
Publishe ’s No e Sp inge Na u e emains neu al wi h ega d o ju isdic ional claims in published maps
and ins i u ional a ilia ions.
123