On the forward–backward method with nonmonotone linesearch for infinite-dimensional nonsmooth nonconvex problems

Azmi, Behzad; Be n eu he , Ma co
A icle — Published Ve sion
On he o wa d–backwa d me hod wi h nonmono one
linesea ch o in ini e-dimensional nonsmoo h noncon ex
p oblems
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: Azmi, Behzad; Be n eu he , Ma co (2025) : On he o wa d–backwa d me hod
wi h nonmono one linesea ch o in ini e-dimensional nonsmoo h noncon ex p oblems,
Compu a ional Op imiza ion and Applica ions, ISSN 1573-2894, Sp inge US, New Yo k, NY, Vol. 91,
Iss. 3, pp. 1263-1308,
h ps://doi.o g/10.1007/s10589-025-00684-x
This Ve sion is a ailable a :
h ps://hdl.handle.ne /10419/323337
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) 91:1263–1308
h ps://doi.o g/10.1007/s10589-025-00684-x
On he o wa d–backwa d me hod wi h nonmono one
linesea ch o in ini e-dimensional nonsmoo h noncon ex
p oblems
Behzad Azmi1·Ma co Be n eu he 2
Recei ed: 31 May 2023 / Accep ed: 9 Ap il 2025 / Published online: 8 May 2025
© The Au ho (s) 2025
Abs ac
This pape p o ides a comp ehensi e s udy o he nonmono one o wa d–backwa d
spli ing (FBS) me hod o sol ing a class o nonsmoo h composi e p oblems in
Hilbe spaces. The objec i e unc ion is he sum o a F éche di e en iable (no
necessa ily con ex) unc ion and a p ope lowe semicon inuous con ex (no neces-
sa ily smoo h) unc ion. These p oblems appea , o example, equen ly in he con ex
o op imal con ol o nonlinea pa ial di e en ial equa ions (PDEs) wi h nonsmoo h
spa si y-p omo ing cos unc ionals. We discuss he con e gence and complexi y o
FBS equipped wi h he nonmono one linesea ch unde di e en condi ions. In pa -
icula , R-linea con e gence will be de i ed unde quad a ic g ow h- ype condi ions.
We also in es iga e he applicabili y o he algo i hm o p oblems go e ned by PDEs.
Nume ical expe imen s a e also gi en ha jus i y ou heo e ical indings.
Keywo ds Nonsmoo h noncon ex op imiza ion ·Fo wa d–backwa d algo i hm ·
In ini e-dimensional p oblems ·Nonmono one linesea ch ·Quad a ic g ow h ·
PDE-cons ained op imiza ion
Ma hema ics Subjec Classi ica ion 90C26 ·49M41 ·65K05 ·65K15 ·49M37 ·
65J22
BBehzad Azmi
[email p o ec ed]
Ma co Be n eu he
ma co.be n eu he @i .uni-s u ga .de
1Depa men o Ma hema ics and S a is ics, Uni e si y o Kons anz, Uni e si ä ss aße 10, 78457
Kons anz, Ge many
2Ins i u e o Indus ial Manu ac u ing and Managemen IFF, Uni e si y o S u ga , Allmand ing 35,
70569 S u ga , Ge many
123
1264 B. Azmi, M. Be n eu he
1 In oduc ion
In his wo k, we a e conce ned wi h he ollowing composi e p oblem
min
u∈H(u):= F(u)+R(u), (P)
whe e His a eal Hilbe space, Fis a con inuously F éche di e en iable unc ion
(possibly noncon ex), and Ris a con ex unc ion whose p oximal ope a o is assumed
o be explici ly compu able. The p ecise de ails will be in oduced in Sec . 2. P oblems
o he o m (P) appea in se e al ields o applica ion such as op imal con ol p oblems
[1,2], sys em iden i ica ion, signal, and image p ocessing [3], machine lea ning, and
s a is ics [4].
A guably one o he mos well-known algo i hms o sol ing p oblem (P)is
o wa d–backwa d spli ing (FBS), also known as he p oximal g adien me hod [3,
5], which is he gene aliza ion o he classical g adien me hod o p oblems wi h an
addi ional nonsmoo h e m (see (7)). The i e a ions o FBS a e de ined by
uk+1=P ox 1
αkRuk−1
αk∇F(uk) o k∈N0,(1)
whe e he s ep-sizes αk>0 a e supposed o be chosen in a way ha gua an ees
con e gence o he algo i hm and accele a es i . I is known ha he global con e gence
o FBS is o be sublinea o o de (1/k) o he con ex case [5], whe e ks ands o he
numbe o i e a ions. This o de can be imp o ed o (1/k2)using an ine ial a ian
o he algo i hm based on Nes e o ’s accele a ed echniques [6,7]. Con e gence o
he i e a es o FBS o a c i ical poin o p oblem (P), e en o he noncon ex case, has
been shown o unc ions sa is ying he Ku dyka–Łojasiewicz p ope y e.g., [8–12]
o quad a ic g ow h e o bounds e.g., [13–16]. Due o he simplici y and e iciency
o FBS, i s con e gence, complexi y, and applicabili y ha e been ex ensi ely s udied,
making i an ongoing a ea o ac i e esea ch. Nume ous s ep-size s a egies ha e
been p oposed and analyzed wi hin he con ex o FBS unde a ious assump ions
and s uc u es. Fo s uc u ed noncon ex ini e-dimensional p oblems, wo ks such as
[17–19] ha e ocused on he ine ial me hod and cons an s ep-size s a egies, while
[20–25] ha e explo ed linesea ch s a egies based on unc ion e alua ions, as well as
quasi-New on and New on- ype di ec ions. Addi ionally, o p oblem (P) posed in an
in ini e-dimensional Hilbe space, e e ences such as [13,26–31] ha e in es iga ed
FBS assuming he con exi y o F, wi h [31] also add essing D.C. p og amming. In
case whe e Fis no necessa ily con ex, we can also men ion [32,33], which explo e
a class o inexac us egion me hods o ensu e he con e gence o FBS and apply
hem o p oblems go e ned by PDEs.
As is well-known o smoo h p oblems, nonmono one linesea ch s a egies appea
o be nume ically e icien in si ua ions whe e a mono one scheme is o ced o p op-
aga e along he bo om o a na ow, cu ed alley. Addi ionally, because hey allow
o inc eases in unc ion alues, hey can be e ec i ely combined wi h spec al g adi-
en me hods, such as he Ba zilai-Bo wein (BB) s ep-sizes [34,35], which na u ally
exhibi nonmono one beha io . Building on he nonmono one app oach de eloped by
123
On he o wa d–backwa d me hod wi h nonmono one… 1265
G ippo e al. [36], W igh e al. [37] p oposed a nonmono one FBS o nonsmoo h
con ex composi e p oblems posed in Rn. The con e gence o his app oach, known
as SpaRSA, was u he s udied in [38], whe e he au ho s demons a ed he o de o
(1/k)con e gence and R-linea con e gence o con ex and s ongly con ex unc-
ions, espec i ely. Ve y ecen ly, in [39], he au ho s p o ed con e gence o a c i ical
poin o his scheme o ini e-dimensional nonsmoo h noncon ex composi e unc ions
unde milde condi ions, speci ically, local Lipschi z con inui y o he g adien o he
smoo h pa and uni o m con inui y o he objec i e unc ion on i s le el se s.
F om a compu a ional pe spec i e, bo h classical g adien and FBS me hods can be
accele a ed i inco po a ed wi h he BB s ep-sizes. These s ep-sizes app oxima e he
cu a u e o he Hessian o he smoo h pa o he objec i e unc ion and a e pa ic-
ula ly e icien in he con ex o PDE-cons ained op imiza ion [34,40]. Fo s ongly
quad a ic unc ions F, R-linea con e gence o he BB s ep-sizes has been es ablished
o (P) p o ided he condi ion numbe o he quad a ic ope a o is su icien ly small
(< 2);see[34, Rema k 3.4]. Howe e , e en o s ongly quad a ic unc ions Fwi h
condi ion numbe s la ge han 2, con e gence o he BB s ep-sizes is no clea . Thus, o
gua an ee con e gence, one needs o combine he BB s ep-sizes wi h a nonmono one
linesea ch, which elies on unc ion e alua ions.
Weak and s ong con e gence can be dis inguished only in he in ini e-dimensional
se ing. In p ac ice, nume ical solu ions o in ini e-dimensional p oblems a e ypically
ob ained by implemen ing algo i hms o ini e-dimensional app oxima ions. How-
e e , analyzing he con e gence o hese algo i hms in he in ini e-dimensional con ex
is c ucial o ensu ing he nume ical obus ness and s abili y o he ini e-dimensional
app oxima ions. Such p ope ies a e exp essed by he so-called mesh-independen
p inciple (MIP); see, e.g., [40–46]. Roughly speaking, MIP uses esul s om in ini e-
dimensional con e gence o p edic he con e gence p ope ies o ini e-dimensional
app oxima ions (disc e ized p oblems). Addi ionally, MIP o e s a heo e ical oun-
da ion o de eloping e inemen s a egies; see, e.g., [47].
In ligh o he abo e discussion, we in es iga e he well-posedness, con e gence,
and complexi y o he nonmono one FBS o p oblems o he o m (P) posed in
in ini e-dimensional Hilbe spaces, unde a ious assump ions such as noncon ex-
i y, con exi y, and quad a ic g ow h- ype condi ions. These esul s also apply o
ini e-dimensional p oblems, whe e ou con e gence and complexi y analyses and
assump ions di e om hose in p e ious wo ks [37–39]. No ably, he con e gence o
his app oach unde quad a ic g ow h- ype condi ions, and i s wo s -case e alua ion
complexi y o eaching an app oxima e s a iona y poin ha e no been p e iously
in es iga ed. We will clea ly ou line ou con ibu ions in he nex sec ion.
In pa icula , we in es iga e he applicabili y o he nonmono one FBS o p ob-
lems go e ned by PDEs. Despi e i s nume ical e iciency, o he bes o ou knowledge,
his app oach has no ye been s udied o in ini e-dimensional p oblems. Fo hese
p oblems, due o he lack o compac ness in he s ong opology, we need o explo e
con e gence in he weak opology, which in ol es s udying no ions o sequen ial
con inui y o some ope a o s wi h espec o he weak opology. He e, he nonmono-
onici y o he app oach, and wo king wi h he weak opology a e wo issues ha we
o e come wi h ou analysis using he Lipschi z con inui y o he g adien mapping (see
De ini ion 1). We will also highligh he challenges and di e ences ha a ise when
123
1266 B. Azmi, M. Be n eu he
conside ing in ini e-dimensional spaces a e each p oo . Addi ionally, we in es iga e
and discuss he applicabili y o ou assump ions and, consequen ly, ou esul s o wo
examples o nonsmoo h noncon ex p oblems wi h PDEs.
Con ibu ions
Mo e p ecisely, he con ibu ions o his wo k can be summa ized as ollows:
(i) S a ing wi h he noncon ex case, we p o e well-posedness o he algo i hm
e en wi hou Lipschi z con inui y o he g adien o F. Unde he global Lipschi z
con inui y o he g adien o F, we p o e he global con e gence o he algo i hm
wi h complexi y (1/√k). To be mo e p ecise, we show ha he no m o he p ox-
g adien mapping o i e a es anishes wi h complexi y (1/√k). We also es ablish
ha e e y weak sequen ial clus e poin o i e a es is a s a iona y poin .
(ii) We de i e he wo s -case e alua ion complexi y o inding an ε ol-s a iona y
poin . Mo e p ecisely, we gi e es ima es on he maximal numbe o he objec-
i e unc ion and p ox-g ad ope a o e alua ions o compu ing an app oxima e
s a iona y poin wi h a use -de ined accu acy h eshold ε ol >0.
(iii) In he con ex se ing, elying on he concep o quasi-Feje sequences, we a e able
o ex end p e iously es ablished esul s o global con e gence, bo h in e ms o
unc ion alues and i e a es wi h espec o he weak sequen ial opology. Fu he ,
we show ha he con e gence is sublinea o o de (1/k)in unc ion alues.
(i ) Unde quad a ic g ow h- ype condi ions, we show global R-linea con e gence,
bo h in e ms o unc ion alues and i e a es. The p oo o he la e is mo e deli-
ca e o in ini e-dimensional p oblems since he ansi ion om weak sequen ial
con e gence o s ong con e gence is no s aigh o wa d.
( ) Finally, aiming a op imiza ion p oblems go e ned by PDEs, we discuss he alid-
i y o he con e gence esul s o he algo i hm wi hou s ong Lipschi z con inui y
o ∇F. Ou heo e ical amewo k is suppo ed by wo nonsmoo h noncon ex
p oblems go e ned by PDEs, including semilinea ellip ic and pa abolic equa-
ions. We also show ha ou esul s a e applicable o hese p oblems and epo
on ela ed nume ical expe imen s.
Ou line o he pape
The es o his pape is o ganized as ollows: Sec . 2p esen s he p elimina ies,
assump ions on he op imiza ion p oblem (P), he algo i hm, and he nonmono one
linesea ch s a egy. Sec ion 3in es iga es he con e gence and complexi y o he algo-
i hm comp ehensi ely unde di e en condi ions. Sec ion 4discusses he applicabili y
o he esul s om he p e ious sec ion o PDE-cons ained op imiza ion p oblems.
Finally, nume ical expe imen s a e epo ed in Sec . 5 ha jus i y ou heo e ical ind-
ings. To imp o e he eadabili y o he pape , we p o ide p oo o some esul s om
Sec . 3in Appendix A.
123

