基于CVaR的逼近算法求解一類(lèi)隨機(jī)逆變分不等式

山述強(qiáng)，宋建成

(西南民族大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，四川 成都 610041)

1 引言

假定(Ω，?，P)是一概率空間，〈.，.〉表示Rn空間的內(nèi)積，K?Rn為非空閉凸子集，有限維空間中的隨機(jī)逆變分不等式(SIVI(f，h))可以表示為:找x*∈Rn，滿足

其中f:Rn×Ω→Rn，h:Rn→Rn為兩向量值函數(shù)，a.s.表示在概率 P下幾乎必然成立.

隨機(jī)逆變分不等式可以被廣泛的應(yīng)用于交通均衡、網(wǎng)絡(luò)經(jīng)濟(jì)均衡、物流供應(yīng)鏈管理等實(shí)際問(wèn)題.對(duì)于上述問(wèn)題，由于模型受隨機(jī)因素影響，一般很難求解，所以需要建立合理的模型求解隨機(jī)逆變分不等式.

對(duì)于類(lèi)似的問(wèn)題，許多學(xué)者做了相應(yīng)的研究.例如:Chen和Fukushima[1]研究了隨機(jī)線性相補(bǔ)問(wèn)題，并用期望殘差極小化方法給出了隨機(jī)線性相補(bǔ)問(wèn)題的解；Fang、Chen和Fukushima[2]研究了隨機(jī)線性相補(bǔ)問(wèn)題的隨機(jī)R0函數(shù)；Zhang和Chen[3]研究了隨機(jī)非線性相補(bǔ)問(wèn)題，并將其應(yīng)用于交通均衡中；Luo和Lin[4]用期望殘差極小化方法求解隨機(jī)變分不等式問(wèn)題；Ma和Huang[5]用期望殘差極小化方法求解一類(lèi)隨機(jī)擬變分不等式問(wèn)題.其它工作可參見(jiàn)于文獻(xiàn)[6-13].

但是，如果將殘差量看作損失，那么期望殘差極小化方法并沒(méi)有對(duì)風(fēng)險(xiǎn)加以考慮，所以僅僅極小化期望可能帶來(lái)高風(fēng)險(xiǎn)，這使得隨機(jī)逆變分不等式在網(wǎng)絡(luò)經(jīng)濟(jì)，物流管理等領(lǐng)域中受到極大限制.為此，Chen和Lin[14]研究了關(guān)于基于CVaR的逼近算法求解了隨機(jī)變分不等式，Ma和Huang[15]改進(jìn)了Chen和Lin在文獻(xiàn)[14]中的模型，并用改進(jìn)后的模型研究了一類(lèi)隨機(jī)變分不等式.受上述學(xué)者的工作啟發(fā)，將采用基于CVaR的逼近算法求解一類(lèi)隨機(jī)逆變分不等式問(wèn)題.并用擬蒙特卡洛方法給出該問(wèn)題的解.

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

定義2.1函數(shù)g:Rn×Ω→R滿足下面條件:

(1)?x∈K，g(x，ω)≥0， a.s.；

(2)x*∈K，g(x*，ω)≥0 a.s.?x*是隨機(jī)逆變分不等式的解；則稱(chēng)g為隨機(jī)逆變分不等式在集合K上的間隙函數(shù).

令X＝{x∈Rn:h(x)∈K}為SIVI(f，h)的可行集，則由文獻(xiàn)[16]中引理2易得下面引理.

引理2.1定義函數(shù)其中0＜α＜1，則有下面結(jié)論:

① ?x∈X，g(x，ω) ≥0，a.s.

②x*∈X，g(x*，ω)≥0 a.s.?x*是隨機(jī)逆變分不等式的解；

③SIVI(f，h)等價(jià)于求解下面的優(yōu)化問(wèn)

其中Rα(x，ω)＝h(x)－PK(h(x)－αf(x，ω))，PK表示在K上的投影.

由引理2.1可知gα(x，ω)為SIVI(f，h)的間隙函數(shù)，將稱(chēng)其為SIVI(f，h)的正則化間隙函數(shù).

令φ(x，μ，ω)＝μ＋(1－β)－1[gα(x，ω)－μ]＋，基于CVaR 的模型就是考察下面的優(yōu)化問(wèn)題:

其中0＜β＜1，[t]＋＝max{t，0}，ρ:Ω → [0，＋∞) 為概率密度函數(shù)，并滿足

對(duì)于給定的u＞0，定義函數(shù)如下:

易證

引理2.2[15]對(duì)于任意的t，s，有下面結(jié)論:

