Convergence of successive linear programming algorithms for noisy functions

Hansknech , Ch is oph; Ki ches, Ch is ian; Manns, Paul
A icle — Published Ve sion
Con e gence o successi e linea p og amming
algo i hms o noisy unc ions
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: Hansknech , Ch is oph; Ki ches, Ch is ian; Manns, Paul (2024) : Con e gence o
successi e linea p og amming algo i hms o noisy unc ions, Compu a ional Op imiza ion and
Applica ions, ISSN 1573-2894, Sp inge US, New Yo k, NY, Vol. 88, Iss. 2, pp. 567-601,
h ps://doi.o g/10.1007/s10589-024-00564-w
This Ve sion is a ailable a :
h ps://hdl.handle.ne /10419/315241
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 (2024) 88:567–601
h ps://doi.o g/10.1007/s10589-024-00564-w
Con e gence o successi e linea p og amming algo i hms
o noisy unc ions
Ch is oph Hansknech 1·Ch is ian Ki ches1·Paul Manns2
Recei ed: 16 Feb ua y 2023 / Accep ed: 30 Janua y 2024 / Published online: 26 Feb ua y 2024
© The Au ho (s) 2024
Abs ac
G adien -based me hods ha e been highly success ul o sol ing a a ie y o bo h
uncons ained and cons ained nonlinea op imiza ion p oblems. In eal-wo ld appli-
ca ions, such as op imal con ol o machine lea ning, he necessa y unc ion and
de i a i e in o ma ion may be co up ed by noise, howe e . Sun and Nocedal ha e
ecen ly p oposed a emedy o smoo h uncons ained p oblems by means o a s abi-
liza ion o he accep ance c i e ion o compu ed i e a es, which leads o con e gence
o he i e a es o a us - egion me hod o a egion o c i icali y (Sun and Nocedal
in Ma h P og am 66:1–28, 2023. h ps://doi.o g/10.1007/s10107-023-01941-9). We
ex end hei analysis o he successi e linea p og amming algo i hm (By d e al.
in Ma h P og am 100(1):27–48, 2003. h ps://doi.o g/10.1007/s10107-003-0485-4,
SIAM J Op im 16(2):471–489, 2005. h ps://doi.o g/10.1137/S1052623403426532)
o uncons ained op imiza ion p oblems wi h objec i es ha can be cha ac e ized as
he composi ion o a polyhed al unc ion wi h a smoo h unc ion, whe e he la e and
i s g adien may be co up ed by noise. This gi es he lexibili y o co e , o example,
(sub)p oblems a ising in image econs uc ion o cons ained op imiza ion algo i hms.
We p o ide compu a ional examples ha illus a e he indings and poin o possible
s a egies o p ac ical de e mina ion o he s abiliza ion pa ame e ha balances he
size o he c i ical egion wi h a elaxa ion o he accep ance c i e ion (o descen
p ope y) o he algo i hm.
Keywo ds Nonsmoo h op imiza ion ·Global con e gence ·Noisy op imiza ion
BCh is oph Hansknech
[email p o ec ed]
Ch is ian Ki ches
[email p o ec ed]
Paul Manns
[email p o ec ed]
1Ins i u e o Ma hema ical Op imiza ion, TU B aunschweig, B aunschweig, Ge many
2Chai o Nume ical Analysis and Op imiza ion, TU Do mund Uni e si y, Do mund, Ge many
123
568 C. Hansknech e al.
1 In oduc ion
Handling non-smoo hness is an ubiqui ous esea ch ques ion in nonlinea op imiza-
ion because i a ises na u ally in di e en a eas, o example, penal y unc ions o
cons ained op imiza ion [4], s a is ical da a analysis and signal p ocessing [5,6], and
neu al ne wo k a chi ec u es [7]. In his wo k we s udy he con e gence p ope ies o
successi e linea p og amming algo i hms o sol e he op imiza ion p oblem
min
x∈Rnφ(x):=ω(F(x)), (P)
whe e ω:Rp→Ris con ex and Lipschi z con inuous wi h polyhed al epig aph, and
F:Rn→Rpis wice con inuously di e en iable. Mo eo e , we assume ha Fand
i s Jacobian can only be accessed inexac ly so ha hei e alua ions a e co up ed by
noise. This and simila p oblems ha e been s udied in he li e a u e, see, o example,
[8–12] and he e e ences he ein.
Many op imiza ion p oblems can be o mula ed in e ms o p oblem (P) such as he
Lag angian o m
min
x∈Rny−Ax2
2+βx1
o he amous LASSO p oblem [5,13] wi h A∈Rm×n,β>0, and y∈Rm ha is
pa icula ly popula among da a scien is s o spa se pa ame e iden i ica ion in o e -
pa ame e ized models. Mo e b oadly speaking, a wide class o nonlinea op imiza ion
p oblems all unde (P) as well. As an example, he uncons ained minimiza ion o a
smoo h objec i e :Rn→Rcan be modeled by se ing p=1 and ω(x)=x o
x∈R. We can also examine nonlinea p og ams cons ained by smoo h unc ions
g:Rn→Rmand h:Rn→Rkyielding p oblems o he o m
min
x∈Rn (x)s. . g(x)≤0,h(x)=0.(NLP)
These p oblems may be sol ed by minimizing a non-smoo h exac penal y unc ion
o he o m
φ(x,ν):= (x)+ν


g(x)T
+,h(x)TT


1
,(1)
whe e y+:= max(y,0)and ν>0. In ac , s ic local solu ions o (NLP) a e local
minimize s o φ(x,ν) o a su icien ly la ge alue o νi gand ha e smoo h and
sa is y he Mangasa ian–F omo i z cons ain quali ica ion [14, Theo em 4.4], [4,
Theo em 17.3] a he espec i e poin s. The penal y unc ion φcan be exp essed
as ω(F(x)), whe e F(x):=( (x), g(x)T,h(x)T)Tis smoo h and ω(x,y,z):=x+
ν(y+T,zT)T1is con ex and polyhed al. Besides p oblems o ype (NLP), a a ie y
o o he p oblems, such as linea o nonlinea i ing p oblems can be o mula ed in
e ms o (P) as well.
Noisy unc ions
The combina ion o uncons ained op imiza ion wi h noisy obse a ions has ecen ly
been examined [1,15–21]. The au ho s conside he minimiza ion o a smoo h unc ion
φ:Rn→Rwhile only ha ing access o
123
Con e gence o successi e linea p og amming… 569
(x)=φ(x)+ε(x)and g(x)=∇φ(x)+e(x), (2)
whe e he only assump ions a e ha bo h |ε|and ea e uni o mly bounded. Conse-
quen ly, i is no gene ally possible o gene a e a sequence {xk}o i e a es con e ging
o a local op imum o s a iona y poin o φ. In ui i ely, while he g adien noise eis
small compa ed o ∇φ, he di ec ion gis a sui able sea ch di ec ion wi h espec o φ.
This allows o he use o an A mijo-like globaliza ion s a egy [16,20] o , in case o
[1,17], a us - egion me hod, whe e he noise is handled by s abilizing he educ ion
a io, which is o cou se closely ela ed o he A mijo condi ion. As soon as a egion is
eached whe e he noise p oduced by εand ebecomes oo la ge ela i e o φand ∇φ
espec i ely, no u he p og ess can be expec ed and he algo i hm may s all. How-
e e , his c i ical egion is isi ed in ini ely o en and once eaching i , he algo i hm
does no p oduce objec i e alues much la ge han he objec i e alues a ained in he
c i ical egion. The au ho s also s udy he p oblem o adap ing quasi-New on me hods
o he noisy se ing.
Con ibu ion
We build on he ideas in [1,15,21] and conside he non-smoo h p oblem (P)ina
se ing, whe e unc ion and de i a i e e alua ions a e only a ailable as noisy obse -
a ions. As he au ho s in [1,15,21], we assume he ollowing noise model: Ra he
han being able o e alua e Fand i s de i a i e Fdi ec ly, we only ha e access o
˜
F(x):=F(x)+δF(x)and G(x):= F(x)+δF(x).
These p oxies consis o he o iginal unc ions Fand Fas well as e o unc ions δF:
Rn→Rpand δF:Rn→Rp×n. In e ms o he p oblem (NLP), his is an amoun o
noise in he objec i e , he cons ain s g,h, and hei espec i e de i a i es. Con a y
o his, we assume ha he unc ion ωdoes no su e om any noise. Wha is mo e,
we p esume ha he s uc u e o ωis well unde s ood in he sense ha , o example,
i s Lipschi z cons an is known, which is ce ainly he case o he penal y unc ion
in (1).
In o de o sol e op imiza ion p oblems o he o m (P), we p opose a us - egion
algo i hm leaning on he successi e linea p og amming empla e p oposed in [2] and
a con e gence analysis ha builds on he ideas in [3,15,21]. Speci ically, we use a
s abiliza ion o he i e a e accep ance es in o de o asse ha a neighbo hood o a
s a iona y poin is isi ed in ini ely o en by he i e a es p oduced by he algo i hm.
The polyhed al s uc u e o ωis handled by i s sol ing a linea p og am in o de o
de e mine a di ec ion o a subsequen Cauchy poin de e mina ion. This can also be
in e p e ed as an ac i e se de e mina ion o he co esponding kinks o he polyhed al
epig aph o ω.
We also p o ide compu a ional examples ha illus a e he heo e ical esul s and
he p ac ical beha io o he algo i hm. Mo eo e , he esul s poin o open ques ions
and possible app oaches ega ding he choice o he co ec s abiliza ion pa ame e in
he accep ance es .
S uc u e o he Remainde
We in oduce he successi e linea p og amming algo i hm and he modi ied accep-
ance es in Sec .2. The asymp o ics o he algo i hm a e analyzed in Sec . 3.We
123
570 C. Hansknech e al.
p o ide compu a ional examples and he co esponding esul s in Sec .4.Wed awa
conclusion in Sec .5.
2 A noise- ole an successi e linea p og amming algo i hm
In he noisy se ing, we canno expec o ind he ue op imum o s a iona y poin s o φ,
since we do no ha e access o Fand F. Speci ically, in a small egion a ound he ue
op imum x∗,˜
Fand Gmay oscilla e, he eby making hei e alua ions un eliable. This
impai s globaliza ion s a egies in nonlinea p og amming because hei accep ance
es s equi e eliable e alua ions o Fand a model unc ion in ol ing F.
In he non-noisy egime, a us - egion me hod p oduces a sequence {xk}o i e a es
by assembling and subsequen ly op imizing model unc ions qk:Rn→R, yielding
as epdk. The quali y o dkis de e mined acco ding o he educ ion a io
ρk:= φ(xk)−φ(xk+dk)
φ(xk)−qk(dk),
which is used o de e mine whe he o no he s ep will be accep ed. Howe e , in
he noisy se ing, we only ha e access o ˜
Fleading o a noisy composi e unc ion
˜
φ(x):=ω( ˜
F(x)). While we can build a model ˜qk:Rn→Rpwhich coincides wi h
˜
Fa xk, we canno con ol he nume a o ˜
φ(xk)−˜
φ(xk+dk). Indeed, i we educe
he us egion, sending dk o ze o, he denomina o o ρkwill end o ze o while he
nume a o will oscilla e, making he a io un eliable. To alle ia e his p oblem, we
u n owa ds a ecen adap a ion [1] o us - egion me hods in o de o sol e he noisy
coun e pa o (P). The au ho s o [1] add a co ec ion e m, ha is a posi i e cons an
ϑ>0, o bo h he nume a o and denomina o o he educ ion a io ρk o mi iga e
he e ec o noisy e alua ions, yielding a modi ied a io
˜ρk:= ˜
φ(xk)−˜
φ(xk+dk)+ϑ
˜
φ(xk)−˜qk(dk)+ϑ.
The pa ame e ϑcan hen be chosen app op ia ely in o de o s abilize he a io. As
we will see, his means ha o ϑla ge enough, he i e a es o he successi e linea
p og amming algo i hm con e ge o a c i ical egion a ound a s a iona y poin . The
downside is ha his egion g ows wi h ϑand he algo i hm also accep s s eps ha do
no imp o e he objec i e.
Apa om his adjus men , we ollow he algo i hmic app oach in [3]. Speci ically,
we use he ollowing pa ially linea ized and quad a ic models a xk∈Rn
˜
(x;d):=ω˜
F(x)+G(x)d,(3)
˜
k(d):= ˜
(xk;d), and (4)
˜qk(d):= ˜
k(d)+1
2d,Bkd,(5)
123

Con e gence o successi e linea p og amming… 571
whe e he Bk∈Rn×na e symme ic (no necessa ily posi i e de ini e) app oxima ions
o he cu a u e o ω◦F. He e and h oughou we le ·,· be he s anda d scala
p oduc in Rn, inducing he 2-no m, which we simply deno e by ·. Fo ma ices,
we le ·be he co esponding ope a o no m, gi en by i s la ges singula alue.
Algo i hm
Based on he models abo e, ou noise- ole an app oach o sol ing (P) is laid ou in
Algo i hm 1. In each i e a ion, an ini ial s ep dLP is compu ed in Line 3by sol ing he
p oblem
min
dLP≤LP
k˜
k(d),
whe e ·LP is a no m on Rnde ining he us egion associa ed wi h ˜
k. While we
make no u he assump ions ega ding his no m, i is in p ac ice ad an ageous o cas
his subp oblem as a linea p og am o be sol ed using s a e-o - he-a LP sol e s [22,
23]. To his end, wo condi ions should be me . Fi s , he epig aph o ωshould be
polyhed al. Second, he easible egion should be polyhed al as well, o , equi alen ly,
·LP should be a polyhed al no m, such as ·1o ·∞. In any case, due o he
equi alence o no ms in Rn he e exis s a cons an γ>0 such ha o each d∈Rn
i holds ha
d≤γdLP.(6)
The algo i hm p oceeds o compu e a Cauchy s ep dC
kin Lines 4–7. To his end, i
employs a line sea ch ini ialized wi h a s ep size su icien ly small o ensu e ha he
Cauchy s ep alls in o he us egion bounded by LP
k. Du ing he line sea ch he s ep
size is sho ened by a ac o o 0 <τ<1 un il he quad a ic educ ion achie ed by
he Cauchy poin is wi hin a ac o o 0 <η<1 o i s linea educ ion.
The ac ual s ep dk o be aken in Line 8can be di e en om he Cauchy s ep
dC
k, p o ided ha i imp o es upon he quad a ic educ ion o dC
k. This gi es some
algo i hmic lexibili y, allowing o he compu a ion o New on- ype s eps in o de
o achie e local quad a ic con e gence. Based on he s abilized educ ion a io ˜ρk
compu ed in Line 9, he s ep is ei he accep ed (Lines 11–12) o ejec ed (Lines 14–
15) acco ding o an accep ance h eshold o ρu>0. Addi ionally, he us - egion
adii k+1and LP
k+1a e adjus ed based on ˜ρk:
1. The alue o k+1is inc eased o dec eased based on whe he ˜ρkachie es a alue
o a leas ρs. The dec ease is such ha he new us - egion adius is a mos κu<1
imes as la ge as he p e ious one, he eby ensu ing a ue educ ion, while being
a leas κldk(wi h 0 <κ
l≤κu) in o de o p e en an immedia e collapse o
he us egion.
2. I ˜ρkachie es a leas ρu(no e ha ρu≤ρs), he LP us - egion adius LP
k+1
is inc eased beyond dC
kLP, as long as i does no exceed he uppe bound o
LP
max ≥1. The new LP us - egion adius is also only inc eased beyond LP
k+1
i he ull LP s ep dLP was accep ed (i.e., αk=1), indica ing ha he pa ially
linea ized model ˜
kis a good app oxima ion o ˜
φkac oss he en i e LP us egion.
I ˜ρk alls sho o ρu,LP
k+1is dec eased while being kep wi hin a ac o o θ>0
o dkLP.
123
572 C. Hansknech e al.
Rema k 2.1 When applied o p oblem (NLP), Algo i hm 1uses he s a egies in o-
duced in [2], which o m he basis o he ac i e se me hod in he highly success ul
Kni o code [24], which combines sequen ial linea p og amming wi h equali y con-
s ained quad a ic p og amming app oaches in o de o achie e obus pe o mance
o e a ange o la ge-scale nonlinea p og amming p oblems.
Algo i hm 1: A noise- ole an algo i hm o minimize φ(x)=ω(F(x))
Inpu : Func ions ω,˜
F,G,
Ini ial poin x0∈Rn,
Ini ial us egion adii 0 <
LP
0≤LP
max,0<
0
Pa ame e s: Accep ance h esholds 0 <ρ
u≤ρs<1,
S ep adjus men s 0 <κ
l≤κu<1, θ>0,
Cauchy line sea ch pa ame e s 0 <η<1, 0 <τ <1,
Ra io s abilize ϑ>0,
Maximum LP us egion adius LP
max ≥1
Ou pu : P imal poin x∗∈Rn
1k←0
2un il Some e mina ion c i e ion is sa is ied
3Compu e LP s ep
dLP
k←a g mindLP≤LP
k˜
k(d)
4αk←min 1,
k/dLP
k
5while ˜
φ(xk)−˜qk(αkdLP
k)<η˜
φ(xk)−˜
k(αkdLP
k)do
6αk←ταk
7dC
k←αkdLP
k
8dk←S ep dsuch ha d≤kand ˜qk(d)≤˜qk(dC
k)
9Compu e s abilized educ ion a io
˜ρk←˜
φ(xk)−˜
φ(xk+dk)+ϑ
˜
φ(xk)−˜qk(dk)+ϑ
10 i ˜ρk≥ρu hen Accep s ep
11 Se xk+1←xk+dk
12 Pick LP
k+1∈dC
kLP,
LP
maxsuch ha LP
k+1≤LP
ki αk<1
13 else Rejec s ep
14 Se xk+1←xk
15 Pick LP
k+1∈min(θdkLP,
LP
k), LP
k
16 i ˜ρk≥ρs hen
17 Se k+1≥k
18 else
19 Choose k+1∈[κldk,κ
uk]
20 k←k+1
21 e u n x∗=xk
123
Con e gence o successi e linea p og amming… 573
3 Con e gence analysis o Algo i hm 1
We begin ou con e gence analysis wi h he in oduc ion o he s anding assump ions
and a ecap o he ele an s a iona i y concep o (P) in Sec .3.1. We analyze he
c i icali y measu e o his no ion o s a iona i y in he noisy se ing in Sec .3.2.Weuse
hese esul s o p o e lowe bounds on he us - egion adii ha occu in Algo i hm 1
in Sec .3.3, which a e hen used o ob ain su icien dec ease and, as a consequence,
con e gence o he p oduced i e a es o c i ical egions in Sec .3.4.
3.1 S anding assump ions and s a iona i y
In o de o s udy he con e gence p ope ies o Algo i hm 1, we make se e al assump-
ions ega ding he amoun o noise, he unc ions ω,F, and he ma ices Bkused in
he quad a ic models ˜qk.
Assump ion 1 We assume ha he noise is uni o mly bounded ia δF(x)≤εFand
δF(x)≤εF o all x∈Rn. We e e o εFand εFas he noise le els o he
unc ions ˜
Fand G espec i ely.
Assump ion 2 ωis Lipschi z-con inuous wi h cons an Lω, i.e., i holds o all x,y∈
Rn ha
|ω(x)−ω(y)|≤Lωx−y.
Assump ion 3 Fand Fa e Lipschi z-con inuous wi h cons an s LFand LF, i.e., i
holds o all x,y∈Rn ha
F(x)−F(y)≤LFx−yand
F(x)−F(y)≤LFx−y.
Assump ion 4 The Hessian app oxima ions Bka e bounded, i.e., he e exis s β>0
such ha o all d∈Rn,k>0 i holds ha
|d,Bkd| ≤ βd2.
Ou aim in he ollowing is o ind a local op imum o φ. A i s -o de necessa y
condi ion (see [25, p. 184]) o op imali y o (P) s a es ha x∗∈Rncan only be a
local op imum i
max
λ∈∂ω(F(x∗))λ, F(x∗)d≥0 o all d∈Rn,(7)
whe e ∂ω(z)deno es he subdi e en ial o ωa z∈Rp. To measu e how close a poin
x∈Rnis o sa is ying hese condi ions, we use he c i icali y measu e in oduced
in [26]. Speci ically, we le
(x;) :=φ(x)−min
dLP≤(x;d)
123
574 C. Hansknech e al.
and se k() :=(xk;) as be o e. Clea ly, since d=0 is a easible solu ion o he
inne op imiza ion p oblem, he alue (x;) is always non-nega i e. On he o he
hand, he ollowing esul es ablishes ha a anishing educ ion o e a non i ial us
egion is an amoun o eaching a poin sa is ying i s -o de condi ions, which we
call a c i ical poin :
Lemma 3.1 ([26], Lemma 2.1) A poin x∗∈Rnsa is ies condi ions (7)i he e exis s
>0such ha
(x∗;) =0.
As a consequence o his esul , an algo i hm sol ing (P) should aim a gene a ing a
sequence o i e a es such ha lim in k→∞ k() =0 o some ixed >0 (assumed
o be 1 in he ollowing). This ensu es he exis ence o an accumula ion poin x∗o
he i e a es sa is ying i s -o de condi ions.
3.2 Analysis o model unc ion and c i icali y measu e in he p esence o noise
Since we do no ha e access o he alues o Fand F equi ed o compu e k,we
de ine a noisy measu e o c i icali y ia
˜
(x;) := ˜
φ(x)−min
dLP≤˜
(x;d)
and se ˜
k() := ˜
(xk;) as be o e. This unc ion is also non-nega i e i he same
ealiza ion o he unc ion noise δF(xk)is used when compu ing ˜
φ(xk)and cons uc ing
he linea app oxima ion ˜
k(d). We analyze i s p ope ies and ela ionship o kbelow.
Since δFcanno be assumed o be con inuous, nei he can ˜
φ. This di e s om he
analysis in [3], whe e he Lipschi z-con inui y o φis used o a gue ha he educ ion
a io app oaches one i he us - egion adius is d i en o ze o. We can, howe e , s a e
ha he c i icali y measu es kand ˜
ka e ela ed by he ollowing app oxima ion
esul : when conside ing a ixed xk, we claim ha ˜
k(1)→k(1) o εF→0 and
εF→0 and ha we also ha e con e gence o he minimize s o he con ex p og ams
in he de ini ions o ˜
k(1)and k(1). This ollows om he epi-con e gence o he
unc ionals
LεF,εF(d):= ˜
k(d)+idLP≤(d)and L0,0(d):=k(d)+idLP≤(d),
whe e iA:Rd→{0,∞} is he indica o unc ion o A⊂Rd, ha is iA(x)=∞i
x/∈Aand iA(x)=0 else. We ecall ha he unc ionals LεF,εFepi-con e ge o L0,0
i and only i o all d∈Rn he inequali ies
L0,0(d)≤lim in
εF,εF→0
LεF,εF(dε) o all sequences dε→dand (8)
L0,0(d)≥lim sup
εF,εF→0
LεF,εF(dε) o some sequence dε→d(9)
hold, see, o example, [27, § 7], which is shown below.
123
Con e gence o successi e linea p og amming… 581
P oo The p oo is in Appendix A.
The ollowing con e gence heo em s a es ha when he objec i e o (P) is bounded
below, an applica ion o Algo i hm 1will p oduce one o wo possible mu ually exclu-
si e ou comes: he algo i hm may s op a a c i ical poin a e a ini e numbe o
i e a ions as desc ibed in Lemma 3.13 o , al e na i ely, Algo i hm 1 isi s a c i ical
egion in ini ely o en. In e ms o he unc ions ω,˜
F, and G, hec i ical egion is
de ined as
C(δ) := x˜
(x;1)≤δ.
By de ini ion, an i e a e xkp oduced du ing he execu ion o Algo i hm 1is con ained
in C(δ) i ˜
k(1)≤δ. Wha is mo e, P oposi ion 3.2 es ablishes ha ˜
k(1) ends o
k(1)as he e o s εFand εFapp oach ze o. These esul s he e o e sugges ha he
i e a e is close o being op imal in he sense o Lemma 3.1.
Theo em 3.14 Conside an applica ion o Algo i hm 1 o he noisy a ian o p ob-
lem (P). Suppose ha Assump ions 1 o 4and (11)hold. Then ei he
˜
k(1)=0 o some k ≥0,
o
lim
k→∞ ˜
φ(xk)=−∞,
o he e a e in ini ely many k ∈Nsuch ha xk∈C(δmax), whe e
δmax := max ⎛
⎝ϑ(1−ρu)γ LP
max
ρuηB,ϑ(1−ρu)γ LP
max
ρuηA⎞
⎠
is gi en in e ms o he cons an s A,B om Lemma 3.12.
P oo I he e a e only ini ely many accep ed s eps, he esul ollows om Lemma
3.13, yielding he i s possibili y. O he wise, we can assume ha du ing he algo-
i hm, an in ini e numbe o accep ed s eps occu s. I ˜
φ(xk) ends o −∞, he second
possibili y occu s, so we can assume in he ollowing ha ˜
φ(xk)(and hence φ(xk))is
bounded below.
Le Kbe he sequence o accep ed s eps, i.e., consis ing o hose kwhe e xk+1= xk.
Clea ly, i lim in k→∞ ˜
k(1)=0, hen he esul ollows. So we can assume ha he e
exis s a δ>0 such ha ˜
k(1)≥δ o all k≥k0. The claim s a ing ha he egion
C(δmax)is isi ed in ini ely o en is an amoun o ensu ing ha δ≤δmax, which will
be he aim o he emainde o his p oo . Fo each k∈K,k≥k0we ha e ha
˜
φ(xk)−˜
φ(xk+1)+ϑ
˜
φ(xk)−˜qk(dk)+ϑ≥ρu>0.
123

582 C. Hansknech e al.
We deduce using Lemma 3.10 ha
˜
φ(xk)−˜
φ(xk+1)≥ρu˜
φ(xk)−˜qk(dk)+(ρu−1)ϑ
≥ρuηαkmin(LP
k,1)˜
k(1)+(ρu−1)ϑ.
I ollows ha
˜
φ(xk)−˜
φ(xk+1)≥ρuηαkLP
kmin 1
LP
k
,1˜
k(1)+(ρu−1)ϑ
≥ρuηαkLP
k
1
LP
max ˜
k(1)+(ρu−1)ϑ.
We can now apply Lemma 3.12 o bound αkLP
kbelow based on min and he
cons an s Aand B:
˜
φ(xk)−˜
φ(xk+1)≥ρuηmin
γ
LP
max ˜
k(1)+(ρu−1)ϑ
=ρuηmin(A,Bδ)
γ
LP
max ˜
k(1)+(ρu−1)ϑ
≥ρuηmin(A,Bδ)
γ
LP
max
δ+(ρu−1)ϑ.
Le us assume owa ds a con adic ion ha δ>δ
max. We dis inguish wo cases wi h
espec o he minimum min(A,Bδ):
1. The minimum is a ained a A, implying ha
˜
φ(xk)−˜
φ(xk+1)≥ρuηA
γ
LP
max
δ+(ρu−1)ϑ
≥ρuηA
γ
LP
max
δmax+(ρu−1)ϑ +C1.
o a cons an C1>0. Using he ac ha
δmax ≥ϑ(1−ρu)γ LP
max
ρuηA
by de ini ion o δmax, his implies ha ˜
φ(xk)−˜
φ(xk+1)≥C1>0.
2. The minimum is a ained a Bδ, implying ha
˜
φ(xk)−˜
φ(xk+1)≥ρuηBδ2
γ
LP
max +(ρu−1)ϑ
≥ρuηBδ2
max
γ
LP
max +(ρu−1)ϑ +C2
123
Con e gence o successi e linea p og amming… 583
o a cons an C2>0. We now use he ac ha
δmax ≥ϑ(1−ρu)γ LP
max
ρuηB
o deduce ha ˜
φ(xk)−˜
φ(xk+1)≥C2>0.
In ei he case ˜
φdec eases by min(C1,C2)>0 om xk o xk+1. Since his dec ease
is s ic ly posi i e and he e a e in ini ely many accep ed s eps in he sequence K,i
ollows ha ˜
φ(xk) ends o −∞, which is a con adic ion. I mus he e o e hold ha
δ≤δmax as desi ed. 
In e p e a ion o Theo em 3.14
In heo e ical e ms, he esul in Theo em 3.14 is as expec ed: he size o he c i ical
egion Cdepends on he s abiliza ion pa ame e ϑ, I we inc ease ϑ, Algo i hm 1can
ole a e a la ge amoun o noise a he cos o a dec eased accu acy wi h espec o he
c i icali y measu e ˜
. O cou se, p oblem (P) can gene ally also be unbounded. The
emaining case, whe e ˜
k(1)=0 o somek∈N, can in ol e di e en scena ios.
I k(1)=0 holds as well, he i e a e xkis a c i ical poin o (P), which is he ideal
si ua ion. O he wise, he noises δF(xk)and δF(xk)a ain alues such ha xkappea s
o be c i ical in he noisy model. In case o an uncons ained e sion o (NLP), his is
an amoun o a non-ze o g adien ha is canceled ou by noise.
Fo a unc ion F ha is no a lic ed by noise, i.e., sa is ying εF=εF=0, i holds
ha Mε
0=Mε
1=0, whe e Mε
0and Mε
1a e he cons an s om Lemma 3.4. This allows
us o se ϑ=0, whe eby we eco e he o iginal algo i hm discussed in [3]. I we
apply Theo em 3.14 in his si ua ion, i ollows om ϑ=0 ha δmax =0, implying
ha he egion C(δmax)con ains p ecisely he poin s c i ical wi h espec o ˜
φ, which
i sel coincides wi h φin his pa icula case. Thus, he o iginal con e gence esul [3,
Theo em 3.8] ollows o Algo i hm 1in he noiseless case.
As men ioned in he in oduc ion, we can also apply Algo i hm 1 o sol e smoo h
uncons ained nonlinea p oblems a ec ed by noise. To his end, we can se ω(x)=x,
achie ing a Lipschi z cons an o Lω=1. Lemma 3.12, speci ically (11), hen sugges s
a s abiliza ion o
ϑ≥2εF+εF
1−ρs
>2εF+εF,(22)
which may be weake han he s abiliza ion o εFanalyzed in [1]i εFbecomes
su icien ly la ge. This is pa icula ly ue o all εF>0 o he choice =2/(1−ρs),
which co esponds o he choice =2/(1−c2)in (8) in [1].
The easonis hees ima einLemma3.7 based on he con exi y o ω. Con e sely,
he au ho s o [1] ha e a Lipschi z con inuous de i a i e o he objec i e a hand. In
ha case, he c i icali y measu e sa is ies
x∈C(δ) ⇐⇒ −min
dLP≤1G(x)d≤δ,
123
584 C. Hansknech e al.
Table 1 Pa ame e s used o nume ical expe imen s
Symbol Explana ion Value
LP
0Ini ial LP us - egion adius 1
LP
max Maximum LP us - egion adius 10
0Ini ial us - egion adius 1
ρuS ep accep ance h eshold 0.1
ρsTh eshold o inc ease o 0.5
κlLowe bound o adjus men o a e ailed s ep 0.1
κuUppe bound o adjus men o a e ailed s ep 0.8
θLowe bound o adjus men o LP a e ailed s ep 0.5
ηFac o o ela i e dec ease o Cauchy s ep 0.1
τSho ening ac o o Cauchy line sea ch 0.5
which in u n is equi alen o G(x)being bounded abo e by a cons an .
4 Nume ical expe imen s
In o de o illus a e he pe o mance and examine he beha io o Algo i hm 1,
we implemen he algo i hm1in Py hon (3.11.5), using numpy [28] (1.26.0),
scipy [29] (1.11.3) (including HiGHS [23] (1.5.0) as LP sol e ), and Ipop [30]
(3.14.13) o sol e he espec i e subp oblems. We gene ally compa e he pe o mance
o he classical algo i hm (i.e., Algo i hm 1wi h a s abiliza ion o ϑ=0), wi h i s
s abilized coun e pa (whe e ϑ>0).
In e ms o e mina ion c i e ia, we i s o all impose an i e a ion limi , a e which
he algo i hm e mina es. Secondly, we moni o he LP us - egion adius, LP.I he
adius con ac s o a alue close o ze o (1 ×10−10), we see his as a ailu e o he
algo i hm and le i e mina e. Las ly, when he noise c i icali y ˜
k(1) alls below he
h eshold o 1 ×10−6, we e mina e he algo i hm, knowing ha he cu en i e a e is
e y close o being op imal. We hen examine he inal i e a e x , i.e., he i e a e xk
in Algo i hm 1o he i e a ion a which he e mina ion c i e ion becomes sa is ied.
I no indica ed o he wise, we choose he pa ame e s o Algo i hm 1acco ding o
he alues in Table 1and he s abiliza ion pa ame e ϑ∗
ε. In o de o ob ain inexac
e alua ions o a gi en unc ion F:Rn→Rpand i s de i a i e, we injec noise by
se ing
δF(x)=XF∈Rp,XF∼Bn(εF), and
δF(x)=XF∈Rp×n,XF∼Bnp(εF), (23)
whe e Bn(s)deno es he uni o m dis ibu ion on he n-dimensional Euclidean ball cen-
e ed a he o igin wi h adius s≥0. We can compu e a sample om his dis ibu ion
1A ailable a h ps://gi hub.com/ch hansk/noisy-nonlinea .
123
Con e gence o successi e linea p og amming… 585
by i s sampling n imes om a s anda d no mal dis ibu ion and scaling he esul ing
ec o [31] by i s Euclidean no m o ob ain a sample om he uni o m dis ibu ion on
Sn(1). We can hen use in e se ans o m sampling o ob ain a sui able adius in [0,s]
and escale he ec o acco dingly. The injec ed noise is bounded acco ding o he
noise le els εFand εFwhile being su icien ly unp edic able o signi ican ly a ec
he solu ion p ocess.
In Sec .4.1, we augmen an example o a quad a ic es p oblem om [1] wi h a
non-smoo h e m. We ob ain quali a i ely simila esul s in his case. Then we compa e
and isualize he di e en beha io s o he uns abilized algo i hm and he s abilized
algo i hm o he Rosenb ock es unc ion in Sec .4.2. In Sec .4.3, we apply he
algo i hm o an image econs uc ion p oblem wi h o al a ia ion egula iza ion and
assess he impac o di e en choices o he s abiliza ion pa ame e . Finally, in Sec . 4.4,
we apply he algo i hm in a penal y me hod o a small cons ained op imiza ion
p oblem om CUTes [32] as mo i a ed in he in oduc ion, which poin s o u u e
esea ch di ec ions. Sec ions4.1,4.2 and 4.4 use essen ially he same ype o a non-
smoo h objec i e unc ion ha includes an 1-penal y e m and we p o ide he equi ed
es ima es o i s Lipschi z cons an in Appendix B.
4.1 Failu e o he classical algo i hm
To illus a e he di e ence in pe o mance be ween he classical algo i hm and Algo-
i hm 1, we conside he case o 1-penalized op imiza ion p oblems o he o m
x→ (x)+λx1wi h a smoo h unc ion :Rn→R. I is clea ha hese p ob-
lems a e non-smoo h due o he p esence o he ·1 e m, while being exp essible as
p oblems o ype (P) based on sui able choices o ωand F. This p oblem class also
enables us o minimize ˜
kand ˜qko e he us egions de ined in e ms o LP and 
by sol ing linea o quad a ic p og ams espec i ely. Wha is mo e, he only cu a u e
in o ma ion in his p oblem class is due o , enabling us o ei he use he Hessian
o (o any quasi-New on app oxima ion) o ob ain he ma ices Bk. We speci ically
examine he case whe e is a quad a ic o he o m
(x)=1
2x,Dx,
whe e Dis he ma ix in Rn×n o n=8 gi en as
D=diag(10−5,10−4.75,10−4.5,...,10−3.25),
aken om [1], whe e his op imiza ion p oblem has been s udied wi hou an 1-
penal y. I is appa en ha he op imal solu ion o his ins ance o (P)isx∗=0. We
se he pa ame e λ o 1 ×10−2while injec ing noise acco ding o (23) wi h noise
le els εF=1×10−1and εF=1×10−5, and ini ialize Algo i hm 1wi h he ini ial
poin x0=(1000,0,...,0)T, limi ing he numbe o i e a ions o 50, and pe o ming
quad a ic s eps based on he ue Hessian D.
We show an example o he di e ence in pe o mance in Fig. 1, whe e he alues
o he educ ion a io a e clipped o ±5 in o de o p ope ly display he esul s. We
123
586 C. Hansknech e al.
see ha he classical algo i hm pe o ms d ama ically wo se han i s s abilized coun-
e pa . Indeed, he classical algo i hm s alls almos immedia ely, due o he educ ion
a io ρkbecoming un eliable. Consequen ly, he LP us egion collapses, and he
classical algo i hm makes no p og ess owa ds op imali y. Con e sely, he addi ion o
a s abiliza ion yields an algo i hm apidly app oaching he op imum, bo h in e ms
o p imal dis ance and objec i e alue while main aining a easonably la ge LP us -
egion adius. Simila ly, noisy and noiseless c i icali y dec ease apidly h oughou he
i e a ions o he s abilized algo i hm. Un o una ely, he c i icali y bound es ablished
in Theo em 3.14 a ains a alue o δmax ≈54 000, limi ing i s use in e ms o he
c i icali y ac ually achie ed h oughou he i e a ions.
We would like o poin ou ha he ailu e o he classical algo i hm is no gua an eed
in his scena io: By unning he expe imen wi h 100 di e en andom seeds we ound
ha he classical algo i hm s alls in abou hal (57) o he cases, while pe o ming well
in he o he hal . Con e sely, he s abilized algo i hm consis en ly pe o ms well in all
cases. I s cha ac e is ics a e quali a i ely simila o he case ha is depic ed in Fig.1.
A key p oblem o he classical algo i hm is he e o e i s un eliabili y when applied o
noisy unc ions.
4.2 A a ian o he Rosenb ock p oblem
Following he p e ious expe imen s conduc ed based on he quad a ic unc ion, we
go on o examine he pe o mance on a a ian o he amous Rosenb ock unc ion,
gi en by
R(x,y):=(a−x)2+b(y−x2)2
wi h pa ame e s o a=1, b=100. The Rosenb ock unc ion has a unique op imum a
(x∗,y∗)=(a,a2), i.e., a (1,1) o ou choice o pa ame e s. We modi y he p oblem
by adding a penal y o λ(x,y)−(x∗,y∗)1wi h a alue o λ=1×10−1, yielding
a p oblem o ype (P) ha ing he same global op imum as R. We show an example
o he di e ence in pe o mance be ween he classical and s abilized algo i hms in
Fig.2. The igu e shows he ajec o ies gene a ed by Algo i hm 1wi h and wi hou
s abiliza ion s a ing a (x0,y0)=(−1.5,0), injec ing noise acco ding o (23) o
di e en alues o εFand a ixed alue o εF=1×10−5, pe o ming quad a ic s eps
acco ding o he ue Hessian o Rwi h an i e a ion limi o 50.
Examining he ajec o ies o he classical algo i hm, shown in Fig. 2a, we ind ha
o di e en alues o εF, he ajec o ies a e ini ially almos iden ical, un il he algo-
i hm s alls a poin s wi h a dis ances o he op imum inc easing wi h εF. Con e sely,
he ajec o ies o he s abilized algo i hm, shown in Fig. 2b, a y signi ican ly o di -
e en noise le els. Howe e , he s abiliza ion yields ajec o ies leading signi ican ly
close o he op imum han hose o he classical algo i hm e en o la ge noise le -
els. This is con i med by he s a is ics shown in Fig. 3, displaying he dis ibu ion o
he dis ance o he op imum o a ious noise le els o 100 di e en andom seeds,
demons a ing ha he s abilized algo i hm consis en ly ou pe o ms he classical one,
in pa icula o la ge noise le els.
123

Con e gence o successi e linea p og amming… 587
Fig. 1 Pe o mance on an 1-penalized quad a ic p oblem o e 50 i e a ions o Algo i hm 1wi h noise
le els o εF=1×10−1and εF=1×10−5.Thex-axes always show he i e a ion coun o Algo i hm 1,
he y-axes show he quan i ies indica ed in he cap ions below he espec i e subplo s
4.3 Image econs uc ion
Al hough his is no he ocus o his a icle, we also p o ide a compu a ional example
ha has a meaning ul p oblem size. Speci ically, we conside an a i icial ask o
econs uc ing an image unde noisy obse a ions. Tha is we seek o eco e a ma ix
Y∈RM×Nwi h alues no malized o be in [0,1]. In ou se ing, Yis only a ailable
in he o m o noisy obse a ions. Speci ically, o an inpu X∈RM×N, he ideli y
123
588 C. Hansknech e al.
Fig. 2 T ajec o ies o he modi ied Rosenb ock p oblem plo ed o e he shi ed c i icali y 1 +φ(x)−
mindLP≤1ω(F(x)+F(x)d), which allows o show i on a loga i hmic scale. The ma ke s show he
posi ion o he inal i e a e
o X, gi en by he squa ed F obenius no m o X−Y,1
2X−Y2
F,aswellasi s
de i a i e wi h espec o Xcanno be e alua ed. Ins ead, we ha e access o he map
X→ 1
2X−˜
Y2
F, whe e ˜
Yis a noisy e sion o Y, ed awn o each guess X.We
ob ain he e m ˜
Yby sampling om a componen wise uni o m dis ibu ion
δY(X)=YF∈RM×N,YF∼UM×N(−εimg,ε
img),
and se ing ˜
Y o Y+δY(X)clipped back o ha e coe icien s in [0,1]. The amoun o
noise injec ed o he image is in u n go e ned by he pa ame e εimg ≥0. This noise
model ansla es in o noise injec ed in o he e alua ions o Fand F, which can be
123
Con e gence o successi e linea p og amming… 589
Fig. 3 Dis ibu ion o he dis ance be ween he inal i e a e x and noiseless op imum x∗ o di e en
alues o he noise le el εF
es ima ed in e ms o εimg,M, and N(see Appendix B) while no con o ming o he
noise model (23). We also impose an aniso opic o al a ia ion (TV) egula iza ion
penal y, de ined as
TV(X):=
M−1

i=1
N

j=1|Xi+1,j−Xi,j|+
M

i=1
N−1

j=1|Xi,j+1−Xi,j|,
o ou objec i e, u ning he p oblem non-smoo h, balancing o ideli y and egula i y
by a pa ame e λ>0. The egula iza ion e m can be exp essed as AM,NX1wi h
a sui able ma ix AM,N. Consequen ly, we can o mula e he econs uc ion p oblem
as p oblem o ype (P), consis ing o a smoo h e m ( he ideli y), and an 1-penalized
linea unc ion. Na u ally, he egula iza ion does no su e om any noise.
Based on a egula iza ion pa ame e o λ=5×10−3we econs uc he image
showninFig.4a. To a oid ha ing o sol e la ge quad a ic p oblems, we do no compu e
quad a ic s eps and op o ins ead inc ease he numbe o i e a ions o 100 s a ing om
X0=0. As a baseline, Fig. 4b shows he image when we apply Algo i hm 1 o he
o iginal image (i.e., se ing εimg =0). The es o ed image closely esembles he
o iginal one.
We p oceed o s udy he e ec o he alue o ϑon he quali y o he econs uc ed
image. In p inciple, i mus hold ha ϑ≥ϑ∗
εin o de o he c i icali y o p o ably
con e ge. I is howe e unclea whe he se ing ϑ o ϑ∗
εyields he bes esul s in
p ac ice. The la ge alue o δmax seen in Sec . 4.1 seems o sugges ha (11) is a he
pessimis ic. We he e o e examine he pe o mance o Algo i hm 1 o alues o ϑno
necessa ily sa is ying he inequali y.
123
590 C. Hansknech e al.
Fig. 4 Sample image o he image econs uc ion
To gauge pe o mance, we eco d bo h he o iginal and noisy objec i e a e he
i e a ions. The esul s, shown in Fig.5, demons a e he e ec o ϑ: Fo small s abiliza-
ion alues, Algo i hm 1s alls ea ly on, as was he case in ou p e ious expe imen s.
As we inc ease ϑ, he e appea s o be an op imal choice o small egion, whe e bo h
he noisy and he noiseless e alua ion o he inal objec i e a e minimized. This e ec
is mo e p onounced o highe alues o εimg, whe e he noiseless objec i e o ϑ=0
is abou 4 imes as la ge as ha o he op imal choice o ϑ. I is in e es ing o see
ha his swee spo also shows in he noisy objec i e, sugges ing ha noisy obse -
a ions may be su icien o ind i . Las ly, as we inc ease ϑbeyond he swee spo ,
he inal objec i e inc eases sha ply. This is likely due o he case ha he algo i hm
simply accep s oo many s eps, e en when hey a e in ac disad an ageous in e ms
o p og essing owa ds an op imum. Ul ima ely, o a su icien ly la ge alue o ϑ,all
s eps a e accep ed, which, as he inal objec i e sugges s, leads o poo solu ions. The
alues o ϑ∗
εa e gi en by 4 ×104,2×105, and 4 ×105 o he espec i e noise le els,
signi ican ly exceeding he op imal alues and beyond he poin , whe e all s eps a e
accep ed.
We also ind ha he objec i es a e consis en wi h he isual appea ance o he
econs uc ed images, shown in Fig. 6: While se ing ϑ o ze o yields sa is ac o y
esul s, e en hough a g ainy appea ance emains o la ge noise le els, a disp opo -
iona ely la ge alue o ϑp oduces a dis o ed esul wi h isible a i ac s. Fo ou bes
guess o ϑ, he es o ed images do no su e om a i ac s and closely esemble he
o iginal one e en o la ge noise le els.
4.4 Cons ained op imiza ion
As a inal example and in o de o demons a e he possible use o Algo i hm 1as
a subp oblem sol e in cons ained op imiza ion algo i hms, we s udy a cons ained
op imiza ion p oblem o he ype (NLP). Speci ically, we examine he beha io o
Algo i hm 1when applied o he HS71 benchma k p oblem o he CUTes [32]
123
Con e gence o successi e linea p og amming… 597
Since he only di e ence be ween he linea ized and quad a ic model is he
quad a ic e m, we ha e ha
1
2(αk/τ)2dLP
k,BkdLP
k≥(1−η) ˜
φ(xk)−˜
k(αdLP
k/τ).
The le hand side can be bounded abo e by using Assump ion 4and ela ion (6)
o yield
1
2(αk/τ)2dLP
k,BkdLP
k≤1
2(αk/τ)2βγ2dLP
k2
LP
≤1
2(αk/τ)2βγ2dLP
kLPLP
k.
Simila ly, o he igh hand side we can use Lemmas 3.7 and 3.8 o ob ain
˜
φ(xk)−˜
k(α/τdLP
k)≥αk/τ ˜
φ(xk)−˜
k(dLP
k)
≥αk/τ min(1,
LP
k)˜
k(1),
Pu ing hese inequali ies oge he yields he bound
dC
kLP =αkdLP
kLP ≥2(1−η)τ
βγ2min 1,1
LP
k˜
k(1)
equi ed o comple e he p oo .

P oo o Lemma 3.13 Le k0be he index o he las accep ed s ep. Then, xk+1=
xk=:x∗ o all k>k0. Consequen ly, a e inishing he k0- he i e a ion, ˜
k(1)s ays
a a cons an alue o δ≥0. Wha is mo e, due o he ejec ion o he s eps ollowing
i e a ion k0i holds o all k>k0 ha k+1≤κuk<
k(since κu<1). The e o e,
k ends o ze o. Recall om Lemma 3.12 ha i δ>0, hen kis bounded away
om ze o. The e o e, since k ends o ze o, i mus hold ha δ=0. 
B Es ima ions
Lipschi z cons an o he 1-penal y unc ion
In he ollowing, we gi e an es ima ion o he Lipschi z cons an Lωo he penal y
unc ion ω:R×Rm→R,ω(x,y)=x+νy1, based on he cons an ν>0 and
he dimension m∈N. Since we use his unc ion in all o he examples in Sec .4, and
since he alue o ϑ∗
εdepends on he alue o Lω, we make i s de i a ion explici . To
ob ain an op imal alue o Lω, we sol e he op imiza ion p oblem
max
x,y,x,y|ω(x,y)−ω(x,y)|
s. . (x−x)2+y−y2≤1,
123

598 C. Hansknech e al.
i.e., we maximize he di e ence in alues o ωwhile con olling he dis ance be ween
he poin s (x,y)and (x,y). Obse e ha
|ω(x,y)−ω(x,y)|=|(x−x)+νy−y1|,
om which i ollows ha bo h he objec i e and he cons ain alue only depend on
x−xand y−y. We can he e o e simpli y he p oblem by se ing y=0 and y=0:
max
x,y|x+νy1|
s. . x2+y2≤1.
We can simpli y he p oblem u he by ealizing ha we can assume bo h xand y
o be non-nega i e, elimina ing he absolu e alue in he objec i e. The la ges a io
o νy1o e y2is achie ed by se ing all en ies o y o he same alue y0∈R,
yielding he p oblem
max
x,y0
x+νmy0
s. . x2+my2
0≤1
x,y0≥0.
By se ing z:=√my0, we ob ain he p oblem
max
x,zx+ν√mz
s. . x2+z2≤1
x,z≥0.
The op imal solu ion o his p oblem is a ained a
x∗
z∗=1
√1+ν2m1
ν√m,
yielding he objec i e √1+ν2m=:Lω.
Image Recons uc ion
In he ollowing, we p o ide es ima ions ega ding he noise le els associa ed wi h he
image ideli y map in oduced in Sec .4.3. Recall ha he squa ed F obenius no m o
ama ixA∈RM×Nis gi en by A2
F:= M
i=1N
j=1a2
ij. Thus, i |aij|≤ε o a
gi en ε>0, i ollows ha
A2
F≤
M

i=1
N

j=1
ε2=ε2MN,
123
Con e gence o successi e linea p og amming… 599
and he e o e, ha AF≤ε√MN. The noisy ideli y unc ion ˜
F(X)sa is ies he
iden i ies
˜
F(X)=1
2X−˜
Y2
F=1
2X−(Y+δY(X))2
F
=1
2X−Y2
F+X−Y,δ
Y(X)F+1
2δY(X)2
F,
whe e ·,·Fdeno es he inne p oduc ha induces he F obenius no m. Since he
en ies o Xand Ya e in [0,1], and he e o e ha e absolu e alues bounded by 1, i
ollows ha X−YF≤√MN. The choice o dis ibu ion implies ha he alues
in δY(X)a e bounded by ±εimg, and he e o e ha δY(X)F≤εimg√MN, om
which i ollows ha
|˜
F(X)−F(X)|≤X−YFδY(X)F+1
2δY(X)2
F≤εimg +1
2ε2
imgMN,
by means o he Cauchy–Schwa z inequali y o ·,·F. Fu he mo e, i holds o any
ma ix A∈Rm×n ha A≤AF. Any es ima ion wi h espec o he F obenius
no m he e o e also p oduces an uppe bound o ou s anda d no m ·. Speci -
ically, he noise le el εimg yields a co esponding alue o εF. Simila ly, i holds
ha G(X)=F(X)−δY(X), and he e o e G(X)−F(X)F≤δY(X)F≤
εimg√MN, co esponding o a alue o εF.
Re e ences
1. Sun, S., Nocedal, J.: A us egion me hod o noisy uncons ained op imiza ion. Ma h. P og am. 66,
1–28 (2023). h ps://doi.o g/10.1007/s10107-023-01941-9
2. By d, R.H., Gould, N.I., Nocedal, J., Wal z, R.A.: An algo i hm o nonlinea op imiza ion using linea
p og amming and equali y cons ained subp oblems. Ma h. P og am. 100(1), 27–48 (2003). h ps://
doi.o g/10.1007/s10107-003-0485-4
3. By d, R.H., Gould, N.I., Nocedal, J., Wal z, R.A.: On he con e gence o successi e linea -
quad a ic p og amming algo i hms. SIAM J. Op im. 16(2), 471–489 (2005). h ps://doi.o g/10.1137/
S1052623403426532
4. W igh , S., Nocedal, J., e al.: Nume ical Op imiza ion, 2nd edn. Sp inge , Be lin (2006). h ps://doi.
o g/10.1007/978-0-387-40065-5
5. Tibshi ani, R.: Reg ession sh inkage and selec ion ia he lasso. J. R. S a . Soc. Se . B Me hodol. 58(1),
267–288 (1996). h ps://doi.o g/10.1111/j.2517-6161.1996. b02080.x
6. Candes, E.J., Rombe g, J.K., Tao, T.: S able signal eco e y om incomple e and inaccu a e measu e-
men s. Commun. Pu e Appl. Ma h. A J. Issued Cou an Ins . Ma h. Sci. 59(8), 1207–1223 (2006).
h ps://doi.o g/10.1002/cpa.20124
7. Fukushima, K.: Cogni on: a sel -o ganizing mul ilaye ed neu al ne wo k. Biol. Cybe ne . 20(3), 121–
136 (1975). h ps://doi.o g/10.1007/BF00342633
8. Aspelmeie , T., Cha i ha, C., Luke, D.R.: Local linea con e gence o he admm/douglas- ach o d
algo i hms wi hou s ong con exi y and applica ion o s a is ical imaging. SIAM J. Imaging Sci. 9(2),
842–868 (2016). h ps://doi.o g/10.1137/15M103580X
9. Ca is, C., Gould, N.I., Toin , P.L.: On he e alua ion complexi y o composi e unc ion minimiza ion
wi h applica ions o noncon ex nonlinea p og amming. SIAM J. Op im. 21(4), 1721–1739 (2011).
h ps://doi.o g/10.1137/11082381X
123
600 C. Hansknech e al.
10. Apka ian, P., Noll, D., Ra anbod, L.: Nonsmoo h bundle us - egion algo i hm wi h applica ions o
obus s abili y. Se -Valued Va . Anal. 24(1), 115–148 (2016). h ps://doi.o g/10.1007/s11228-015-
0352-5
11. Boyd, S., Pa ikh, N., Chu, E., Pelea o, B., Ecks ein, J., e al: Dis ibu ed op imiza ion and s a is ical
lea ning ia he al e na ing di ec ion me hod o mul iplie s. Found. T ends®Mach. Lea n. 3(1), 1–122
(2011). h ps://doi.o g/10.1561/2200000016
12. Nes e o , Y.: G adien me hods o minimizing composi e unc ions. Ma h. P og am. 140(1), 125–161
(2013). h ps://doi.o g/10.1007/s10107-012-0629-5
13. San osa, F., Symes, W.W.: Linea in e sion o band-limi ed e lec ion seismog ams. SIAM J. Sci. S a .
Compu . 7(4), 1307–1330 (1986). h ps://doi.o g/10.1137/0907087
14. Han, S.-P., Mangasa ian, O.L.: Exac penal y unc ions in nonlinea p og amming. Ma h. P og am.
17(1), 251–269 (1979). h ps://doi.o g/10.1007/BF01588250
15. Shi, H.-J.M., Xie, Y., By d, R., Nocedal, J.: A noise- ole an quasi-new on algo i hm o uncons ained
op imiza ion. SIAM J. Op im. 32(1), 29–55 (2022). h ps://doi.o g/10.1137/20M1373190
16. I win, B., Habe , E.: Secan penalized b gs: a noise obus quasi-new on me hod ia penalizing he
secan condi ion. Compu . Op im. Appl. 84(3), 651–702 (2023). h ps://doi.o g/10.1007/s10589-022-
00448-x
17. Cao, L., Be ahas, A.S., Scheinbe g, K.: Fi s -and second-o de high p obabili y complexi y bounds
o us - egion me hods wi h noisy o acles. Ma h. P og am. 66, 1–52 (2023). h ps://doi.o g/10.1007/
s10107-023-01999-5
18. Gal, R., Habe , E., I win, B., Saleh, B., Zi , A.: How o ca ch a lion in he dese : on he solu ion o
he co e age di ec ed gene a ion (cdg) p oblem. Op im. Eng. 22(1), 217–245 (2021). h ps://doi.o g/
10.1007/s11081-020-09507-w
19. Cu is, F.E., Scheinbe g, K., Shi, R.: A s ochas ic us egion algo i hm based on ca e ul s ep no mal-
iza ion. In o ms J. Op im. 1(3), 200–220 (2019). h ps://doi.o g/10.1287/ijoo.2018.0010
20. Be ahas, A.S., By d, R.H., Nocedal, J.: De i a i e- ee op imiza ion o noisy unc ions ia quasi-
new on me hods. SIAM J. Op im. 29(2), 965–993 (2019). h ps://doi.o g/10.1137/18M1177718
21. Xie, Y., By d, R.H., Nocedal, J.: Analysis o he BFGS me hod wi h e o s. SIAM J. Op im. 30(1),
182–209 (2020). h ps://doi.o g/10.1137/19M1240794
22. Gu obi Op imiza ion, LLC: Gu obi Op imize Re e ence Manual (2022). h ps://www.gu obi.com
23. Huang u, Q., Hall, J.J.: Pa allelizing he dual e ised simplex me hod. Ma h. P og am. Compu . 10(1),
119–142 (2018). h ps://doi.o g/10.1007/s12532-017-0130-5
24. By d, R.H., Nocedal, J., Wal z, R.A.: Kni o: an in eg a ed package o nonlinea op imiza ion. In:
La ge-Sscale Nonlinea Op imiza ion, pp. 35–59. Sp inge , Be lin (2006). h ps://doi.o g/10.1007/0-
387-30065-1_4
25. Fle che , R.: P ac ical Me hods o Op imiza ion: Vol. 2: Cons ained Op imiza ion (1981). h ps://doi.
o g/10.1002/9781118723203
26. Yuan, Y.-x: Condi ions o con e gence o us egion algo i hms o nonsmoo h op imiza ion. Ma h.
P og am. 31(2), 220–228 (1985). h ps://doi.o g/10.1007/BF02591750
27. Rocka ella , R.T., We s, R.J.-B.: Va ia ional Analysis, ol. 317. Sp inge , Be lin (2009). h ps://doi.
o g/10.1007/978-3-642-02431-3
28. Ha is, C.R., Millman, K.J., an de Wal , S.J., Gomme s, R., Vi anen, P., Cou napeau, D., Wiese , E.,
Taylo , J., Be g, S., Smi h, N.J., Ke n, R., Picus, M., Hoye , S., an Ke kwijk, M.H., B e , M., Haldane,
A., del Río, J.F., Wiebe, M., Pe e son, P., Gé a d-Ma chan , P., Sheppa d, K., Reddy, T., Weckesse , W.,
Abbasi, H., Gohlke, C., Oliphan , T.E.: A ay p og amming wi h NumPy. Na u e 585(7825), 357–362
(2020). h ps://doi.o g/10.1038/s41586-020-2649-2
29. Vi anen, P., Gomme s, R., Oliphan , T.E., Habe land, M., Reddy, T., Cou napeau, D., Bu o ski,
E., Pe e son, P., Weckesse , W., B igh , J., an de Wal , S.J., B e , M., Wilson, J., Millman, K.J.,
Mayo o , N., Nelson, A.R.J., Jones, E., Ke n, R., La son, E., Ca ey, C.J., Pola , ˙
I, Feng, Y., Moo e,
E.W., Vande Plas, J., Laxalde, D., Pe k old, J., Cim man, R., Hen iksen, I., Quin e o, E.A., Ha is,
C.R., A chibald, A.M., Ribei o, A.H., Ped egosa, F., an Mulb eg , P.: SciPy 1.0 Con ibu o s: SciPy
1.0: undamen al algo i hms o scien i ic compu ing in py hon. Na . Me hods 17, 261–272 (2020).
h ps://doi.o g/10.1038/s41592-019-0686-2
30. Wäch e , A., Biegle , L.T.: On he implemen a ion o an in e io -poin il e line-sea ch algo i hm o
la ge-scale nonlinea p og amming. Ma h. P og am. 106(1), 25–57 (2006). h ps://doi.o g/10.1007/
s10107-004-0559-y
123
Con e gence o successi e linea p og amming… 601
31. Ma saglia, G.: Choosing a poin om he su ace o a sphe e. Ann. Ma h. S a . 43(2), 645–646 (1972).
h ps://doi.o g/10.1214/aoms/1177692644
32. Gould, N.I., O ban, D., Toin , P.L.: Cu es : a cons ained and uncons ained es ing en i onmen wi h
sa e h eads o ma hema ical op imiza ion. Compu . Op im. Appl. 60(3), 545–557 (2015). h ps://doi.
o g/10.1007/s10589-014-9687-3
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