On he o wa d–backwa d me hod wi h nonmono one… 1267
No a ion
Th oughou his pape , he Hilbe space His endowed wi h he scala p oduc (·,·)H
and he induced no m ·H. Fo a adius >0 and ¯u∈H, we de ine B (¯u):= {u∈
H:u−¯uH< }. We also deno e wi h PS:H→H, he o hogonal p ojec ion on o
he se S⊂H. Fu he o e e y ˜
∈R, we de ine ≤˜
:= {u∈H:(u)≤˜
}.
By A gmin we deno e he se o minimize s o . Some imes we will use se - alued
(in-)equali ies, i.e. A≤B o A,B⊂H, meaning ha a≤b o all a∈Aand b∈B.
We call a sequence {uk}k⊂Hquasi-Féje mono one wi h espec o a non-emp y
se S⊂H, i o e e y ∈Si holds ha
uk+1− 2
H≤uk− 2
H+k,
whe e {k}k⊂R≥0is a summable sequence, i.e., ∞
k=0k<∞. To a oid con usion
in he no a ion, he de i a i e and g adien o Fa e de ined by F:H→Hand
∇F:H→H, espec i ely. In his case, o e e y u∈Hwe iden i y ∇F(u)∈
Hby he unique Riesz ep esen a i e o F(u)∈H, wi h Hdeno ing he dual
space o H. We also use he no ion o he con ex subdi e en ial o con ex unc ion
φ:H→R∪{+∞}a u∈dom φ:= {u∈H:φ(u)<+∞} de ined as
∂φ(u):= {w∈H:φ( ) −φ(u)≥(w, −u)H o all ∈H}.
2 P oblem o mula ion and algo i hm
In his sec ion, he p ecise heo e ical amewo k and he algo i hm will be in oduced.
Fi s , we s a e he p ecise assump ions on (P).
Assump ion 1 Fo p oblem (P),
A1:R:H→R∪{+∞}is p ope , con ex, and lowe semicon inuous.
A2:F:H→R∪{+∞}is con inuously F éche di e en iable on in (dom F)con-
aining dom R, ha is, dom R⊆in (dom F).
A3:∇F:in (dom F)→His globally LF-Lipschi z con inuous.
A4: The g adien ∇F:in (dom F)→His weak- o-s ong sequen ially con inuous.
Condi ions A1–A2 a e s anda d in o de o gua an ee he well-posedness o he algo-
i hm. A3 will be used o de i e complexi y esul s o i e a ions and we will discuss
he elaxa ion o his condi ion o a la ge class o p oblems go e ned by PDEs la e
in Sec . 3.4.WeuseA4 o show ha e e y weak sequen ial accumula ion poin o
i e a es belongs o S∗. No e ha , i dim(H)<∞,A4 ollows om A2.
Acco ding o Assump ion 1, he Fe ma p inciple [48, P oposi ion 9.1.5] o (P)
eads as ollows: I u∗∈His a local minimize o , hen
−∇F(u∗)∈∂R(u∗). (2)
123
1268 B. Azmi, M. Be n eu he
Fu he , wi h simila a gumen s as in he p oo o [26, Theo em 26.2], he condi ion
(2) can be equi alen ly exp essed as
u∗=P ox 1
αR(u∗−1
α∇F(u∗)) o some α>0,(3)
whe e he p oximal ope a o P ox 1
αR:H→His de ined by
P ox 1
αR(u):= a gmin
∈HR( ) +α
2 −u2
H.
This ope a o is well-de ined due o A1. We also de ine he se o c i ical poin s by
S∗:= {u∈H:−∇F(u)∈∂R(u)}.
Now we u n ou a en ion owa ds o malizing (1) and he p oposed s ep-size upda e
s a egy by a nonmono one linesea ch me hod. The e o e we in oduce he p ox-g ad
ope a o and he g adien mapping in he Hilbe space se ing analogously o, e.g., [5,
14].
De ini ion 1 Fo e e y α∈R>0, we de ine
1. he p ox-g ad ope a o Tα:in (dom F)→dom Rwi h u→ P ox 1
αR(u−
1
α∇F(u)).
2. he g adien mapping Gα:in (dom F)→Hwi h u→ α(u−Tα(u)).
Due o De ini ion 1and by some simple compu a ions, we ob ain o e e y u∈
in (dom F) ha
Gα(u)−∇F(u)∈∂R(Tα(u)). (4)
Fu he , i we de ine o e e y u∈in (dom F),w∈H, and α∈R>0
Qα(w, u):= F(u)+(∇F(u), w −u)H+α
2w−u2
H+R(w),
hen Tα(u)is he unique minimize o Qα(·,u), i.e.
Tα(u)=a gmin
w∈H
Qα(w, u).
As a consequence, we can w i e
(∇F(u), Tα(u)−u)H+1
2αGα(u)2
H+R(Tα(u)) ≤R(u). (5)
By means o he p ox-g ad ope a o and he g adien mapping, he i e a ions (1) can
be e o mula ed as ollows:
123
On he o wa d–backwa d me hod wi h nonmono one… 1269
uk+1=Tαk(uk) o k∈N0,(6)
uk+1=uk−1
αk
Gαk(uk) o k∈N0.(7)
In his case, o e e y u0∈in (dom F), he i e a ions a e well-de ined, ha is {uk}k⊂
dom R⊆H. Fu he , due o (7), we can see he analogy be ween he p oximal
g adien me hod and classical g adien descen o smoo h minimiza ion. Using (3)
and he no ion o he g adien mapping, we also can cha ac e ize he c i ical poin s o
(P), as ollows.
P oposi ion 1 Fo u ∗∈in (dom F), i holds ha Gα(u∗)=0 o some α∈R>0i
and only i u∗∈S∗.
The e o e Gα(¯u)=0 de ines a na u al e mina ion condi ion analogously o he smoo h
case.
The e a e many possible choices o he s ep-size αkin ou i e a i e scheme. In his
wo k, we will conside s ep-size upda es by a BB- ype upda e ule o a combina ion
o hem wi h a nonmono one linesea ch. To be mo e p ecise, as he ini ial ial s ep-
size wi hin he nonmono one linesea ch, we will choose one o he spec al g adien
BB- ypes s ep-sizes de ined by
αBB1a
k:= (uk−uk−1,∇F(uk)−∇F(uk−1))H
(uk−uk−1,uk−uk−1)H,
αBB2a
k:= (∇F(uk)−∇F(uk−1),∇F(uk)−∇F(uk−1))H
(uk−uk−1,∇F(uk)−∇F(uk−1))H,
αBB1b
k:= (uk−uk−1,Gαk−1(uk)−Gαk−1(uk−1))H
(uk−uk−1,uk−uk−1)H,
αBB2b
k:= (Gαk−1(uk)−Gαk−1(uk−1),Gαk−1(uk)−Gαk−1(uk−1))H
(uk−uk−1,Gαk−1(uk)−Gαk−1(uk−1))H
.
The i s wo s a egies co espond o he BB-me hod p esen ed e.g. in [40]. The las
wo no el BB-me hods modi y he classical BB-me hod and y o inco po a e ull
i s -o de in o ma ion by using he g adien mapping and no only he g adien o F.
Fu he mo e, we will use so-called al e na ing BB- ype upda e ules gi en by
αABBa := αBB1a o ke en and αBB2a o kodd,
αABBb := αBB1b o ke en and αBB2b o kodd.
Rema k 1 In he case o R=0, we ha e Gl(u)=∇F(u) o e e y l>0 and
u∈H. The e o e, many o he in oduced s ep-size upda es abo e a e iden ical, i.e.
αBB1b =αBB1a,αBB2b =αBB2a, and αABBb =αABBa.
Fo he nonmono one linesea ch upda e, we conside
(uk+1)≤max
0≤j≤m(k)(uk−j)−δ
αkGαk(uk)2
H,(8)
123
1270 B. Azmi, M. Be n eu he
whe e 0 <δ<1 and memo y m:N0→N0sa is ies
m(0)=0 and m(k)=min{m(k−1)+1,mmax} o k∈N,(9)
wi h a gi en uppe bound mmax ∈N0. Simila ly o [49], we also de ine he unc ions
:N0→N0and ν:N0→N0wi h
(k):= k−a g max
0≤j≤m(k)(uk−j) o k≥0 wi h k−m(k)≤(k)≤k,
ν(k):= (kmmax +k) o k≥0.
Thus, by hese no a ions, we ha e max
0≤j≤m(k)(uk−j)=(u(k))and (8) can be
ew i en as
(uk+1)≤(u(k))−δ
αkGαk(uk)2
H.(10)
Fu he we se
αk=αin ,kηik,(11)
whe e η>1. The ini ial s ep-size αin ,k>0 is chosen by he BB-me hod and a
lowe bound αin >0 is gi en o ensu e nonnega i i y. To limi he ini ial s ep-size
nume ically, also an uppe bound αsup >α
in is employed. In he upda e, we choose
he smalles in ege ik∈N0in (11), such ha (8) is sa is ied. This p ocedu e is
summa ized in Algo i hm 1.
Algo i hm 1 Nonmono one FBS
Inpu : 0<δ<1, mmax ∈N0,η>1, αsup >α
in >0, u0∈H,andα0>0.
Ou pu : A s a iona y poin u∗∈Ho (P).
1: Se k=0;
2: while Gαk(uk)H>0do
3: i k=0 hen
4: Se αin ,k:= max{αin ,min{αsup,α
0};
5: else
6: Compu e αBB
kacco ding o a BB-me hod and se
αin ,k:= max{αin ,min{αsup,αBB
k}};
7: end i
8: Se αk=αin ,kηik,whe eik≥0 is he smalles in ege o which (8) holds;
9: Se uk+1=uk−1
αkGαk(uk)and k=k+1;
10: end while
No e ha by P oposi ion 1, he c i e ion Gαk(uk)H≤ε ol wi h some ole ance
ε ol >0 is a easonable s opping c i e ion in he nume ical ealiza ion o Algo i hm 1.
123
On he o wa d–backwa d me hod wi h nonmono one… 1277
Thus, using L1, we can in e ha
kδ
α(mmax+1)min
0≤i≤k
mmax+1(mmax+1)−1Gαi(ui)2
H
≤k
mmax+1δ
αmin
1≤i≤k
mmax+1Gαν(i)−1(uν(i)−1)2
H
≤k
mmax+1

i=1
δ
αGαν(i)−1(uν(i)−1)2
H≤(u0)−(uk),
and his yields
min
0≤i≤k
mmax+1(mmax+1)−1Gαi(ui)H≤α(mmax+1)((u0)−(uk))
kδ.(27)
Fu he , using he second pa o Lemma 4and he ac ha k
mmax+1(mmax +1)−
1−k<mmax, we can deduce ha
min
0≤i≤kGαi(ui)H≤Cmmax
Gmin
0≤i≤k
mmax+1(mmax+1)−1Gαi(ui)H.(28)
Finally, (23) ollows om (27), (28), P2, and he ac ha αk≥αin o all k≥0.
(iii) We show ha e e y weak sequen ial accumula ion poin o {uk}k⊂His a
s a iona y poin o (P). In o he wo ds, we suppose ha ukiu∗ o a subsequence
{uki}i⊂{uk}kand u∗∈H. Then we show ha u∗∈S∗. Fo he sake o con enience,
we use he same no a ion o he subsequence as o he sequence i sel . To begin, due
o (22)in(i), P2, and he ac ha αk≥αin , we can conclude ha
lim
k→∞Gαin (uk)H=0 and lim
k→∞Tαin (uk)−ukH=0.(29)
Applying (4) o α=αin and u=uk, we ob ain o e e y k∈N0 ha
Gαin (uk)−∇F(uk)∈∂R(Tαin (uk)). (30)
Due o A4, we can in e ha uku∗implies ∇F(uk)→∇F(u∗)and, hus, using
(29)weha eGαin (uk)−∇F(uk)→−∇F(u∗)as k→∞.Due o(29), we also
can conclude ha Tαin (uk)u∗as k→∞. The e o e, sending k→∞in (30)
and using he ac ha he g aph o ∂Ris sequen ially closed [26, P oposi ion 16.26]
unde he weak opology o domain and he s ong opology o codomain, we ob ain
−∇F(u∗)∈∂R(u∗). This comple es he p oo . 
Rema k 2 In he case ha dim(H)<∞, he s a emen o (iii) in Theo em 6holds
ue o e e y (s ong) accumula ion poin o {uk}kwi hou equi ing A4.
123

1278 B. Azmi, M. Be n eu he
In he nex heo em, we de i e an es ima e ha e lec s he wo s -case complexi y
o he equi ed unc ion and g adien -like e alua ions o Algo i hm 1 o ind an ε ol-
s a iona y poin . The p oo is inspi ed by he one gi en in [50, Theo em 3.4] o smoo h
p oblems.
Theo em 7 (Wo s -case complexi y) Suppose ha A1–A3 hold and ha is bounded
om below wi h ¯
:= in u∈H(u)>−∞. Then o a gi en ole ance ε ol >0,
Algo i hm 1 equi es a mos
k
max := γ
comp((u0)−¯
)
ε2
ol (31)
unc ion e alua ions o and
kg
max := γg
comp((u0)−¯
)
ε2
ol (32)
G adien -like Gα(·)e alua ions o ind an i e a e uksa is ying Gαk(uk)H≤ε ol,
whe e
γ
comp := (mmax+1)C2mmax
G
γdec and γg
comp := (mmax+1)αC2mmax
G
δ,
wi h
γdec := min δ
αsup ,2(1−δ)δ
n1ηLFand n1:= logηηLF
2αin (1−δ).
P oo The p oo can be ound in Appendix A. 1.
This inishes ou conside a ions o con e gence and complexi y in he gene al
se ing.
3.2 Con ex case
In his sec ion, highe -o de con e gence a es will be shown in wo cases o addi-
ional s uc u al assump ions. Fi s ly, we conside he case whe e Fis also con ex.
A e wa ds, he case o a quad a ic g ow h assump ion on will be in es iga ed. We
assume he ollowing modi ied e sion o Assump ion 1.
Assump ion 2 Assume ha A1–A3 hold. Fu he , ins ead o A4, assume ha
A’4:F:H→Ris con ex.
Unde Assump ion 2, he whole unc ion is con ex. In his case, we can conclude
ha he se o minimize s o coincides wi h S∗p o ided ha S∗=∅and ha S∗is
closed and con ex. Fu he , we ha e
S∗=A gmin =(∂)−1(0).
123
On he o wa d–backwa d me hod wi h nonmono one… 1279
The associa ed minimal unc ion alue is deno ed by ∗∈R.
Nex we p o e an auxilia y lemma which will be used la e .
Lemma 8 Suppose ha Assump ion 2holds, S∗=∅, and {uk}kis gene a ed by Algo-
i hm 1. Then o e e y λ∈[0,1], i holds
(uν(k))−∗≤(1−λ) (uν(k−1))−∗+αλ2
2dis 2(uν(k)−1,S∗)
+˜
C
αν(k)−1Gαν(k)−1(uν(k)−1)2
H,
(33)
whe e ˜
C:= LF
2αin . Fu he , we ha e he ollowing inequali y o he ini ial i e a ions
(uν(1))−∗≤C0dis 2(u0,S∗), (34)
wi h cons an C0which is independen o u0.
P oo The p oo can be ound in Appendix A. 2.
Now we a e eady o p o ide he main con e gence esul o he con ex case. Fo
he sake o con enience in he p esen a ion, we se
Ek:= (uk)−∗ o e e y k≥0,
and use his no a ion in he emainde o his sec ion.
Theo em 9 (Global con e gence and O(k−1)complexi y o he con ex case) Sup-
pose ha Assump ion 2holds, S∗=∅, and {uk}kis gene a ed by Algo i hm 1. Then
he ollowing s a emen s hold ue:
(i) E e y weak sequen ial accumula ion poin o {uk}kbelongs o S∗.
(ii) {uk}kcon e ges weakly o a minimize u∗∈S∗and i s “shadow” sequence
con e ges s ongly o u∗, ha is PS∗uk→u∗.
(iii) I holds (uk)→∗as k →∞and o la ge enough k ≥0, he e exis
cons an s ρ1>0and ρ2>0such ha
(uk)−∗≤ρ1
ρ2+k.(35)
P oo (i) We suppose ha a subsequence {uki}iwi h ukiu∗is gi en. We will show
ha u∗∈S∗. To show his, we p o e ha he e exis s a anishing sequence o sub-
g adien s {wki}i⊂H, i.e. wki→0, co esponding o {uki}iwi h wki∈∂(uki) o
e e y i∈N.Using(4), we de ine
wk+1:= Gαk(uk)+∇F(uk+1)−∇F(uk)∈∂(uk+1). (36)
Fu he , since S∗=∅,is bounded om below. Hence, we can use (i) o Theo em 6
and (22) holds. This, oge he wi h (36) and he boundedness o αk, implies
wk+1H≤Gαk(uk)H+∇F(uk+1)−∇F(uk)H≤(1+LF
αk)Gαk(uk)H→0,
123
1280 B. Azmi, M. Be n eu he
as k→∞. In pa icula , we can in e ha wki→0asi→∞. Using he ac ha he
g aph o ∂ is sequen ially closed [26, P oposi ion 16.26] unde he weak opology
o domain and he s ong opology o codomain oge he wi h wki→0 and ukiu∗,
we a i e a 0 ∈∂(u∗)and he e o e u∗∈S∗.
(ii) We show ha uku∗wi h u∗∈S∗. In his ma e , we show ha {uk}kis a
quasi-Fejé sequence wi h espec o S∗=∅.Using(4), we can w i e o e e y k∈N0
ha
0∈αk(uk+1−uk)+∂R(uk+1)+∇F(uk). (37)
Fu he , since Ris con ex and ∇Fis Lipschi z con inuous, by he Haddad-Bailon
Theo em [26, Co olla y 18.16, p. 270], we ha e
(∇F( ) −∇F(w), −w)H≥LF−1∇F( ) −∇F(w)2
H.
Fu he , we can w i e o e e y , w, z∈in (dom F) ha
(∇F( ) −∇F(w), z−w)H
=(∇F( ) −∇F(w), −w)H+(∇F( ) −∇F(w), z− )H
≥LF−1∇F( ) −∇F(w)2
H−∇F( ) −∇F(w)Hz− H
≥−LF
4z− 2
H,
(38)
whe e in he las line we ha e used he ac ha (x):= LF−1x2−xz− His
s ic ly con ex and a ains i s global minimum a x∗=LF
2z− H.
Using (38) o uk+1,uk, and any u∗∈S∗in place o ,z, and w, espec i ely, we
ob ain
(∇F(uk)−∇F(u∗), uk+1−u∗)H≥−LF
4uk+1−uk2
H.
Toge he wi h he ac ha ∂Ris mono one, c . [26], and (2), we can w i e
(η +∇F(uk), uk+1−u∗)H≥−LF
4uk+1−uk2
H o all η∈∂R(uk+1). (39)
Using (37) and (39), we can deduce ha
(uk+1−uk,uk+1−u∗)H≤LF
4αkuk+1−uk2
H.(40)
Fu he , using (40) and he ac ha
(w − ,w −z)H=1
2w− 2
H−1
2 −z2
H+1
2w−z2
H o all z,w, ∈H,
123
On he o wa d–backwa d me hod wi h nonmono one… 1281
we can in e ha
1
2uk+1−u∗2
H−1
2uk−u∗2
H≤LF
4αk−1
2uk+1−uk2
H
≤LF
4α3
in Gαk(uk)2
H,
(41)
whe e i can be seen om (21) and (25) ha
∞

k=mmax+1Gαk(uk)2
H≤(mmax +1)C4mmax+2
G
∞

k=1Gαν(k)−1(uν(k)−1)H<∞.
The e o e, he sequence {uk}k⊂His quasi-Fejé mono one wi h espec o S∗and
since, due o (i), e e y weak sequen ial accumula ion poin o {uk}k⊂Hbelongs o
S∗=∅, we can conclude by [51, P oposi ion 1(3)] ha {uk}kis weakly con e gen
and i has a unique accumula ion poin .
In addi ion, since S∗is closed and con ex, we can conclude, due o [52, P oposi ion
3.6 (i )], ha {PS∗uk}kcon e ges s ongly o a poin ˆu∈S∗. Mo eo e , since u∗−
PS∗uk→u∗−ˆuand uk−PS∗uku∗−ˆu, i ollows om he de ini ion o o hogonal
p ojec ion ha u∗−ˆu2
H=limk→∞(u∗−PS∗uk,uk−PS∗uk)H≤0. Hence, we
ob ain ha u∗=ˆu.
(iii) The p oo o his pa is inspi ed by he one in [38, Theo em 3.2.]. Fi s , we
show ha (uk)→∗. Due o (ii), uku∗ o some u∗∈S∗. As in he p oo o (i),
he e exis s a sequence wk→0 wi h wk∈∂(uk). The e o e, we can w i e
(uk)≤∗+(wk,uk−u∗)H o e e y k∈N0.(42)
Sending k→∞in (42) and using he ac s ha uku∗and wk→0 and he weak
sequen ial lowe semicon inui y o , we can conclude ha
∗≤lim in
k→∞ (uk)≤lim sup
k→∞
(uk)≤∗.
Hence, (uk)→∗.
Nex , we u n o he e i ica ion o (35) o a la ge enough k.Due o(33)o
Lemma 8, o e e y λ∈[0,1], i holds
Eν(k)≤(1−λ)Eν(k−1)+αλ2
2dis 2(uν(k)−1,S∗)+˜
C
αν(k)−1Gαν(k)−1(uν(k)−1)2
H.
(43)
Since {uk}kis quasi-Féje mono one wi h espec o S∗=∅, due o [52, P oposi ion
3.6 (ii)], he sequence dis 2(uk,S∗)is con e gen . The e o e, o a posi i e cons an
κ>0, we ha e
dis 2(uν(k)−1,S∗)≤κ, o all k≥1.(44)
123
1282 B. Azmi, M. Be n eu he
Fu he , using (43), (44), and L2, we can w i e
Eν(k)≤(1−λ)Eν(k−1)+αλ2κ
2+˜
C
δEν(k−1)−Eν(k),(45)
whe e he exp ession on he igh -hand side is s ic ly con ex in λ, since
d2
dλ2(1−λ)Eν(k−1)+αλ2κ
2=ακ > 0.
The e o e, i possesses he unique minimize λ=Eν(k−1)
ακ . Since {Eν(k)}k→0, his
implies ha o la ge enough k, we can se λ=Eν(k−1)
ακ ≤1in(45) and ob ain ha
Eν(k)≤Eν(k−1)−E2
ν(k−1)
2ακ +˜
C
δEν(k−1)−Eν(k).
Toge he wi h he ac ha Eν(k)≤Eν(k−1), we can w i e
Eν(k)≤Eν(k−1)−Eν(k−1)Eν(k)
2ακ +˜
C
δEν(k−1)−Eν(k)
and, hus, ob ain
Eν(k)≤1+δ
2ακ( ˜
C+δ)Eν(k−1)−1Eν(k−1).(46)
Fu he , (46) can be exp essed as
1
Eν(k)≥1
Eν(k−1)+δ
2ακ( ˜
C+δ).
Applying his inequali y ecu si ely o in ege s k1and k2wi h k2≥k1and la ge
enough k1sa is ying Eν(k1)
ακ ≤1, we ob ain
1
Eν(k2)≥1
Eν(k1)+δ(k2−k1)
2ακ( ˜
C+δ),
and by easy compu a ions, also
Eν(k2)≤2ακ( ˜
C+δ)Eν(k1)
2ακ( ˜
C+δ)+Eν(k1)δ(k2−k1).
Thus, o k≥0 la ge enough, we se k2=k
mmax+1and ob ain
Ek≤Eν(k
mmax+1)≤2ακ( ˜
C+δ)Eν(k1)
2ακ( ˜
C+δ)+Eν(k1)δ(k
mmax+1−k1)
≤2ακ( ˜
C+δ)Eν(k1)
−k1Eν(k1)δ+2ακ( ˜
C+δ)+Eν(k1)δ( k
mmax+1)
.
123

On he o wa d–backwa d me hod wi h nonmono one… 1283
The e o e, (35) ollows by se ing
ρ1:= (mmax +1)δ−12ακ( ˜
C+δ)
and
ρ2:= (mmax +1)(δEν(k1))−12ακ( ˜
C+δ) −k1Eν(k1)δ.
Thus, he p oo is comple e. 
Compa ing Theo em 9 o Theo em 6, one ob ains weak con e gence o he whole
sequence and con e gence o he associa ed objec i e unc ion e alua ions wi h a e
1/k.
Rema k 3 No e ha o he case whe e dim(H)<∞, due o he equi alence o he
weak and s ong opologies, i ollows om (ii) o Theo em 9 ha ukcon e ges o u∗
in he s ong opology. Mo eo e , we will la e use he con e gence PS∗uk→u∗o
he shadow sequence o de i e he s ong con e gence uk→u∗unde he quad a ic
g ow h condi ions. This is ob iously no longe necessa y when dim(H)<∞.
3.3 Con e gence unde quad a ic g ow h- ype condi ions
In his sec ion, we u n ou a en ion owa ds quad a ic g ow h- ype condi ions and
s udy con e gence o Algo i hm 1unde hese condi ions.
De ini ion 2 (Quad a ic g ow h condi ion) We say ha sa is ies he quad a ic
g ow h condi ion,i
(u)−∗≥γ, dis 2(u,S∗) o all u∈∩dom (47)
holds wi h a se ⊂H, a cons an γ, >0, and S∗=∅. We e e o his no ion
as global i =H, and as local, i o u∗∈S∗, ∈(0,∞], and ω>0, we ha e
=B (u∗)∩[∗<+ω]. Addi ionally, is said o sa is y he s ong quad a ic
g ow h condi ion a u∗i S∗={u∗}on . Tha is,
(u)−(u∗)≥γ,u−u∗2
H o all u∈∩dom . (48)
The quad a ic g ow h condi ion is a geome ical assump ion which desc ibes he la -
ness o he objec i e unc ion a ound i s minimize s. Roughly speaking, his condi ion
is conside ed as a elaxa ion o he s ong con exi y condi ion and allows us o ob ain
as e a es o con e gence (linea ) and also con e gence in he s ong opology o he
i e a ion sequence. I is also closely ela ed o he no ion o Tikhono well-posedness
[53]. The ela ionship be ween he quad a ic g ow h condi ion and he so-called me -
ic sub egula i y o he subdi e en ial has been in es iga ed e.g. in [10,54–57]. The
s ong quad a ic g ow h condi ion (48)issaid obe hequad a ic unc ional g ow h
p ope y in [16] p o ided ha is con inuously di e en iable o e a closed con ex
123
1284 B. Azmi, M. Be n eu he
se . In [15,58], is also called 2-condi ional on i i sa is ies he quad a ic g ow h
condi ion (47). This p ope y was ecen ly p o ed in [10, Theo em 5] o be equi alen
wi h he case whe e sa is ies he Ku dyka-Łojasiewicz inequali y wi h o de 1/2.
Theo em 10 Suppose ha Assump ion 2and he quad a ic g ow h condi ion (47)hold
o := [<
∗+ω]wi h ω>0. Then, o he sequence o i e a es {uk}kgene a ed
by Algo i hm 1, he e exis s ¯
k∈Nsuch ha o e e y k ≥¯
k, we ha e
(uk)−∗≤Ccσk,(49)
and
dis 2(uk,S∗)≤Cdσk,(50)
whe e he cons an s Cc>0,C
d>0, and 0<σ<1a e independen o k.
Fu he , he e exis s u∗∈S∗such ha ukcon e ges in he s ong opology o u∗,
i.e. uk→u∗, and i holds
uk−u∗2
H≤Cpσk,(51)
wi h a cons an Cp>0which is independen o u∗and k.
P oo Fi s , due o L2 and (iii) om Theo em 9, he sequence {(uν(k))}kis mono on-
ically dec easing and con e ges o ∗. Fu he , using (20), we can deduce o k≥1
ha
(uν(k)−1)≤(u(ν(k)−1))≤(uν(k−1)). (52)
Thus, o gi en ω>0, he e exis s ¯
kω∈Nsuch ha
(uν(k)−1))∈[<
∗+ω] o all k≥¯
kω.
Nex , we show ha
Eν(k)≤θEν(k−1) o all k≥¯
kω,(53)
wi h a cons an θ∈(0,1)independen o k.
Le an a bi a y k≥¯
kωbe gi en. To show (53), we choose an a bi a y ζsa is ying
0<ζ<min{1
δ,1
2˜
C,γ,
2α˜
C}.
Now we conside he ollowing cases:
•The inequali y 1
αν(k)−1Gν(k)−1(uν(k)−1)2
H≥ζEν(k−1)holds. In his case,
using L2, we ob ain
Eν(k)≤Eν(k−1)−δ
αν(k)−1Gν(k)−1(uν(k)−1)2
H≤(1−ζδ)Eν(k−1),
123
On he o wa d–backwa d me hod wi h nonmono one… 1285
whe e due o he choice o ζwe ha e 1 −ζδ < 1.
•The inequali y
1
αν(k)−1Gν(k)−1(uν(k)−1)2
H<ζEν(k−1)(54)
holds. This case is mo e delica e. Using he quad a ic g ow h condi ion (47) and
(52), we ob ain o k≥¯
kω ha
dis 2(uν(k)−1,S∗)≤1
γ, Eν(k)−1≤1
γ, Eν(k−1).(55)
Now, using Lemma 8,(33), and (55), we can w i e o e e y λ∈[0,1] ha
Eν(k)≤˜
Cζ+1−λ+α
2γ, λ2Eν(k−1),(56)
whe e i can be easily seen ha he minimum o ˜
Cζ+1−λ+α
2γ, λ2a ained
a λ∗:= min{1,γ,
α}is s ic ly smalle han 1 and he e o e (53) holds o k≥¯
kω.
Le now k≥¯
k:= ¯
kω(mmax +1)be gi en. By successi ely applying (53), we
ob ain
Ek
L1
≤Eν(k
mmax+1)≤θ1−¯
kωθk
mmax+1Eν(¯
kω−1)
≤θ1−¯
kωθ
k
mmax+1Eν(¯
kω−1)≤θ1−¯
kωθ
1
mmax+1k
Eν(¯
kω−1).
(57)
Toge he wi h he quad a ic g ow h condi ion (47), we ha e
dis 2(uk,S∗)≤1
γ, Ek≤θ1−¯
kω
γ, θ
1
mmax+1k
Eν(¯
kω−1).(58)
Thus, o e e y k≥¯
k, he i e a es uks ay in .
Se ing Cc:= θ1−¯
kωEν(¯
kω−1),Cd:= γ−1
,θ1−¯
kωEν(¯
kω−1), and σ:= θ
1
mmax+1<1,
we a e inished wi h he e i ica ion o (49) and (50).
Nex , we show ha uk→u∗ o uku∗wi h u∗∈S∗gi en in Theo em 9(ii).
Due o (50), dis (uk,S∗)→0 and we can in e ha uk−PS∗uk→0. This oge he
wi h ac ha PS∗uk→u∗(see (ii)in Theo em 9) leads o uk→u∗.
Finally, we show ha (51) holds ue. To see his, le p∈Nbe a bi a y, using
Young’s inequali y we ha e
uk−uk+p2
H≤2uk−PS∗uk2
H+uk+p−PS∗uk2
H
=2dis 2(uk,S∗)+uk+p−PS∗uk2
H.
(59)
123
1286 B. Azmi, M. Be n eu he
Using (41), we ob ain o an a bi a y u∗∈S∗ ha
uk+p−u∗2
H≤uk−u∗2
H+LF
2α2
in
k+p−1