由于問(wèn)題(1)包含數(shù)學(xué)期望，使得其求解變得極為困難.因此，將用擬蒙特卡洛方法給出問(wèn)題(1)的解.考察下面的優(yōu)化問(wèn)題:

其中 Φ(x，μ，ω，u)＝μ＋(1－β)－1[gα(x，ω)－μ]u，Ωk＝{ωj∈Ω:j＝1，2，…，Nk} 為觀測(cè)集，當(dāng)k→∞時(shí)，Nk→∞.

引理2.3[17]如果Φ(ω)在Ω上可積，那么

由引理2.1和文獻(xiàn)[3]中的方法易得下面引理.

引理2.4 假定對(duì)于任意的ω∈Ω，f(.，ω)是連續(xù)可微的，h(x)連續(xù)可微，且滿足對(duì)于x∈X，E(｜｜f(x，ω)｜｜2)＜∞，E(｜｜?xf(x，ω)｜｜2)＜∞.那么，對(duì)于任意的ω∈Ω ，gα(x，ω)對(duì)于x也是連續(xù)可微的.特別的，對(duì)于任意的x∈X，ω∈Ω，有

3 主要結(jié)果

在這一節(jié)中，將給出優(yōu)化問(wèn)題(1)的解存在的一些充分條件，并在一定條件下求解出該問(wèn)題.

定理3.1定義向量值函數(shù)M2(ω)，N2(ω)如下:

其中Ω0表示Ω的一個(gè)零測(cè)集.若分別用λmin(G)，λmax(G)表示對(duì)稱(chēng)矩陣G的最小和最大特征值.那么，下列結(jié)論成立:

(i)如果，那么，對(duì)于幾乎處處的ω∈Ω，gα(.，ω)為一凸函

數(shù)；進(jìn)一步的，優(yōu)化問(wèn)題(1)為一凸優(yōu)化問(wèn)題.

(ii)如果，那么，對(duì)于幾乎處處的ω∈Ω，gα(.，ω)為一強(qiáng)凸函數(shù).優(yōu)化問(wèn)題(1)中目標(biāo)函數(shù)Θ(x，μ)是關(guān)于x的強(qiáng)凸函數(shù).

證明:(i)由[15]中定理1可知，對(duì)于任意的半正定矩陣A，

所以α是良定義的.

因?yàn)?，?3)式可知，對(duì)于任意的y，幾乎處處的ω∈Ω，

h(.，y，ω)的Hessen矩陣是半正定的，所以對(duì)于任意的y，幾乎處處的ω∈Ω，h(x，y，ω)是關(guān)于x的凸函數(shù).由gα(x，ω)的定義可知對(duì)于幾乎處處的ω∈Ω，gα(x，ω)是關(guān)于 x的凸函數(shù)，進(jìn)而可知優(yōu)化問(wèn)題 (1)是凸優(yōu)化問(wèn)題.

(2)由(3)式可知，當(dāng)時(shí)，對(duì)于任意的y，幾乎處處的ω∈Ω，h(.，y，ω)的Hessen矩陣是正定的，那么對(duì)于任意的y，幾乎處處的ω∈Ω，h(x，y，ω)是關(guān)于x的強(qiáng)凸函數(shù)，所以對(duì)于幾乎處處的ω∈Ω，gα(x，ω)是關(guān)于x的強(qiáng)凸函數(shù)，進(jìn)而可知優(yōu)化問(wèn)題 (1)中目標(biāo)函數(shù)Θ(x，μ)是關(guān)于x的強(qiáng)凸函數(shù).

注3.1:由定理3.1和[18]中定理3.2、定理3.3可知，當(dāng)Θ(x，μ)滿足一定條件時(shí)，優(yōu)化問(wèn)題(1)有解.

定理3.2定義函數(shù)M2:Ω →Rn×n，N2:Ω →Rn，假定h(x)＝M1x＋N1，

有界.

證明.由定理3.1可知，E(gα(x，ω))是強(qiáng)凸函數(shù).那么

假設(shè)存在c*使得Lc*( )無(wú)界.那么存在(xk，μk)?Lc*( )滿足:

由Lc()和Θ(x，μ)的定義可知，對(duì)于任意的 k，有

和

因?yàn)檫M(jìn)而可知，對(duì)于任意的 k，μk有界，所以

從而有

這與c*有界矛盾.所以，對(duì)于任意的正數(shù)c，Lc()有界.

定理3.3令h(x)＝M1x＋N1，f(x，ω)＝M2(ω)x＋N2(ω)，并滿足:

如果(xk，μk)為優(yōu)化問(wèn)題 (2)的最優(yōu)解，則(xk，μk)的所有聚點(diǎn)都是優(yōu)化問(wèn)題 (1)的最優(yōu)解.

