隨機變分不等式的隨機投影梯度算法

楊 燦, 夏福全

(四川師范大學 數(shù)學與軟件科學學院, 四川 成都 610066)

1 引言及預備知識

本文主要研究如下的隨機變分不等式問題:求x∈C使得

〈E[f(x,ξ(θ))],y-x〉≥0, ?y∈C,

(1)

其中,C是Rn中的非空閉凸子集,f(x,ξ):Rn×Rk→Rn是一個連續(xù)映射,ξ:Ω→Rk是定義在某概率空間(Ω,Λ,P)上的隨機變量,E[f(x,ξ(θ))]表示f(x,ξ(θ))相對于分布ξ的期望值.

眾所周知,變分不等式問題在交通、經(jīng)濟平衡、博弈論和網(wǎng)絡問題等方面都有著重要應用[1-5].在實際生活中,雖然許多問題只涉及到確定的數(shù)據(jù),但也有很多問題的數(shù)據(jù)包含隨機變量,比如幾個公司提供可替代商品的庫存和服務的價格競爭[6-7]、一些隨機動態(tài)博弈[8-9].很多包含隨機變量的問題都可以歸結為帶有隨機變量的變分不等式模型,即隨機變分不等式問題.隨機變分不等式問題是一般變分不等式問題的一個推廣[10-12],但關于隨機變分不等式的理論與算法都非常有限.由于隨機變分不等式有著廣泛的應用,因而,隨機變分不等式問題引起了越來越多的專家學者的關注和研究.

令F(x)=E[f(x,ξ(θ))],則(1)式變?yōu)橄铝械囊话阕兎植坏仁絾栴}:求x∈C滿足

〈F(x),y-x〉≥0, ?y∈C.

(2)

對于經(jīng)典的變分不等式問題(2),已經(jīng)有非常多的有效的方法可以求解.因此,當E[f(x,ξ(θ))]容易計算時,隨機變分不等式問題容易求解.但在實際應用中,E[f(x,ξ(θ))]的計算一般比較困難,比如雖然函數(shù)f(x,ξ(θ))已知,但是ξ的分布未知并且ξ的信息只能從過去樣本的數(shù)據(jù)中獲得;或者E[f(x,ξ(θ))]必須通過模擬近似估算而不能直接獲得.在這些情況下,已有求解一般變分不等式的數(shù)值方法等都不能直接用于求解隨機變分不等式問題.

最近,Malitsky[26]提出了求解變分不等式問題(2)的一種新的數(shù)值方法——投影反射梯度算法,具體迭代過程是:

xn+1=PC(xn-λ(F(yn)),
yn=2xn-xn-1,

其中,PC表示在集合C上的投影,λ>0是常數(shù).為了證明該算法所產(chǎn)生的迭代序列的收斂性,假設F是偽單調(diào)以及Lipschitz連續(xù)的.該算法的優(yōu)點在于:在迭代的每一步,只需要向可行集進行一次投影,迭代中也只需對函數(shù)F賦值一次.數(shù)值結果表明該算法快速且有效.

本文主要的工作是結合Malitsky[26]的投影反射梯度算法和隨機逼近方法,給出了隨機變分不等式(1)的隨機投影梯度方法.該方法結合了Malitsky[26]算法和隨機逼近方法的優(yōu)點,因而算法簡單快速.在一定條件下,證明了該算法所產(chǎn)生的迭代序列的全局收斂性.

定義1.1設C?Rn為非空閉凸集,對任意x∈Rn,定義

PC(x):=argmin{‖x-y‖:y∈C},

稱PC(x)是x在C上的投影.

定義1.2稱映射F:Rn→Rn是：

1) 單調(diào)的,若對于任意的x,y∈Rn,有

〈F(x)-F(y),x-y〉≥0;

2) 是偽單調(diào)的,若對于任意的x,y∈Rn,有

〈F(y),x-y〉≥0?〈F(x),x-y〉≥0;

3) 是偽單調(diào)-加的,若F是偽單調(diào)的,且對于任意的x,y∈Rn,有

〈F(x),x-y〉=0,〈F(y),x-y〉≥

0?F(x)=F(y);

4)Lipschitz連續(xù)的,若存在常數(shù)L>0,對于任意的x,y∈Rn,有