j=kGαj(uj)2
H.
In pa icula , we ha e o u∗=PS∗uk ha
uk+p−PS∗uk2
H≤dis 2(uk,S∗)+LF
2α2
in
k+p−1

j=kGαj(uj)2
H.(60)
Fu he , using L2 and (25), we can w i e o la ge enough k ha
k+p−1

j=kGαj(uj)2
H≤C4mmax+2
G
k+p−1

j=kGα
ν j
mmax+1−1
(u
ν j
mmax+1−1
)2
H
≤C4mmax+2
Gαδ−1
k+p−1

j=k
δ
α
ν j
mmax+1−1Gα
ν j
mmax+1−1
(u
ν j
mmax+1−1
)2
H
≤C4mmax+2
Gαδ−1⎛
⎝Eν k
mmax+1−1−E
ν k+p
mmax+1⎞
⎠.
(61)
Combining (59), (60), (61), and se ing ¯
Cp:= C4mmax+2
GαLF
δα2
in
,wea i ea
uk−uk+p2
H≤4dis
2(uk,S∗)+¯
Cp⎛
⎝Eν k
mmax+1−1−E
ν k+p
mmax+1⎞
⎠.
Sending p→∞and using Theo em 9(iii), (50), and simila compu a ions as in (57),
we ob ain o e e y k≥¯
k ha
uk−u∗2
H≤4dis
2(uk,S∗)+¯
CpEν k
mmax+1−1
≤4Cdσk+¯
Cpθ−1−¯
kωσkEν(¯
kω−1)=Cpσk.
Thus, (51) holds ue wi h Cp:= 4Cd+¯
Cpθ−1−¯
kωEν(¯
kω−1)and his comple es he
p oo . 
Co olla y 11 Suppose ha Assump ion 2holds and he quad a ic g ow h condi ion
(47)is sa is ied o := B (u∗)∩[<
∗+ω]wi h ,ω∈(0,∞). Fu he assume
ha , {uk}kgene a ed by Algo i hm 1, con e ges s ongly o some u∗∈S∗. Then he e
123
On he o wa d–backwa d me hod wi h nonmono one… 1293
o he p oximal ope a o is gi en by
P ox 1
αR(u)( ,x)=min{max{⎧
⎪
⎨
⎪
⎩
u( ,x)−C2,u( ,x)>C2,
u( ,x)+C2,u( ,x)<−C2,
0,o he wise,
,ua},ub},
whe e C2=λ/α.
4.3 Discussion on he quad a ic g ow h condi ion
In he emainde o he sec ion, we p esen a si ua ion in which Fis locally s ongly
con ex and, as a consequence, Algo i hm 1con e ges locally R-linea by Co olla y 13.
We conside he case ha o u∗∈S∗,Fis wice con inuously F éche di e en iable
and i s second de i a i e sa is ies
F(u∗)(h,h)≥Ch2
H o all h∈H,(76)
wi h some C>0. Fo he wo p e ious p oblems, we exp ess F(u∗)in e ms o
solu ions o PDEs and discuss when Fis locally s ongly con ex.
Fo bo h p oblems (PE) and (PP), he con ol- o-s a e ope a o u→ y(u) om H
o Wis wice con inuously F éche di e en iable, and by simila compu a ion as in
[63], i s second de i a i e can be exp essed as
y(u)(h,q)=−E−1
y(y(u), u)Eyy(y(u), u)(y(u)h,y(u)q) o all h,q∈H,(77)
since he con ol ope a o is linea .
To be able o use Co olla y 13 o p oblem (PE), we i s ede ine Fand Ras
ollows
F(u):= 1
2y(u)−yd2
L2() +σ
2u2
L2(),R(u):= λuL1() +δU(u).
In his case, wi h he same a gumen s gi en in Sec . 4.1,(PE) can be ew i en as (P)
o which H1–H4 hold. Fu he , using he chain ule and (77), we can w i e o e e y
h,q∈H ha
F(u)(h,q)=J(y(u))y(u)h,y(u)qW,W
+−E−∗
y(y(u), u)J(y(u)), Eyy(y(u), u)(y(u)h,y(u)q)Z,Z+σ(h,q)H,
whe e ·,·s ands o he dual pai ing and Jwas de ined in (72). Hence, F(u∗)wi h
u∗∈S∗can be exp essed as
F(u∗)(h,h)=yh2
L2() +%
p∗exp(y∗)(yh)2dx+σh2
H,(78)
123

