次梯度外梯度算法求解隨機(jī)變分不等式

張小娟

(重慶師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院， 重慶401331)

引言

隨機(jī)變分不等式(Random Variational Inequalities，SVI)問(wèn)題已經(jīng)被廣泛應(yīng)用到經(jīng)濟(jì)、供應(yīng)鏈網(wǎng)絡(luò)、交通運(yùn)輸和博弈論等領(lǐng)域[1-2]。本文考慮SVI問(wèn)題：找到x*∈X使得：

(x-x*)TF(x*)≥ 0，?x∈X

(1)

其中，X?n是非空閉凸集，映射F:n→n且F(x)：=E[f(x,ξ)]，ξ∈Ω是某概率空間(Ω,F,P)的一個(gè)隨機(jī)變量，E[f(x,ξ)]是數(shù)學(xué)期望，f(x,ξ)是一個(gè)連續(xù)映射。

目前求解問(wèn)題式(1)最常用的方法主要有兩類(lèi)：其一是樣本均值逼近(Sample Average Approximation，SAA)[3-4]，該法是將Nk個(gè)樣本函數(shù)的均值函數(shù)去代替期望值函數(shù)，從而在適當(dāng)?shù)臈l件下，當(dāng)k無(wú)限增大時(shí)證明代替后的問(wèn)題與原問(wèn)題等價(jià)；其二是隨機(jī)逼近(Sample Approximation，SA)[5]，該法是一種迭代算法，只采用一個(gè)樣本函數(shù)逼近期望值函數(shù)，目前很多隨機(jī)優(yōu)化問(wèn)題都是采用該法[6-7]。SA與SAA都是取樣本點(diǎn)逼近原問(wèn)題，但是SA方法每次取的樣本個(gè)數(shù)少，且數(shù)值表現(xiàn)好于SAA，因此，本文主要考慮SA方法來(lái)解問(wèn)題式(1)。

基于投影型的SA方法分為一次投影和兩次投影。一次投影迭代格式簡(jiǎn)單，但是理論不好[8-10]。兩次投影理論和數(shù)值結(jié)果好于一次投影，因此本文關(guān)注兩次投影即外梯度方法。最近Kannan等人[11]提出了基于外梯度的SA方法來(lái)求解問(wèn)題式(1)。其迭代格式為：

yk=ΠX[xk-αkf(xk,ξk)]

xk+1=ΠX[xk-αkf(yk,ηk)]

其中，αk>0是步長(zhǎng)；ξk、ηk是來(lái)自隨機(jī)變量ξ的樣本，并且獨(dú)立同分布。在F偽單調(diào)并且F有界或者Lipschitz連續(xù)下依概率1收斂。Iusem等人[12-13]提出用樣本均值的外梯度方法求解問(wèn)題式(1)，在F偽單調(diào)并且Lipschitz連續(xù)下依概率1收斂。雖然外梯度方法理論好于一次投影，但當(dāng)投影難以計(jì)算的時(shí)候，此法計(jì)算代價(jià)大。本文受確定型問(wèn)題的次梯度外梯度方法[14]的啟發(fā)，將基于外梯度的SA方法的第二次投影改投在一個(gè)半空間上，提出用基于次梯度外梯度的SA方法來(lái)求解問(wèn)題式(1)，并且新的迭代點(diǎn)是第k步和矯正步的一個(gè)凸組合，在適當(dāng)?shù)募僭O(shè)下獲得全局收斂性。

1 預(yù)備知識(shí)

定義1[1]設(shè)X?n是非空閉凸集，點(diǎn)y∈n到X上的投影為：

定義2[1]對(duì)任意的x∈n和α>0，定義問(wèn)題式(1)的剩余函數(shù)為：

當(dāng)α=1時(shí)，剩余函數(shù)簡(jiǎn)記為r(x)。

引理1[1]x*是問(wèn)題式(1)的解，當(dāng)且僅當(dāng)對(duì)任意α>0有：

x*=ΠX[x*-αF(x*)]

引理2[1]給定x∈n，對(duì)α∈(0,∞)，函數(shù)α|→是不增的。

引理3[1]設(shè)X?n是非空閉凸集，有：

(1)對(duì)任意的

(2)對(duì)任意的x∈n,y∈X，(x-ΠX(x))T(y-ΠX(x))≤0。

(3)對(duì)任意的

引理4[15]設(shè)對(duì)任意的x,y∈n，λ∈(0,1)有：

2 算法及其收斂性

投影算法迭代格式在解決SVI問(wèn)題時(shí)方法簡(jiǎn)單且效果較好，本文考慮用此法解決SVI問(wèn)題。目前用投影算法解決問(wèn)題式(1)的相關(guān)文獻(xiàn)甚少，自從文獻(xiàn)[8]提出基于基本投影的SA方法來(lái)求解SVI問(wèn)題后，就有學(xué)者提出基于外梯度的SA方法來(lái)求解SVI問(wèn)題。眾所周知當(dāng)投影難以計(jì)算的時(shí)候，外梯度就受限制，而基本投影反而有利，但基本投影理論本身具有局限。為此，本文考慮采用修正外梯度算法，并受次梯度外梯度算法的啟發(fā)，提出用基于次梯度外梯度算法的SA來(lái)求解SVI問(wèn)題，將第二次投影改投在一個(gè)半空間上，并且充分利用已知點(diǎn)信息，新的迭代點(diǎn)為第k步和矯正步的一個(gè)凸組合。