‖F(xiàn)(x)-F(y)‖≤L‖x-y‖.

引理1.1[27]設C是Rn中的非空閉凸集,對任意x∈Rn,則:

1) 〈PC(x)-x,y-PC(x)〉≥0,?y∈C;

2) ‖PC(x)-y‖2≤‖x-y‖2-‖x-PC(x)‖2,?y∈C.

E[Vn+1|Fn]≤(1+αn)Vn-γn+βn,

(3)

2 算法及其收斂性

總假設F(x)=E[f(x,ξ(θ))]且F是Lipschitz連續(xù)映射,其Lipschitz連續(xù)系數(shù)為L>0.對每個n≥0,令ωn=f(xn,ξn)-F(xn).對給定的常數(shù)λ>0,設

r(x,y):=‖y-PC(x-λF(y))‖+‖x-y‖.

首先介紹隨機變分不等式問題(2)解的迭代算法.

2) 對當前的迭代點xn和yn,令

xn+1=PC(xn-an(F(yn)+ωn)).

(4)

若r(xn,yn)=0,則算法停止.否則,計算

yn+1=2xn+1-xn；

(5)

3) 令n=n+1,回到2).

顯然,ωn=f(xn,ξn)-F(xn)是隨機誤差.易知,在迭代的第n步,用ξ的一個樣本ξn計算f(xn,ξn),并把它當作F(xn)的一個近似.因此,當近似F(xn)時,不需要知道變量ξ的概率分布.這非常有利于算法的實現(xiàn).

對任意n≥1,首先定義與算法2.1相關的σ-域為

Fn=(w0,w1,…,wn-1,y0,y1,…yn-1,x0,x1,…xn}.

(b)E[ωn|Fn]=0;

易知,假設2.1中條件(a)是隨機逼近中選擇步長的一個準則,參見文獻[29].假設條件(b)和(c)表示隨機誤差ωn是無偏的且是受控的方差標度.這些假設是隨機逼近方法相關文獻中的常用準則.

引理2.1若變分不等式問題(1)的解集S非空,z∈S且F:Rn→Rn為Lipschitz連續(xù)映射,則由算法2.1所生成的序列{xn}和{yn}滿足

(6)

證明根據(jù)xn+1=PC(xn-an(F(yn)+wn))以及引理2.1的2)有

‖xn+1-z‖2≤‖xn-an(F(yn)+wn)-z‖2-
‖xn-an(F(yn)+wn)-xn+1‖2=
‖xn-z‖2-‖xn-xn+1‖2-
2an〈F(yn)+wn,xn-z〉+
2an〈F(yn)+wn,xn-xn+1〉=
‖xn-z‖2-‖xn-xn+1‖2-
2an〈F(yn)+wn,xn+1-z〉=
‖xn-z‖2-‖xn-xn+1‖2-
2an〈F(yn),xn+1-z〉-2an〈wn,xn+1-z〉.

(7)

易知

-2an〈F(yn),xn+1-z〉=

-2an〈F(yn)-F(yn-1),xn+1-yn〉-
2an〈F(yn-1),xn+1-yn〉-
2an〈F(yn),yn-z〉.

(8)

由于{xn}?C,根據(jù)

xn=PC(xn-1-an(F(yn-1)+wn-1))

以及引理1.1的1)有