1294 B. Azmi, M. Be n eu he
whe e y∗=y(u∗), p∗=p(u∗), and yh∈Wis he weak solu ion o he linea ized
s a e equa ion
$−κyh+exp(y∗)yh=hin ,
yh=0on∂.
No e ha , Fis locally s ongly con ex on a neighbo hood o u∗∈S∗p o ided ha
(76) holds o some C>0. Fu he , using (78), (76) can be equi alen ly ew i en as
σh2
L2() +yh2
L2() +%
p∗exp(y∗)(yh)2dx≥Ch2
L2() o all h∈H.
(79)
We obse e ha he only e m in (79) ha can spoil he posi i e de ini eness o F(u∗)
and, hence, local s ong con exi y o F, is he e m in ol ing p∗. This e m o igina es
om he nonlinea i y in he s a e equa ion. No e ha ei he a small enough adjoin
p∗o a la ge enough pa ame e σensu e ha (79) and equi alen ly (76) hold. A
small enough adjoin can occu , o ins ance, i y∗−yd2
L2() is su icien ly small.
Simila ly, o he second example (PP), we ob ain o Fand Rde ined in (74) ha
F(u∗)(h,h)=yh2
L2(0,T;L2()) +
T
%
0%

6p∗y∗(yh)2dxd ,(80)
whe e yh∈Wis he weak solu ion o he linea ized s a e equa ion
⎧
⎪
⎨
⎪
⎩
˙yh−κyh+3(y∗)2yh=hin (0,T)×,
yh=0on(0,T)×∂,
yh(T)=0in,
and p∗sol es he weak o mula ion o (75) o y∗. Fo his p oblem, due o he absence
o he e m σ
2·2
Hin he objec i e unc ion, he local s ong con exi y is no clea . Fo
he ellip ic p oblem (PE), he au ho s in [64] ha e s udied a weake condi ion which
implies ha he quad a ic g ow h condi ion (48) is sa is ied. Fu he mo e om [65,
Sec ion 3], i especially ollows ha o σ=0 condi ion (79) canno be sa is ied o
he ellip ic p oblem (PE).
5 Nume ical expe imen s
In his sec ion, we epo on he nume ical expe imen s o he p oblems (PE) and (PP)
in o de o e i y he capabili ies o Algo i hm 1nume ically. Th oughou , we use
Gαk(uk)H≤ε ol wi h some ole ance ε ol >0 as he e mina ion condi ion, as i is
p oposed in Sec . 2. Ou codes ha e been implemen ed in Py hon 3 and use FEniCS
123
On he o wa d–backwa d me hod wi h nonmono one… 1295
Table 1 Example 1: Pa ame e se ing
Op imiza ion p oblem Algo i hm 1
κσλyduaubε ol αin αsup α0ηδ mmax
(0,1)210−210−410−3See Fig. 1a−32 10
−610−410210 8 0.9 8
Fig. 1 Example 1: The desi ed s a e yd, he op imal s a e, and he op imal con ol (le o igh )
(see [66]) o he ma ix assembly. Spa se memo y managemen and compu a ions
ha e been implemen ed wi h SciPy (see [67]). All compu a ions below ha e been un
on an Ubun u 22.04 no ebook wi h 32 GB main memo y and an In el Co e i7-8565U
CPU.
We will also compa e di e en s ep-size app oaches o he i e a ions (1) wi h
espec o g adien -like e alua ions and unc ion e alua ions as in oduced in The-
o em 7. We conside a ixed s ep-size, di e en combina ion o BB- ype s ep-sizes
p esen ed in Sec . 2(wi hou linesea ch me hod), and BB- ype s ep-sizes inco po a ed
wi h he (non-)mono one linesea ch app oach.
No e ha o p oblems go e ned by nonlinea PDEs such as (PE) and (PP), any
g adien -like Gαe alua ion equi es sol ing a nonlinea s a e equa ion and a linea
adjoin equa ion and any unc ion e alua ion is in ol ed wi h sol ing a nonlinea
s a e equa ion. Fu he mo e, he numbe o g adien -like e alua ions co esponds o
he numbe o i e a ions ko Algo i hm 1.
Example 1 (Ellip ic p oblem) In his example, we conside p oblem (PE). Fo he
spa ial disc e iza ion, we ollow a disc e ize-be o e-op imize app oach and use P1-
ype ini e elemen s on a F ied ichs-Kelle iangula ion o he spa ial domain .To
e icien ly e alua e he nonlinea i y, we eso o mass lumping. Fo he nume ical
es s, we choose he pa ame e s summa ized in Table 1. No e ha o he ixed s ep-
size app oach, we se αk=α0in (1) o all k∈N0.
The desi ed s a e, he op imal s a e, and he op imal con ol a e illus a ed in Fig. 1.
We can see ha he bounds a e ac i e o he con ol, hough no s ong spa si y is
p omo ed, due o he choices o λand σ.
We compa e he di e en BB- ype s ep-sizes p esen ed in Sec . 2wi h he ixed s ep-
size app oach and wi h a (non-)mono one linesea ch app oach. The esul s ega ding
compu a ional ime, unc ion e alua ions, and g adien -like e alua ions a e ga he ed
123
1296 B. Azmi, M. Be n eu he
Fig. 2 Example 1: Con e gence o Algo i hm 1. “E o ” e e s o Gαk(uk)Ha he cu en i e a e
Fig. 3 Example 1: Example o
non-con e gence wi hou
linesea ch. “E o ” e e s o
Gαk(uk)Ha he cu en
i e a e
in Table 2. Fo he linesea ch me hods, he mos ola ile o he no el BB- ype s ep-size
upda es, i.e. BB1b, is used as he ini ial ial s ep-sizes wi hin Algo i hm 1.
As can be seen om Table 2, o his example, all o he app oaches ou pe o m
he one wi h ixed s ep-size by a huge ma gin o abou wo o de s o magni ude. The
al e na ing BB-me hods appea o be mo e e icien compa ed o he single BB-upda es
o bo h he old and no el s ep-sizes. Fu he mo e, excep in he case o BB1, he
no el s ep-sizes ou pe o m he old ones and, o e all, hey appea o be compe i i e.
All o hese conside a ions a e alid o bo h compu a ional ime and g adien -like
e alua ions. Func ion e alua ions a e only needed i a linesea ch me hod is used.
Compa ed o he BB1b me hod, he nonmono one linesea ch me hod needs abou 250
ewe g adien -like e alua ions, bu his comes a he cos o 887 addi ional unc ion
e alua ions o he linesea ch and his esul s in an inc eased o e all compu a ional
ime. Compa ed o he mono one (mmax =0) linesea ch, he nonmono one app oach
pe o ms signi ican ly be e . The con e gence beha io is also isualized in Fig. 2.
Figu e 3p esen s an example, whe e a BB- ype s ep-size upda e wi hou linesea ch
ails o con e ge. In his example, we s a he algo i hms wi h α0=1 ins ead o
α0=10. This con i ms he necessi y o inco po a ing a linesea ch s a egy o ensu e
con e gence.
Example 2 (Pa abolic p oblem) In his example, we conside (PP). He e, he spa ial
domain is disc e ized in he same manne as in Example 1. Fo he empo al disc e iza-
ion, we use he C ank Nicolson/Adams Bash o h scheme [68]. In his scheme, he
123
On he o wa d–backwa d me hod wi h nonmono one… 1297
Table 2 Example 1: Nume ical esul s o ixed s ep-size, di e en spec al g adien me hods as in oduced in Sec . 2, and a (non-)mono one linesea ch me hod wi h espec
o BB1b
Fixed BB1a BB2a ABBa BB1b BB2b ABBb nonmon. LS (BB1b) mon. LS (BB1b)
g ad.-like e al. 153,662 618 1046 571 941 608 383 697 991
un.e al.0000000887 1527
ime [s] 1.56 ·1031.01 ·1011.36 ·1011.55 ·1018.39 ·1007.92 ·1005.65 ·1002.21 ·1013.30 ·101
123
1298 B. Azmi, M. Be n eu he
Table 3 Example 2: Pa ame e se ing
Op imiza ion p oblem Algo i hm 1
Tκλyduaubε ol αin αsup α0ηδ mmax
(0,1)2110
−210−2See Fig. 4−100 100 10−610−410210 4 0.8 4
Fig. 4 Example 2: Snapsho s o he desi ed s a e yda ime ins ances 0,0.25,0.5and0.75
Fig. 5 Example 2: Snapsho s o he op imal s a e a ime ins ances 0,0.25,0.5and0.75
Fig. 6 Example 2: Snapsho s o he op imal con ol a ime ins ances 0,0.25,0.5and0.75
implici C ank Nicolson scheme is used excep o he nonlinea e ms which a e
ea ed using he explici Adams Bash o h scheme and mass lumping. Fo he nume -
ical es s, we choose he pa ame e s summa ized in Table 3. Fo he ixed s ep-size
app oach, we choose αk=α0 o k∈N0, simila ly o he p e ious example.
The desi ed s a e, he op imal s a e, and he op imal con ol a ime ins ances =
0,0.25,0.5,0.75 a e depic ed in Figs. 4,5, and 6, espec i ely. We can see spa si y in
space o he con ol. No e ha spa si y in ime can also be obse ed in he sense ha
he con ol s ays ze o on an in e al be ween ime ins ances =0.25 and =0.75.
Simila ly o Example 1, we compa e he di e en BB- ype s ep-sizes p esen ed
in Sec . 2wi h he ixed s ep-size app oach and wi h a (non-)mono one linesea ch
123