次梯度外梯度算法步驟為：

Step0選擇初始點(diǎn)x0∈n，γ>0，θ,δ∈(0,1)，初始樣本點(diǎn)令k:=0。

Step1給定xk，產(chǎn)生來(lái)自Ω的樣本ξk，計(jì)算xk=ΠX[xk-f(xk,ξk)]，停止，否則轉(zhuǎn)Step 2。

Step2計(jì)算：

(2)

這里的α∈{γθl,l∈∪0}使得下式成立的最大α為：

(3)

構(gòu)造半空間Sk：

Sk:={ω∈n|(xk-αkf(xk,ξk)-yk)T×

(ω-yk)≤0}

(4)

產(chǎn)生來(lái)自Ω的樣本ηk，計(jì)算：

tk=ΠSk[xk-αkf(yk,ηk)]

xk+1=δxk+(1-δ)tk

(5)

令k:=k+1，轉(zhuǎn)Step1。其中，αk>0是步長(zhǎng)；ξk,ηk是來(lái)自隨機(jī)變量ξ的樣本，并且獨(dú)立同分布；Sk為構(gòu)造的半空間。新的迭代點(diǎn)為一個(gè)凸組合的形式。定義由算法產(chǎn)生的隨機(jī)誤差：

為了獲得收斂性本文做如下假設(shè)：

假設(shè)1問(wèn)題式(1)的解集X*:=S(F,X)非空。

假設(shè)2設(shè)F:X→n是偽單調(diào)的,即對(duì)任意的x,y∈X有：

(y-x)TF(x)≥0?(y-x)TF(y)≥0

引理5若假設(shè)1-3成立，對(duì)任意的k∈N算法產(chǎn)生的序列{xk}滿(mǎn)足：

(6)

證明通過(guò)假設(shè)2和引理3可得到：

2αk(tk-xk)Tf(yk,ηk)=

2αk(tk-yk)Tf(yk,ηk)-2αk(yk-xk)Tf(yk,ηk)=

(7)

由于x*∈S(F,X)和F是偽單調(diào)的，則有(yk-x*)TF(yk)≥0，則：

(tk-x*)TF(yk)≥(tk-yk)TF(yk)

由于tk∈Sk以及式(4)，則有：

(tk-yk)T(xk-αkf(xk,ξk)-yk)≤0

(8)

因此，通過(guò)式(8)得到：

(tk-yk)T(xk-αkf(yk,ηk)-yk)=

(tk-yk)T(xk-αkf(xk,ξk)-yk)+

αk(tk-yk)T(f(xk,ξk)-f(yk,ηk))≤

αk(tk-yk)T(f(xk,ξk)-f(yk,ηk))

(9)

通過(guò)式(7)和式(9)得：

(10)

通過(guò)式(5)、式(10)和引理5，有：

(11)

因此，有：

(12)

結(jié)合式(11)和式(12)，有：

引理6如果假設(shè)2成立，算法在k+1不終止，有：

證明如果γ滿(mǎn)足式(2)，則αk=γ,否則有：

(13)

由假設(shè)2成立得到：

(14)

通過(guò)假設(shè)3和定理1，令：

ak:≡0

3 數(shù)值試驗(yàn)

例1考慮問(wèn)題式(1)，ξ是均勻分布在Ω=[0,1]，X=+×+×+且有：

例2考慮問(wèn)題式(1)，ξ是均勻分布在Ω=[0,1]，X=+×+×+且有：

例3考慮問(wèn)題式(1)，ξ是均勻分布在

有：

例4考慮問(wèn)題式(1)，ξ是均勻分布在

有：

這些例子對(duì)任意的ξ∈Ω都有唯一解x*=(0,1,1)T。選擇初始點(diǎn)x0=(0,0,0)T。

例1～例4的數(shù)值試驗(yàn)結(jié)果見(jiàn)表1，其中第二列x*是近似解，第三列是CPU時(shí)間。

表1 例1-例4的數(shù)值試驗(yàn)結(jié)果

從表1中可知，近似解都接近解點(diǎn)(0,1,1)T，由此證明該算法是可行的。

4 結(jié)束語(yǔ)

結(jié)合確定性變分不等式的投影算法和隨機(jī)逼近方法，提出用基于次梯度外梯度的SA方法來(lái)求解SVI問(wèn)題，在適當(dāng)?shù)募僭O(shè)下，F(xiàn)偽單調(diào)且Lipschitz連續(xù)下獲得了依概率1收斂，并且數(shù)值試驗(yàn)證明該方法有效。