證明:不妨假設(shè)(x*，μ*)是(xk，μk)的聚點(diǎn)，即(xk，μk)→(x*，μ*)∈X×Rn，在此將分三步證明定理成立.

首先，證明對(duì)于任意的(x，μ)∈X×Rn，下面式子成立:

由引理2.2知

因?yàn)?，所以上式收斂?，進(jìn)而可知(5)式成立.

其次，證明

由中值定理可知

所以由(4)式可知下面式子成立:

(7)式可知(6)式成立.

由引理2.2可知，下式成立:

最后，證明(x*，μ*)是優(yōu)化問(wèn)題(1)的解.

因?yàn)?xk，μk)是優(yōu)化問(wèn)題 (2)的解.所以，對(duì)于任意的(x，μ)∈K×Rn，有

ρ(ωj)，所以，(x*，μ*) 是優(yōu)化問(wèn)題(1)的解.

注3.2 由定理3.3可知，優(yōu)化問(wèn)題(1)的解可以先通過(guò)求解優(yōu)化問(wèn)題(2)的解，再用定理3.3的逼近算法求得.

注3.3 定理3.3的結(jié)果是對(duì)文獻(xiàn)[14]中定理2的推廣.當(dāng)h(x)＝x時(shí)，定理3.3將退化為文獻(xiàn)[14]中的定理2.

[1] CHEN X J，F(xiàn)UKUSHIMA M.Expected residual minimization method for stochastic linear complementarity problems[J].Mathematics of Operations Research，2005，30:1022-1038.

[2] FANG H，CHEN X J，F(xiàn)UKUSHIMA M.Stochastic$R＿0$matrix linear complementarity problems[J].SIAM Journal on Optimization，2007，18:482-506.

[3] ZHANG C，CHEN X J.Stochastic nonlinear complementarity problem and applications to traffic equilibrium under uncertainty[J].Journal of Optimization Theory and Applications，2008，137:277-295.

[4] LUO M J，LIN G H.Expectted residual minimization method for stochastic variational inequality problems[J].Journal of Optimization Theory and Applications，2009，140:103-116.

[5] MA H Q，HUANG N J.Expected residual minimization method for a class of stochastic quasivariational inequality problens[J].Journal of Applied Mathematics，2012，2012:doi:10.1155/2012/816528.

[6] LIN G H，F(xiàn)UKUSHIMA M.New reformulations for stochastic nonlinear compelementarity problems[J].Optimization Methods and Software，2006，21:551-564.

[7] JANG H，XU H.Stochastic approximation approaches to the stochastic variational inequality problems[J].IEEE Trans Automat Control，2008，53:1462-1475.

[8] LUO M J，LIN G H.Convergence results of the ERM method for nonlinear stochastic variational problems[J].Journal of Optimization Theory and Application，2009，142:569-581.

[9] MA H Q，WU M，HUANG N J，et al.Expected residual minimization method for stochastic variational inequality problem with nonlinear perturbations[J].Applied Mathematics and Computation，2013，219:6256-6267.

[10] CHEN X J，WETS J B，ZHANG Y F.Stochastic variational inequalities:residual minimization smoothing sample average approximations[J].SIAM Journal of Optimization，2012，22:649-673.

[11] CHEN X J，ZHANG C，F(xiàn)UKUSHIMA M.Robust solution of monotone stochastic linear complementarity problems[J].Mathematical Programming，2009，117:51-80.

[12] LUO M J，LIN G H.Stochastic variational inequality problems with additional constraints and their applications in supply chain network equilibria[J].Pacific Journal of Optimization，2011，7:263-279.

[13] MA H Q，WU M，HUANG N J.Expected residual minimization method for stochastic variational inequality problem with nonlinear perturbations[J].Applied Mathematics and Computation，2013 219:6256-6267.

[14] CHNE X J，LIN G H.CVaR-based formulation and approximation method for a class of stochastic variational inequality problems[J].Numerical Algebra，Control and Optimization，2011，1:35-48.

[15] MA H Q，HUANG N J.CVaR-based formulation and approximation method for a class of stochastic variational inequality problems[J].Mathematical inequalities and Applications，2013，16:981-998.

[16] D.Aussel，R.Guptab and A.Mehrab，Gap functions and error bounds for inverse quasi-variational inequality problems，Journal of Mathematical Analysis and Applications，2013，407，270-280.

[17] .PATRICK B.Probability and Measure[M].New York:Wiley Interscience，1995.

[18] M.Fukushima.非線性最優(yōu)化基礎(chǔ)[M].林桂華，譯.北京:科學(xué)出版社，2011.