〈xn-xn-1+an(F(yn-1)+wn-1,xn-xn+1〉≤0,
〈xn-xn-1+an(F(yn-1)+wn-1,xn-xn-1〉≤0.

上述兩式相加,注意到y(tǒng)n=2xn-xn-1,有

〈xn-xn-1+an(F(yn-1)+wn-1),yn-xn+1〉≤0.

從而,根據(jù)xn-xn-1=yn-xn及上式可推知

2an〈F(yn-1),yn-xn+1〉≤
2〈xn-xn-1,xn+1-yn〉+2an〈wn-1,xn+1-yn〉=
2〈yn-xn,xn+1-yn〉+2an〈wn-1,xn+1-yn〉=
‖xn+1-xn‖2-‖xn-yn‖2-
‖xn+1-yn‖2+2an〈wn-1,xn+1-yn〉.

(9)

另一方面,由于F是Lipschitz連續(xù)映射,則

(10)

此外,根據(jù)Cauchy-Schwarz不等式及均值不等式,易知

(11)

將(8)～(10)式代入(7)式得到

(12)

引理得證.

選取常數(shù)λ>0滿足下列不等式

事實上,由于an→0(n→∞),當n充分大時,可以選取充分大λ>0滿足(13)式.

引理2.2若變分不等式問題(1)的解集S非空,z∈S且F：Rn→Rn為Lipschitz連續(xù)映射,則由算法2.1所生成的序列{xn}和{yn}滿足

(14)

其中λ>0滿足(13)式.

證明設z∈S,選取λ>0滿足(13)式,根據(jù)F的Lipschitz連續(xù)性以及Cauchy-Schwarz不等式有

2an〈F(yn),yn-z〉=

〈F(yn)-F(xn),yn-z〉+2an〈F(xn),yn-z〉≥

-2anL‖yn-xn‖‖yn-z‖+2an〈F(xn),yn-z〉≥

(15)

另一方面,根據(jù)F的Lipschitz連續(xù)性以及Cauchy-Schwarz不等式有

2an〈F(xn),yn-z〉=

2an〈F(xn),yn-xn〉+2an〈F(xn),xn-z〉=

2an〈F(xn)-F(yn),yn-xn〉+
2an〈F(yn),yn-xn〉+2an〈F(xn),xn-z〉≥
-2anL‖yn-xn‖-2an‖F(xiàn)(yn)‖×
‖yn-xn‖+2an〈F(xn),xn-z〉≥

-2anL‖yn-xn‖-2an‖F(xiàn)(yn)-F(z)‖×
‖yn-xn‖-2an‖F(xiàn)(z)‖‖yn-xn‖+
2an〈F(xn),xn-z〉≥-2anL‖yn-xn‖-
2anL‖yn-z‖‖yn-xn‖-
2an‖F(xiàn)(z)‖‖yn-xn‖+2an〈F(xn),xn-z〉≥

將(16)式代入(15)式可得(14)式,結論成立.

定理2.1假設變分不等式問題(1)的解集S非空,F：Rn→Rn為偽單調(diào)-加Lipschitz連續(xù)映射,則由算法2.1所生成的序列{xn}幾乎處處收斂于問題(1)的解.

證明對任意z∈S,λ>0滿足(13)式,根據(jù)引理2.1和引理2.2有

‖xn+1-z‖2≤

根據(jù)(17)式及假設條件2.1可得

E[‖xn+1-z‖2|Fn]≤

(18)

令

由假設條件2.1及(13)式可知,對充分大的n有,ξn>0,ηn>0,從而(18)式變?yōu)?/p>

E[‖xn+1-z‖2|Fn]≤

(19)

再設

γn=ξn‖xn-yn‖2+ηn‖xn-yn-1‖2+
2an〈F(xn),xn-z〉,

(20)

注意到z∈S是變分不等式(1)的解,xn∈C,故

〈F(xn),xn-z〉≥0.

(21)

另外,根據(jù)假設條件2.1及(13)式可知

(22)

從而根據(jù)(20)～(22)式可知

(23)

此外,對任意的y∈C,由于z∈S,有〈F(z),y-z〉≥0.因此,對任意的y∈C有

由于對任意x∈C,F(x)=E[f(x,ξ(θ))],故

〈E[f(x,ξ(θ))],y-x〉≥0, ?y∈C,

[1]BREZISH.Opérateursmaximauxmonotones:etsemi-groupesdecontractionsdanslesespacesdeHilbert[J].JAcousticalSocietyAmerica,1989,125(4):2680.

[2]GIANNESSIF,MaugeriA.VariationalInequalityandNetworkEquilibriumProblems[M].NewYork:PlenumPress,1995:315-320.

[3]VERMARU.Generalconvergenceanalysisfortwo-stepprojectionmethodsandapplicationtovariationalproblems[J].ApplMathLett,2005,18(11):1286-1292.

[4]FACCHINEIF,PANGJS.Finite-dimensionalVariationalInequalitiesandComplementaryProblemsVolumeI/II[M].NewYork:Springer-Verlag,2003.

[5]LUOZQ,PANGJS,RALPHD.MathematicalProgramswithEquilibriumConstraints[M].Cambridge:CambridgeUniversityPress,1996.

[6]CHENFY,YANH,YAOL.Anewsvendorpricinggame[J].IEEETransactionsonSystemsManandCyberneticsPartASystemsandHumans,2004,34(4):450-456.

[7]CMAHAIANS,VANRYZING.Inventorycompetitionunderdynamicconsumerchoice[J].OperationsResearch,2001,49(5):464-657.

[8]BASART,OLSDERG.DynamicNoncooperativeGameTheory[M].Philadeiphia:SIAM,1999.

[9]FILARJ,VRIEZEK.CompetitiveMarkovDecisionProcesses[M].Berlin：Springer-Verlag,1996.

[10]GURKANG, ?ZGEAY,ROBINSONSM,etal.Samplepathsolutionofstochasticvariationalinequalities,withapplicationstooptionpricing[C].Proceedingsofthe28thconferenceonWintersimulation-WSC96,1996.DOI:10.1145/256562.256646.

[11]GURKANG,OZGEAY,ROBINSONSM.Sample-pathsolutionofstochasticvariationalinequalities[J].MathematicalProgramming,1999,84(2):313-333.

[12]ROBINSONSM.Analysisofsample-pathoptimization[J].MathematicsofOperationsResearch,1996,21(3):513-528.

[13]SHAPIROA,DENTCHEVAD,RUSZCZYNSKIA.LecturesonStochasticProgramming:ModelingandTheory[M].Philadeiphia:SIAM,2009.

[14]XUH.Sampleaverageapproximationmethodsforaclassofstochasticvariationalinequalityproblems[J].AsiaPacificOperationalResearch,2011,27(1):103-119.

[15]ROBBINSH,MONROS.Astochasticapproximationmethod[J].AnnMathematicalStatistics,1951,22(3):400-407.

[16]ROBINSONSM,MONROS.Onastochasticapproximationmethod[J].AnnMathematicalStatistics,1954,25(3):463-483.

[17]JIANGHY,XUHF.Stochasticapproximationapproachestothestochasticvariationalinequalityproblem[J].IEEETransactionsonAutomaticControl,2008,53(6):1462-1475.

[18]KOSHALJ,NEDICA,SHANBHAGUV.Regularizediterativestochasticapproximationmethodsforstochasticvariationalinequalityproblems[J].IEEETransactionsonAutomaticControl,2013,58(3):594-609.

[19]NEMIROVSKIA,JUDITSKYA,LANG,etal.Robuststochasticapproximationapproachtostochasticprogramming[J].SIAMJOptim,2009,19(4):1574-1609.

[20]JUDITSKYA,NEMIROVSKIA,TAUVELC.Solvingvariationalinequalitieswithstochasticmirror-proxalgorithm[J].StochasticSystems,2011,1(1):17-58.

[21]BERTSEKASDP,TSITSIKLISJM.Neuro-dynamicprogramming[J].AthenaScientific,1996,27:1687-1692.

[22]ERMOLIEVY.StochasticQuasigradientMethods,NumericalTechniquesforStochasticOptimization[M].NewYork:Springer-Verlag,1988.

[23]KUSHNERHJ,YING.StochasticApproximationandRecursiveAlgorithmsandApplications[M].NewYork:Springer-Verlag,2003.

[24]ORMANA.Optimizationofstochasticmodels,theinterfacebetweensimulationandoptimization[J].OperationalResearchSociety,1998,49(6):675-675.

[25]FREYJ.Introductiontostochasticsearchandoptimization:estimation,simulation,andcontrol[J].Wiley-Interscience,2004,46(3):368-369.

[26]MALITSKYY.Projectedreflectedgradientmethodsformonotonevariationalinequalities[J].SIAMJOptim,2015,25(1):502-520.

[27]BAIOCCHIC,CAPELOA.VariationalandQuasivariationalInequalities[M].NewYork:JohnWiley,1984.

[28]ROBBINSH,SIEGMUNDD.Aconvergencetheoremfornonnegativealmostsupermartingalesandsomeapplications[C]//OptimizingMethodsinStatistics.RustagiJS,ed.NewYork:Academic,1971:233-257.

[29]PFLUGGC.Optimizationofstochasticmodels[C]//TheInterfaceBetweenSimulationandOptimization.NewYork:KluwerAcademic,1996.