On he o wa d–backwa d me hod wi h nonmono one… 1299
Table 4 Example 2: Nume ical esul s o ixed s ep-size, di e en spec al g adien me hods as in oduced in Sec . 2, and a (non-)mono one linesea ch me hod wi h espec
o BB1b
Fixed BB1a BB2a ABBa BB1b BB2b ABBb nonmon. LS (BB1b) mon. LS (BB1b)
g ad.-like e al. 515,044 375 758 784 470 445 221 463 471
un.e al.0000000639 713
ime [s] 5.66 ·1044.28 ·1018.70 ·1018.89 ·1015.35 ·1015.08 ·1012.50 ·1018.65 ·1019.57 ·101
123
1300 B. Azmi, M. Be n eu he
Fig. 7 Example 2: con e gence o Algo i hm 1. “E o ” e e s o Gαk(uk)Ha he cu en i e a e
app oach, and he esul s ega ding compu a ional ime, unc ion e alua ions, and
g adien -like e alua ions a e p esen ed in Table 4. To e eal he e iciency o he
linesea ch s a egy, we inco po a e he leas e icien BB- ype s ep-size, namely BB1b,
wi h he linesea ch s a egy.
All conside a ions and obse a ions om Example 1hold also ue o his example.
Tha is, he i e a ions (1) o he choice o he BB- ype s ep-sizes signi ican ly ou pe -
o m hose wi h ixed s ep-size, as is o be expec ed. The no el al e na ing BB-me hod
ou pe o ms he o he app oaches. The nonmono one linesea ch me hod ou pe o ms
he mono one e sion. I also ou pe o ms he BB1b e sion conce ning g adien -like
e alua ions, bu he cos o addi ional 639 unc ion e alua ions again does no pay o
o o e all compu a ional ime. The con e gence beha io is also isualized in Fig. 7.
To summa ize, all he nume ical esul s om he abo e examples show he capa-
bili ies o Algo i hm 1and he necessi y o he use o a linesea ch me hod. F om he
abo e example, we can conclude ha he inco po a ion o nonmono one linesea ch
and BB s ep-sizes leads o an e icien algo i hm o a class o nonsmoo h noncon ex
PDE-cons ained op imiza ion p oblems. Mo eo e , he con e gence beha io is a
be e han wha ou wo s -case complexi y esul s sugges . In pa icula , when com-
bined wi h he BB me hods, his is ypical beha io , see e.g., [34,35,40]. Whe he
he s ong quad a ic g ow h condi ion helps o accele a e con e gence in he ellip ic
example (PE) owa ds he end is no en i ely clea , al hough he o ange cu es in
Figs. 2c and 3sugges i .
Conclusion
We ha e s udied he nonmono one FBS me hod o a class o nonsmoo h in ini e-
dimensional composi e p oblems in Hilbe spaces. S a ing wi h he gene al noncon-
ex se ing, we ha e es ablished global con e gence wi h complexi y (1/√k)and also
p o ided a wo s -case complexi y analysis. Unde addi ional con exi y assump ion,
con e gence has been imp o ed o he sublinea o o de (1/k)in unc ion alues. I
addi ionally, a quad a ic g ow h- ype condi ion is sa is ied, we ha e shown R-linea
con e gence, bo h in unc ion alues and i e a es. Addi ional di icul ies a ising in he
ansi ion om weak o s ong con e gence in he in ini e-dimensional se ing ha e
been discussed in de ail. Finally, he nonmono one FBS and he no el BB s ep-size
123
On he o wa d–backwa d me hod wi h nonmono one… 1301
ules exploi ing he nonsmoo h pa we e success ully es ed o ellip ic and pa abolic
PDE-cons ained p oblems.
Appendix A P oo s
A. 1 P oo o Theo em 7
He e, we es ic ou sel es mainly o de i ing (31). Jus i ica ion o (32) ollows by
simila a gumen s. The p oo is ca ied ou by de e mining he minimum educ ion o
he objec i e unc ion be ween i e a ion s ep uk+1and i s maximal p edecesso , i.e.
u(k), wi h espec o (11) as long as Algo i hm 1has no been e mina ed. No e ha
u(k)can be calcula ed wi hou u he e alua ions o he objec i e unc ion by s o ing
p e ious i e a es. When using Algo i hm 1, we ha e he ollowing wo cases:
•Assume ha (8) in S ep 4 o Algo i hm 1holds o αk:= αin ,kand he e o e
ik=0. Then we ha e a dec ease
(u(k))−(uk+1)≥δ
αin ,kGαk(uk)2
H≥δ
αsup Gαk(uk)2
H.
In his case, only one addi ional unc ion e alua ion is necessa y o ob ain his
dec ease.
•Assume ha (8) in S ep 4 o Algo i hm 1 ails o hold o αin ,kand he e o e
ik≥1 back acking s eps a e pe o med. Due o (iii) o Lemma 4we ha e αk=
αin ,kηik<ηLF
2(1−δ), and, as a consequence, we can bound ikas ollows ik<
logηηLF
2αin ,k(1−δ).Hence, S ep 4 equi es a mos n1:= logηηLF
2αin (1−δ)
unc ion e alua ions. A he ime ha he linesea ch s a egy e mina es in his s ep,
we ha e he dec ease
(u(k))−(uk+1)≥δ
αkGαk(uk)2
H>2(1−δ)δ
ηLFGαk(uk)2
H.
Ga he ing he wo abo e cases, we can see ha unc ion alue dec ease pe unc ion
e alua ion is gi en, in he wo s case, by
(u(k))−(uk+1)≥γdec Gαk(uk)2
H,
123
1302 B. Azmi, M. Be n eu he
wi h γdec := min δ
αsup ,2(1−δ)δ
n1ηLF. Fu he , using simila a gumen s as in he p oo o
Theo em 6, we ob ain
(u0)−¯
≥(u0)−(uk)≥(uν(0))−(uν(k
mmax+1))
=k
mmax+1

