PPA-basedmethodsformonotoneinversevariationalinequalities
Bing-ShengHea,1
ab
HenryX.Liub,2MinLiaXiao-ZhengHeb
DepartmentofMathematics,NanjingUniversity,Nanjing,210093,China.
DepartmentofCivilEngineering,UniversityofMinnesota,Minneapolis,55455,USA.
Abstract.Weconsideraclassofinversevariationalinequalities:Findavectoru∗,suchthat
F(u∗)∈Ω,
T
v−F(u∗)u∗≥0,
∀v∈Ω.
Unliketheregularvariationalinequalities,themappingF(u),insteadofthevariableu,isrestrictedinaclosedconvexsetΩ.InversevariationalinequalitiesarisefromvarioussystemcontrolproblemswhereuisacontrolvariableandF(u)istherelevantsystemstatus.Insomeapplications,themap-pingF(u)ismonotone.Forsolvingmonotoneinversevariationalinequalities,thispaperpresentstheproximalpointalgorithm(PPA)anditsinexactversions.Finally,wepresentaPPA-basedself-adaptivemethodthatonlyneedsthefunctionvalueF(u)forgivenvariables.
KeyWords.Inversevariationalinequality,monotonemapping,proximalpointalgorithm.
1Introduction
LetΩbeaclosedconvexsetofRnandfbeamappingfromRnintoitself.Theclassicalvariationalinequality,abbreviatedbyVI(Ω,f),istodetermineavectorxinΩsuchthat
(x−x)Tf(x)≥0,
∀x∈Ω.
(1.1)
Inthispaper,however,weconsideraclassofinversevariationalinequalities:Findu∈Rn,suchthat
F(u)∈Ω,
T
v−F(u)u≥0,
∀v∈Ω,
(1.2)
whereF(u):Rn→RnisafunctionandΩ⊂Rnisaclosedconvexset.WedenoteProblem(1.2)byIVI(Ω,F).Itisclearthat,bysettingu=f(x)andF(u)=f−1(u),IVI(Ω,F)canbetranslatedintotheclassicalvariationalinequalityVI(Ω,f).However,insomepracticalapplications,f(x)doesnotallowmeasurements,onlyF(u)isavailable.
Inversevariationalinequalities,similarwithclassicalVI(Ω,f)[5,6,7],haveawiderangeap-plicationsindifferentfields.TheprimarymotivationofourresearchonIVI(Ω,F)arisesfromthetransportationsystemoperationandcontrolpolicies.Considerasimplenetworkwhichincludesoneorigination-destinationpairconnectedbyafewroutes.Letubetheimposedroutecost(tollchargesorsubsidies)andF(u)betherelevantrouteflows.Inordertoavoidtrafficcongestionandrationally
12
ThisauthorwassupportedbyNSFCGrant10571083.Email:hebma@nju.edu.cnEmail:henryliu@umn.edu
1
http://www.paper.edu.cn
usetheroadservices,theadministrationshouldfindacontrolcostusuchthattherelevantrouteflowsF(u)stayinarange,sayΩ.TheequilibriumcanbeinterpretedasanIVI(Ω,F).
Similarapplicationsofinversevariationalinequalitiescanalsobefoundintheelectricalpowernetworkmanagement.Therearepeakandvalleyperiodsintheusageofelectricitypower.Theelectricitynetworkisendangeredifoverloadedwhenthepeakperiodsofelectricityconsumptionoccur.Ontheotherhand,whentheelectricityconsumptionreachesvalleytime,electricitycouldbewastedduetothedifficultyofstoringunusedpower.Toensurethesafetyofelectricitynetworkandtoencourageoff-peakusage,theelectricitypowercompanycouldchargedifferentunitpricesforpeaktimeusageandvalleytimeusage.Suchapricingschemecouldleadtoagoodcontrolofpowerusagewithinthereasonablerange.TheequilibriumofthiscontrolproblemisalsoanIVI(Ω,F)ofform(1.2).Assumingthattheusersbehaverationallyaccordingtotheeconomicprinciple,themappingsofIVI(Ω,F)inabovementionedexampleshavesomenon-increasingproperties.
IVI(Ω,F)belongstothegeneralvariationalinequalityGVI(Ω,F,Q)[10]:Findu∈Rn,suchthat
F(u)∈Ω,
(v−F(u))TQ(u)≥0,
∀v∈Ω.
TheexistenceresultsongeneralvariationalinequalitieshavebeeninvestigatedbyPangandYao[12].SinceIVI(Ω,F)isaspecialGVI(Ω,F,Q),itmotivatesustoexploititsstructuralpropertyandtodevelopaclassofproximal-typemethodsforsolvingIVI(Ω,F).ThroughoutthispaperweassumethatthemappingFismonotone,thesolutionsetofIVI,denotedbyS∗,isnonemptyandtheprojectiononΩissimpletocarryout.TheEuclideannormwillbedenotedby·.
2Preliminaries
Thissectionstatessomepreliminariesthatareusefulintheconvergenceanalysisofthispaper.First,theprojectionofavectorvontoaclosedconvexsetΩ,definedas
PΩ(v)=argmin{u−v|u∈Ω},
playsanimportantroleinouranalysis.Awellknownpropertyoftheprojectionmappingis
T
v−PΩ(v)u−PΩ(v)≤0,
∀v∈Rn,u∈Ω.
(2.1)
Letβ>0,sincetheearlyworkofEaves[3],ithasbeenknownthatthevariationalinequalityproblemVI(Ω,f)isequivalenttoaprojectionequation
x=PΩ[x−βf(x)],
wherePΩ(·)denotestheorthogonalprojectionmappingontoΩ.Inotherwords,solvingVI(Ω,f)isequivalenttofindingazeropointoftheresiduefunction
e(x,β):=x−PΩ[x−βf(x)].
Similarly,theinversevariationalinequality(1.2)isequivalenttothefollowingprojectionequation
F(u)=PΩ[F(u)−βu].
2
(2.2)
http://www.paper.edu.cn
Let
r(u,β):=(1/β){F(u)−PΩ[F(u)−βu]}
denotethescaledresidueoftheprojectionequation.Thenwehave
u∈S∗⇐⇒r(u,β)=0.
Thistellsusthatsolvingtheinversevariationalinequalityisequivalenttofindingazeropointofr(u,β).Forgivenu∈Rn,themagnituder(u,β)isdependentonβ.Thefollowingpropertiesofr(u,β)areneededinconvergenceanalysis.Forself-completeness,asimilarproofasin[15]isprovided.
˜≥β>0,wehaveLemma2.1Foranyu∈Rnandβ
˜(u,β˜)≥βr(u,β)βrand
˜)≤r(u,β).r(u,β
(2.5)(2.4)(2.3)
˜)/r(u,β),weneedonlytoproveβ/β˜≤t≤1.NotethatitsequivalentProof.Lett=r(u,β
expressionis
˜)(t−1)≤0.(t−β/βInthefollowingweuse
(v−PΩ(v))T(PΩ(v)−w)≥0,
∀v∈Rn,w∈Ω.
(2.7)(2.6)
˜]andv:=F(u)−βuandusingBysettingw:=PΩ[F(u)−βu
˜]=βr˜(u,β˜)−βr(u,β),PΩ[F(u)−βu]−PΩ[F(u)−βuweobtain
˜(u,β˜)−βr(u,β)}≥0.{r(u,β)−u}T{βrSimilarly,wecanget
˜)−u}T{βr(u,β)−βr˜(u,β˜)}≥0.{r(u,β
Adding(2.8)and(2.9),weget
˜)}T{βr˜(u,β˜)−βr(u,β)}≥0.{r(u,β)−r(u,βandtherefore
˜r(x,β˜)2≤(β+β˜)r(u,β)Tr(u,β˜).βr(u,β)2+β
3
(2.11)(2.10)(2.9)(2.8)
http://www.paper.edu.cn
Dividing(2.11)byr(u,β)2,weget
˜2≤(β+β˜)t.β+βt
andconsequently(2.6)ishold.Theassertionisproved.
Foru∗∈S∗andastartingpointu0,wedenoteS0(u∗):={u∈Rn|u−u∗≤u0−u∗}andgivethefollowingdefinitionsaboutF.
Definition2.1ThefunctionFissaidtobeLipschitzcontinuousonRnifthereisaconstantL>0
suchthat
F(u)−F(v)≤Lu−v,
∀u,v∈Rn.
Definition2.2ThefunctionFissaidtobemonotoneonRnif
(u−v)T(F(u)−F(v))≥0
∀u,v∈Rn;
FissaidtobeuniformlystronglymonotoneonRnif
(u−v)T(F(u)−F(v))≥τu−v2
∀u,v∈Rn.
Somepropertiesoftheprojectionmappingareusefulintheconvergenceanalysisoftheproposedmethodsinthispaper,welisttheminthefollowinglemma.Lemma2.2LetΩbeaclosedconvexsetinRn,thenwehave
PΩ(v)−u2≤v−u2−v−PΩ(v)2,and
[v−PΩ(v)]−[w−PΩ(w)]2≤v−w2−PΩ(v)−PΩ(w)2,Proof.Usingawell-knowninequalityoftheprojectionmapping,
Tv−PΩ(v)u−PΩ(v)≤0,∀v∈Rn,u∈Ω,wegetAssertion(2.12)immediately.Inaddition,itfollowsthatT
v−w)PΩ(v)−PΩ(w)≥PΩ(v)−PΩ(w)2,∀v,w∈Rn.Usingtheaboveinequality,weobtain
[v−PΩ(v)]−[w−PΩ(w)]2
=v−w2−2v−w)TPΩ(v)−PΩ(w)+PΩ(v)−PΩ(w)2≤v−w2−PΩ(v)−PΩ(w)2
andthesecondassertionofthislemmaisproved.
Aconsequentresultof(2.13)is
[v−PΩ(v)]−[w−PΩ(w)]≤v−w,
∀v,w∈Rn,
(2.14)
∀v,w∈Rn.
(2.13)
∀v∈Rn,u∈Ω,
(2.12)
whichwillbeoftenusedinthefollowinganalysisofthispaper.
4
http://www.paper.edu.cn
3TheproximalpointalgorithmforIVI(Ω,F)
Proximalpointalgorithm(PPA)[11,13]isanattractivemethodforsolvingmonotoneVI(Ω,f).Forgivenxk∈Ωandβk>0,PPAtakesthesolutionofsubproblem
x∈Ω,
(x−x)Tfk(x)≥0,
∀x∈Ω
asthenewiteratexk+1,where
fk(x)=(x−xk)+βkf(x).
Inotherwords,PPAsolvestheoriginalVI(Ω,f)viasolvingaseriesofsubproblemVI(Ω,fk).Itiswellknownthatthesequence{xk}generatedbyPPAforVI(Ω,f)satisfy
xk+1−x∗2≤xk−x∗2−xk−xk+12
and
xk+1−x∗2≤xk−x∗2−e(xk+1,βk)2.
RecentdevelopmentsandinvestigationsofPPAforvariationalinequalitiescanbefoundin[1,2,14].ForIVI(Ω,F),wepresenttheproximalpointalgorithmwithagivenboundedsequence{βk}andprovethesamepropertiesasPPAforVI(Ω,f).
Method1.TheProximalPointAlgorithmforIVI(Ω,F).
Givenu0∈Rn.Fork=0,1,...,ifuk∈S∗thentakethesolutionofthefollowingproblem
Fk(u)∈Ω,
(v−Fk(u))Tu≥0,
∀v∈Ω,
(3.1)
asthenewiterateuk+1,where
Fk(u)=F(u)+βk(u−uk).
(3.2)
Remark.Astherelationshipof(1.2)and(2.2),thenewiterategeneratedby(3.1)-(3.2)satisfies
Fk(uk+1)=PΩ[Fk(uk+1)−βkuk+1].andthus
uk+1=uk−(1/βk)F(uk+1)−PΩ[F(uk+1)−βkuk].
(3.4)(3.3)
SinceF(u)ismonotone,Fk(u)isuniformlystronglymonotone.Therefore,eachiterationofthePPAforIVI(Ω,F)istosolveauniformlystronglymonotoneinversevariationalinequalityIVI(Ω,Fk).Innumericalviewpoint,IVI(Ω,Fk)iswellconditionedincomparisonwithIVI(Ω,F).Theorem3.1Thesequence{uk}generatedbyMethod1forIVI(Ω,F)satisfies
uk+1−u∗2≤uk−u∗2−uk−uk+12.
5
(3.5)
http://www.paper.edu.cn
Proof.Notethat(see(3.4))
βkuk+1=PΩ[F(uk+1)−βkuk]−[F(uk+1)−βkuk]andforanysolutionpointu∗(dueto(2.2))
βku∗=PΩ[F(u∗)−βku∗]−[F(u∗)−βku∗].Hencewehave
βk(uk+1−u∗)2
={[F(uk+1)−βkuk]−PΩ[F(uk+1)−βkuk]}−{[F(u∗)−βku∗]−PΩ[F(u∗)−βku∗]}2.
Bysettingv=F(uk+1)−βkukandw=F(u∗)−βku∗andusing(2.13),weobtain
βk(uk+1−u∗)2
≤(F(uk+1)−F(u∗))−βk(uk−u∗)2−PΩ[F(uk+1)−βkuk]−PΩ[F(u∗)−βku∗]2.
SubstitutingPΩ[F(uk+1)−βkuk]=F(uk+1)+βk(uk+1−uk)(see(3.3))andPΩ[F(u∗)−βku∗]=F(u∗)inthesecondtermoftherighthandsideoftheaboveinequality,weget
βk(uk+1−u∗)2
≤(F(uk+1)−F(u∗))−βk(uk−u∗)2−(F(uk+1)−F(u∗))+βk(uk+1−uk)2=βk(uk−u∗)2−βk(uk+1−uk)2−2βk(uk+1−u∗)T(F(uk+1)−F(u∗))≤βk(uk−u∗)2−βk(uk+1−uk)2.
ThelastinequalityisduetothemonotonicityofFandtheassertionisproved.Theorem3.2Thesequence{uk}generatedbyMethod1forIVI(Ω,F)satisfies
uk+1−u∗2≤uk−u∗2−r(uk+1,βk)2.Proof.Using(3.5)weneedonlytoprove
r(uk+1,βk)≤uk−uk+1.
Itfollowsfromthedefinitionofr(uk+1,βk)and(3.3)that
βkr(uk+1,βk)=F(uk+1)−PΩ[F(uk+1)−βkuk+1]
=PΩ[F(uk+1)−βkuk]+βk(uk−uk+1)−PΩ[F(uk+1)−βkuk+1].
Bysetting
v=F(uk+1)−βkuk+1
andw=F(uk+1)−βkuk,
(3.8)(3.7)(3.6)
therighthandsideof(3.8)canbewrittenas
[v−PΩ(v)]−[w−PΩ(w)]
6
http://www.paper.edu.cn
anddueto(2.14)
βkr(uk+1,βk)≤v−w=βk(uk−uk+1).Theproofiscomplete.
(3.9)
Inequality(3.6)tellsusthatthesequence{uk}generatedbyPPAiscontainedinS0(u∗)foranyu∗∈S∗.Sinceuk+1isclosertothesolutionsetthanuk,wesayPPAisacontractionmethod.Basedon(3.6),wecanestablishtheconvergenceofthePPAforIVI(Ω,F).However,thesubproblemitselfisstillaninversevariationalinequality.Thetaskofsolvingthesubproblemsisratherexpensive.ThecostlycomputationalloadofexactPPAmotivatesustoconsiderinexactversionsofPPA[1,4,10].Intherestofthissection,wediscusshowtoproduceaninexactsolutionofthesubIVI(Ω,Fk)withsomerelativeinexactnesscriteria.
Inexactprocedure.ProducinganapproximatesolutionofIVI(Ω,Fk).Forgivenβk>0andδk>0,theapproximatesolutionu˜ksatisfies
F(˜uk)−ξk+βk(˜uk−uk)=PΩ[F(˜uk)−ξk−βkuk],where
ξk≤δkβk(uk−u˜k).
(3.11)(3.10)
Remark.Forfixedβk>0,subIVI(Ω,Fk)(3.1)-(3.2)isauniformlystronglymonotoneinversevariationalinequality(withmodulusβk)whichhasauniquesolution,sayu∗k.Itsatisfies
∗∗
Fk(u∗k)=PΩ[Fk(uk)−βkuk].
kk∗TheexactPPAtakesuk+1=u∗kasthenewiterate.Notethatuk=u,otherwiseuisasolutionofIVI(Ω,F).Inprinciple,wecanuseaGoldstein’stypeprojectionmethod(e.g.,[9])togetanapproximatesolutionofauniformlystronglymonotoneinversevariationalinequality.Letu¯k≈u∗kbeanapproximatesolutionof(3.1)-(3.2)andthus
Fk(¯uk)≈PΩ[Fk(¯uk)−βku¯k].Notethat(3.12)canbewrittenas
F(¯uk)+βk(¯uk−uk)≈PΩ[F(¯uk)−βkuk].Forthisu¯k,bysetting
u˜k=uk−(1/βk){F(¯uk)−PΩ[F(¯uk)−βkuk]},wehave
F(¯uk)+βk(˜uk−uk)=PΩ[F(¯uk)−βkuk]
7
(3.12)
(3.13)
(3.14)
(3.15)
http://www.paper.edu.cn
andthusu˜k(≈u¯k)isalsoanapproximatesolutionofPPAsubproblem(3.1)-(3.2).Let
ξk=F(˜uk)−F(¯uk),
(3.16)
kk˜k≈u¯k≈u∗Equation(3.15)canbewritteninform(3.10)andu˜k=u∗k=u,forkifξ=0.Sinceu
anygivenδk>0,wecanaskξktobesmallsuchthatCondition(3.11)tobesatisfied.TheinexactPPAinthefollowingsectionsarebasedonu˜kandξkproducedbytheInexactProcedure.ThefollowingresultwillbeusedintheconvergenceanalysisofdifferentPPA-basedinexactmethods.
Theorem3.3Ifuk,u˜kandξksatisfyEquation(3.10)-(3.11),thenwehave
r(˜uk,βk)≤(1+δk)uk−u˜k.
Proof.Itfollowsfromthedefinitionofr(˜uk,βk)and(3.10)that
βkr(˜uk,βk)=F(˜uk)−PΩ[F(˜uk)−βku˜k]
=PΩ[F(˜uk)−ξk−βkuk]+βk(uk−u˜k)+ξk−PΩ[F(˜uk)−βku˜k].
Notethattherighthandsideof(3.18)canbewrittenas
[v−PΩ(v)]−[w−PΩ(w)],with
v=F(˜uk)−βku˜k
andw=F(˜uk)−ξk−βkuk.
(3.18)(3.17)
Byusing(2.14)weobtain
PΩ[F(˜uk)−ξk−βkuk]+βk(uk−u˜k)+ξk−PΩ[F(˜uk)−βku˜k]≤v−w
=βk(uk−u˜k)+ξk.
Assertion(3.17)followsfrom(3.18),(3.19)and(3.11)immediately.
(3.19)
4AninexactPPAforIVI(Ω,F)
Theinexactproximalpointalgorithminthissectiontakessuchu˜kin(3.10)asthenewiterate.Wedescribetheprocedureasfollows.
Method2.AninexactProximalPointAlgorithmforIVI(Ω,F).
Givenu0∈Rn.Fork=0,1,...,ifuk∈S∗thentakeu˜kin(3.10)asthenewiterateuk+1.Initsinexactnesscriterion(3.11),
δk=νηk
whichsatisfies
ν∈(0,1)
and
∞k=0
2
ηk<+∞.
(4.1)
8
http://www.paper.edu.cn
Themainpropertiesofthesequence{uk}generatedbytheinexactPPAinthissectionwillbedescribedinthefollowingtheorems.
Theorem4.1Let{uk}bethesequencegeneratedbyMethod2(aninexactPPA)forIVI(Ω,F).Thenwehave
22
uk+1−u∗2≤(1+2ηk)uk−u∗2−(1−ν2−2ηk)uk−uk+12.
(4.2)
Proof.Sinceuk+1=u˜k,itfollowsfrom(3.10)that
βkuk+1=PΩ[F(uk+1)−ξk−βkuk]−[F(uk+1)−ξk−βkuk].Sinceu∗isasolutionpoint,dueto(2.2),wehave
−βku∗=[F(u∗)−βku∗]−PΩ[F(u∗)−βku∗].Addingtheabovetwoinequalities,weobtain
βk(uk+1−u∗)={PΩ[F(uk+1)−ξk−βkuk]−[F(uk+1)−ξk−βkuk]}
−{PΩ[F(u∗)−βku∗]−[F(u∗)−βku∗]}.
(4.4)(4.3)
SimilarlyasintheproofofTheorem3.1,applyingLemma2.2totherighthandsideof(4.4),weget
βk(uk+1−u∗)2
≤(F(uk+1)−F(u∗))−ξk−βk(uk−u∗)2
−PΩ[F(uk+1)−ξk−βkuk]−PΩ[F(u∗)−βku∗]2.
SubstitutingPΩ[F(uk+1)−ξk−βkuk]=F(uk+1)−ξk−βk(uk−uk+1)(see(4.3))andPΩ[F(u∗)−βku∗]=F(u∗)inthesecondtermoftherighthandsideoftheaboveinequality,weget
βk(uk+1−u∗)2
≤(F(uk+1)−F(u∗))−ξk−βk(uk−u∗)2−(F(uk+1)−F(u∗))−ξk−βk(uk−uk+1)2=βk(uk−u∗)+ξk2−βk(uk−uk+1)+ξk2−2βk(uk+1−u∗)T(F(uk+1)−F(u∗))≤βk(uk−u∗)+ξk2−βk(uk−uk+1)+ξk2.
(4.5)
Thelastinequalityof(4.5)isduetothemonotonicityofF.ByusingCauchy-Schwarzinequalitywehave
12
βk(uk−u∗)+ξk2≤(1+2ηk)βk(uk−u∗)2+1+2ξk2
2ηkand
12
βk(uk−uk+1)+ξk2≥(1−2ηk)βk(uk−uk+1)2+1−2ξk2.
2ηk
Substitutingthemin(4.5)andusingtheinexactnesscriterion(4.1),weobtain
222
βk(uk+1−u∗)2≤(1+2ηk)βk(uk−u∗)2−(1−2ηk)βk(uk−uk+1)2+(1/ηk)ξk2
22
≤(1+2ηk)βk(uk−u∗)2−(1−ν2−2ηk)βk(uk−uk+1)2
(4.6)
andtheproofiscomplete.
9
http://www.paper.edu.cn
Theorem4.2Let{uk}bethesequencegeneratedbyMethod2(aninexactPPA)forIVI(Ω,F).Thenwehave
u
k+1
−u≤(1+
∗2
22ηk)uk
2)(1−ν2−2ηk
−u−r(uk+1,βk)2.2(1+νηk)
∗2
(4.7)
Proof.Accordingto(4.2)weneedonlytoprove
r(uk+1,βk)≤(1+νηk)uk−uk+1.
Sincewedirectlytakeu˜kasthenewiterate,i.e.,uk+1=u˜k,itfollowsfromTheorem3.3that
r(uk+1,βk)≤(1+δk)uk−uk+1.
Assertion(4.8)followsfrom(4.9)and(4.1)immediately.
1−ν2
4(4.8)
(4.9)
2≤Sincelimk→∞ηk=0,withoutlossofthegenerality,wecanassumethatνηk<1andηk
forallk.Thus,theresultsinTheorem4.2canbewrittenas
u
k+1
−u≤(1+
∗2
22ηk)uk
1−ν2
−u−r(uk+1,βk)2.
8
∗2
(4.10)
k22∞Since∞k=0ηk<+∞,itfollowsthatΠk=0(1+2ηk)<+∞andthesequence{u}generatedbytheinexactPPAinthissectionisbounded.Basedon(4.10),usingthesametechniqueasin[10],wecanprovetheconvergenceoftheinexactPPAproposedinthissection.AshortcomingoftheinexactPPAinthissectionistheinexactnesscriterion(4.1).Since
ξk
≤νηk
βk(uk−uk+1)
and
limηk=0,
(4.11)
k→∞
itrequirestherelativeaccuracyhigherandhigherastheiterationindexincreases.
5ThePPA-basedprediction-correctionmethod
TheinexactPPAinthelastsectiondirectlytakesanapproximatesolutionofthePPAsubproblem,u˜kin(3.10),asthenewiterateuk+1.Theshortcomingisthatitneedsaratherrestrictiveinexactnesscriterionaspointedin(4.11).Inthissection,weconsidertorelaxtheinexactnesscriterionto
ξk≤νβk(uk−u˜k)
and
ν∈(0,1),
whereu˜kandξkaredescribedin(3.10).However,insteadoftakingu˜kasthenewiterate,wetakeitasapredictor.Itoffersusadescentdirectionoftheunknowndistancefunctionu−u∗atthepointuk.
10
http://www.paper.edu.cn
Method3.APPA-basedprediction-correctionmethod.
Givenu0∈Rn.Fork=0,1,...,ifuk∈S∗,do:Predictionstep:Takeu˜kin(3.10)asapredictor.Initsinexactnesscriterion(3.11),
δk=ν
whichsatisfies
ν∈(0,1).
(5.1)
Correctionstep:Producethenewiterateuk+1bytakingastepsizeαkalongthedirection−d(uk,βk),
uk+1=uk−αkd(uk,βk),where
d(uk,βk)=(uk−u˜k)+ξk/βk
and
(uk−u˜k)Td(uk,βk)αk=γ,
d(uk,βk)2
γ∈(0,2).
(5.4)(5.3)(5.2)
Eachiterationoftheproposedmethodconsistsoftwosteps:predictionstepandcorrectionstep.Thepredictionstepoffersanapproximatesolutionof(3.1)-(3.2)andthecorrectionstepupdatesthenewiterate.Since(3.1)-(3.2)isthesubproblemofPPA,themethodisreferredtothePPA-basedprediction-correctionmethod.Infact,underCondition(5.1),thepredictionstepoffersusadescentdirectionoftheunknowndistancefunctionu−u∗atthepointuk.Thispropertywillbeprovedinthefollowingtheorem.
˜kbethepredictorgeneratedink-thiterationofMethod3.ThenwehaveTheorem5.1Letu
(uk−u∗)Td(uk,βk)≥(uk−u˜k)Td(uk,βk)where
d(uk,βk)=(uk−u˜k)+ξk/βk.UnderCondition(5.1)wehave
(uk−u˜k)Td(uk,βk)≥(1−ν)uk−u˜k2.Proof.Notethat,foranysolutionpointu∗,wehave
(βku∗)T{PΩ[F(˜uk)−ξk−βkuk]−F(u∗)}≥0.Keepinmindthat
F(˜uk)−ξk+βk(˜uk−uk)=PΩ[F(˜uk)−ξk−βkuk].
11
(5.9)(5.8)(5.7)(5.6)(5.5)
http://www.paper.edu.cn
SinceF(u∗)∈Ω,bysettingv=F(˜uk)−ξk−βkukandu=F(u∗)in(2.1),wehave
{[F(˜uk)−ξk−βkuk]−PΩ[F(˜uk)−ξk−βkuk]}T{PΩ[F(˜uk)−ξk−βkuk]−F(u∗)}≥0.Itfollowsfrom(5.9)that
(−βku˜k)T{PΩ[F(˜uk)−ξk−βkuk]−F(u∗)}≥0.Adding(5.8)and(5.10)weobtain
(u∗−u˜k)T{PΩ[F(˜uk)−ξk−βkuk]−F(u∗)}≥0.DuetothemonotonicityofF,wehave
(u∗−u˜k)T{F(u∗)−F(˜uk)}≥0.Adding(5.11)and(5.12)weget
(˜uk−u∗)T{F(˜uk)−PΩ[F(˜uk)−ξk−βkuk]}≥0.
SincePΩ[F(˜uk)−ξk−βkuk]=F(˜uk)−ξk+β(˜uk−uk)(see(5.9)),itfollowsthat
(˜uk−u∗)T{βk(uk−u˜k)+ξk}≥0andthusbythedefinitionofd(uk,βk),wehave
(uk−u∗)Td(uk,βk)≥(uk−u˜k)Td(uk,βk).
Therestassertion(5.7)followsfrom(3.11)and(5.1)immediately.
(5.13)(5.12)(5.11)(5.10)
Theorem5.1tellsusthat−d(uk,βk)isadescentdirectionoftheunknowndistancefunctionu−u∗atthepointuk.Alongthisdirection,wewanttofindastep-lengthandtodeterminethenewiteratethatclosertothesolutionset.Letusdenote
uk+1(α)=uk−αd(uk,βk)
asthestepsizedependentnewiterateandset
θk(α)=uk−u∗2−uk+1(α)−u∗2.
θk(α)canbeviewedasaprofitfunctionink-thiteration.Bydenoting
qk(α)=2α(uk−u˜k)Td(uk,βk)−α2d(uk,βk)2,andusing(5.5),wehave
θk(α)=uk−u∗2−uk−u∗−αd(uk,βk)2
≥2α(uk−u˜k)Td(uk,βk)−α2d(uk,βk)2=qk(α),
12
(5.16)(5.15)(5.14)
http://www.paper.edu.cn
andthusgetalow-boundofθk(α).Notethatqk(α)isaquadraticfunctionthatreachesitsmaximumat
∗αk
(uk−u˜k)Td(uk,βk)=.
d(uk,βk)2(5.17)
Inaddition,foranyuk∈S∗,sinceuk−u˜k2>ξk/βk2(see(5.1)),(uk−u˜k)Td(uk,βk)=uk−u˜k2+(uk−u˜k)Tξk/βk
11k
u−u˜k2+(uk−u˜k)Tξk/βk+ξk/βk2>221=d(uk,βk)2,
2
wehave
1∗
αk=(uk−u˜k)Td(uk,βk)/d(uk,βk)2>.
2
Thefollowingtheoremgivesthemainresultfortheproposedprediction-correctionmethod.
∗givenby(5.17).Forthenewiterateuk+1Theorem5.2Letd(uk,βk)begivenby(5.3)andαk
generatedby
(5.18)
uk+1=uk−αkd(uk,βk)with
∗
αk=γαk
(5.19)
andγ∈(0,2)(5.20)
wehave
uk+1−u∗2≤uk−u∗2−
γ(2−γ)(1−ν)k
u−u˜k2,
2
∀u∗∈S∗.
(5.21)
Proof.Notethatαkgivenin(5.20)isjustthesameasin(5.4)inthecorrectionstep.Itfollowsfrom(5.14)and(5.16)that
uk−u∗2−uk+1−u∗2≥qk(αk).Using(5.15),(5.18)and(5.7)weobtain
2
qk(αk)=2αk(uk−u˜k)Td(uk,βk)−αkd(uk,βk)2
∗∗k
=2αkγ(uk−u˜k)Td(uk,βk)−γ2αk(u−u˜k)Td(uk,βk)
1≥γ(2−γ)(1−ν)uk−u˜k2
2
andtheassertionisproved.
(5.22)
Theorem5.3Thesequence{uk}generatedbyMethod3(APPA-basedprediction-correctionmethod)forIVI(Ω,F)satisfies
uk+1−u∗2≤uk−u∗2−
γ(2−γ)(1−ν)
r(˜uk,βk)2.22(1+ν)
13
(5.23)
http://www.paper.edu.cn
Proof.Accordingto(5.21)weneedonlytoprove
r(˜uk,βk)≤(1+ν)uk−u˜k.
Assertion(5.24)followsfrom(3.17)and(5.1)immediately.
(5.24)
Forgivenνandγ,theresultsinTheorem5.3canbewrittenasuk+1−u∗2≤uk−u∗2−c0r(˜uk,βk)2,
c0>0.
(5.25)
Inequality(5.25)tellsusthatthesequence{uk}generatedbyMethod3iscontainedinS0(u∗)foranyu∗∈S∗anduk+1isclosertothesolutionsetthanuk.ThePPA-basedprediction-correctionmethodisalsoacontractionmethod.Basedon(5.25),wecandeducetheconvergenceofthemethod.
6Self-adaptivePPA-basedprediction-correctionmethod
Indeed,theinexactnesscriterion(5.1)ismuchmorerelaxedthan(4.1).Sometimeswecangettheapproximatesolutionof(3.10)whichsatisfiesCondition(5.1)directlyviachoosingasuitablelargeβk>0.AssumethatFisLipschitzcontinuouswithconstantL(seeDefinition2.1)andβk≥L/ν.Wetake
u˜k=uk−(1/βk){F(uk)−PΩ[F(uk)−βkuk]}asthepredictorandthus
F(uk)+βk(˜uk−uk)=PΩ[F(uk)−βkuk].Setting
ξk=F(˜uk)−F(uk),Equation(6.2)canberewrittenas
F(˜uk)−ξk+βk(˜uk−uk)=PΩ[F(˜uk)−ξk−βkuk],thisisjustthesameformulaas(3.10).Sinceβk≥L/ν,wehave
ξk=F(˜uk)−F(uk)≤Luk−u˜k≤νβk(uk−u˜k).
(6.5)(6.4)(6.3)(6.2)(6.1)
andtheinexactnesscriterion(5.1)issatisfied.Inprinciple,wecanuseArmijo’sliketechniquetofindasuitableβk.Foratrialβk>0,wegetatrialu˜kvia(6.1)andcalculate
F(uk)−F(˜uk)
τk=.
βk(uk−u˜k)
(6.6)
Ifτk≤ν,thistrialu˜kisacceptedasthepredictor.Otherwise,weenlargeβkbyafactorandrepeat
theprocess.Thenewiterateuk+1isupdatedbythesamecorrectioninthelastsection.
14
http://www.paper.edu.cn
Method4.ASelfadaptivePPA-basedprediction-correctionmethod.Givenu0∈Rnandatrialβ0>0.Fork=0,1,...,ifuk∈S∗,do:Predictionstep.Findanacceptablepredictoru˜k:1)u˜k=uk−(1/βk){F(uk)−PΩ[F(uk)−βkuk]};F(uk)−F(˜uk)
.τk:=
βk(uk−u˜k)2)Ifτk>ν,thenenlargeβkby
βk:=βk∗1.5,
andgoto1).
Correctionstep:Producethenewiterateuk+1by
uk+1=uk−αkd(uk,βk),where
d(uk,βk)=(uk−u˜k)+[F(˜uk)−F(uk)]/βk
and
(uk−u˜k)Td(uk,βk)
αk=γ,
d(uk,βk)2γ∈(0,2).
Sincewefindthesuitableβkbysomeself-adaptivetechnique,Method4isreferredtoSelf-adaptivePPA-basedprediction-correctionmethod.ThemethodissimilarasthemethodforVI(Ω,f)[8]butinaconvertform.Thegeneratedsequence{uk}stillsatisfies
uk+1−u∗2≤uk−u∗2−c0r(˜uk,βk)2,
c0>0.
(6.7)
UndertheassumptionthatFisLipschitzcontinuous,theacceptedsequence{βk}isup-bounded.LetβM=sup∞k=0βk,itfollowsfromLemma2.1that
uk+1−u∗2≤uk−u∗2−c0r(˜uk,βM)2,
c0>0.
Theconvergencecanbededucedfromtheaboveinequality.
Remark.Inthepredictionstep,insteadoftheenlargementtechnique2),wecanalsoenlargeβkbyβk:=βk∗τk∗1.2.Thesequence{βk}generatedbytheself-adaptivePPA-basedprediction-correctionmethodisnon-decreasing.However,ifβkistoolarge(andthusτkwillbesmall),itwillleadslowconvergence.Therefore,weallowthetrialβklimitedtimestobereducedbyβk+1=βk∗τk/0.9whenτk≤0.5.
7Conclusions
Similarwiththeclassicalvariationalinequalities,theinversevariationalinequalitieshaveawiderangeapplicationsindifferentfields.FormonotoneIVI(Ω,F),wepresentedaclassofproximal
15
http://www.paper.edu.cn
pointalgorithms,exact,inexactandself-adaptivemethods.Undercertainregularconditions,theconvergencespeedofallpresentedmethodsislinear.Forgivenuk,thesmallertheproximalparameterβkis,themoreexpensiveisthecomputationalloadforsolvingthesubproblemtosatisfy(3.10)-(3.11).Inordertoreducethecomputationalcostineachiteration,theself-adaptivePPA-basedprediction-correctionmethodisrecommended.
References
[1]A.Auslender,M.TeboulleandS.Ben-Tiba,Alogarithmic-quadraticproximalmethodfor
variationalinequalities,Comput.Optim.Appl.,12(1999),pp.31-40.[2]R.S.BurachikandA.N.Iusem,Ageneralizedproximalpointalogrithmforthevariational
inequalityprobleminaHilbertspace,SIAMJ.Optim.,8(1998),pp.197-216.[3]B.C.Eaves,Onthebasictheoremofcomplementarity,Math.Progr.,1(1971),pp.68–75.[4]J.Eckstein,ApproximateiterationsinBregman-function-basedproximalalgorithms,Math.
Progr.,83(1998),pp.113-123.[5]F.FacchineiandJ.S.Pang,Finite-dimensionalvariationalinequalitiesandcomplementarity
problems.SpringerSeriesinOperationsResearch,Spinger-Verlag,2003.[6]M.C.FerrisandJ.S.Pang,Engineeringandeconomicapplicationsofcomplementarityproblems,
SIAMRev.,39(1997),pp.669-713.[7]P.T.HarkerandJ.S.Pang,Finite-dimensionalvariationalinequalityandnonlinearcomplemen-tarityproblems:ASurveyoftheory,algorithmsandapplications,Math.Progr.,48(1990),pp.161–220.[8]B.S.He,Aclassofprojectionandcontractionmethodsformonotonevariationalinequalities,
Appl.Math.andOptimi.,35(1997),pp.69–76.[9]B.S.He,AGoldstein’stypeprojectionmethodforaclassofvariantvariationalinequalities,J.
Comput.Math.17(1999),pp.425-434.[10]B.S.He,Inexactimplicitmethodsformonotonegeneralvariationalinequalities,Mathematical
Programming,86(1999),pp.199-217.[11]B.Martinet,Regularizationd’inequationsvariationellesparapproximationssucessives,Revue
Francaised’InformatiqueetdeRechercheOp´erationelle,4(1970),pp.154-159.[12]J.SPangandJ.C.Yao,Onageneralizationofanormalmapandequation,SIAMJ.ControlandOptimization,33(1995),pp.168-184.[13]R.T.Rockafellar,Monotoneoperatorsandtheproximalpointalgorithm,SIAMJ.Con.Optim.,
14(1976),pp.877-898.[14]M.Teboulle,Convergenceofproximal-likealgorithms,SIAMJ.Optim.,7(1997),pp.1069-1083.[15]T.ZhuandZ.G.Yu,Asimpleproofforsomeimportantpropertiesoftheprojectionmapping,
MathematicalInequalities&Applications,7(2004),pp.453-456.
16
因篇幅问题不能全部显示，请点此查看更多更全内容