i=1
(uν(i−1))−(uν(i))≥k
mmax+1

i=1
γdec Gαν(i)−1(uν(i)−1))2
H
≥γdec k
mmax+1min
1≤i≤k
mmax+1Gαν(i)−1(uν(i)−1)2
H
≥γdec k
mmax+1min
0≤i≤k
mmax+1(mmax+1)−1Gαi(ui)2
H
≥γdec k
C2mmax
G(mmax+1)min
0≤i≤kGαi(ui)2
H.
(A1)
To ind an ε ol-s a iona y poin , we assume ha up o he cu en i e a ion kAlgo i hm 1
has no been e mina ed, i.e. Gαi(ui)H> o all i=0,...,k. In his case, using
(A1), we can w i e (u0)−¯
>γdec k
C2mmax
G(mmax+1)ε2
ol, and, he e o e, he o al
numbe o unc ion e alua ions o in Algo i hm 1is bounded om abo e by
k
max ≤C2mmax
G(mmax+1)((u0)−¯
)
γdec ε2
ol =γ
comp((u0)−¯
)
ε2
ol .
Thus, we a e inished wi h he e i ica ion o (31). Simila ly, using (23), i can be
easily shown ha he o al numbe o Gαk(uk)e alua ions is bounded by
kg
max ≤C2mmax
Gα(mmax+1)((u0)−¯
)
δε2
ol =γg
comp((u0)−¯
)
ε2
ol ,
and, hus, he p oo is comple e.
A. 2 P oo o Lemma 8
Fi s , we show o e e y k≥1 ha
(uk)≤min
w∈H
Qαk−1(w, uk−1)+LF
2αin αk−1Gαk−1(uk−1)2
H.(A2)
Due o A3, he descen lemma, see [59, Lemma 1.30], implies
F(uk)≤F(uk−1)+(∇F(uk), uk−uk−1)H+LF
2α2
k−1Gαk−1(uk−1)2
H.
123