求解一類特殊隨機(jī)廣義垂直線性互補(bǔ)問題的光滑化SAA方法

張 杰， 單文柏， 石 楠， 遲宏楊

(遼寧師范大學(xué) 數(shù)學(xué)學(xué)院， 遼寧 大連 116029)

求解一類特殊隨機(jī)廣義垂直線性互補(bǔ)問題的光滑化SAA方法

張 杰， 單文柏， 石 楠， 遲宏楊

(遼寧師范大學(xué) 數(shù)學(xué)學(xué)院， 遼寧 大連 116029)

隨機(jī)廣義垂直線性互補(bǔ)問題(SEVLCP)是一類隨機(jī)均衡問題,在金融工程、管理科學(xué)、交通均衡、博弈論等領(lǐng)域有重要的應(yīng)用.基于CHKS函數(shù)，提出了一類特殊廣義垂直線性互補(bǔ)問題的光滑化函數(shù)，并在此基礎(chǔ)上研究了一類特殊隨機(jī)廣義垂直互補(bǔ)問題的光滑化樣本均值近似方法.在一定的條件下給出了樣本充分大時(shí)保證光滑化樣本均值近似問題解的存在性的充分性條件并建立了這類方法的收斂性分析，即當(dāng)樣本數(shù)目充分大時(shí)，光滑化樣本均值近似問題的最優(yōu)解接近隨機(jī)廣義垂直互補(bǔ)問題的解.

隨機(jī)廣義垂直線性互補(bǔ)問題；樣本均值近似方法；光滑化

有限維互補(bǔ)問題廣泛應(yīng)用于工程領(lǐng)域、經(jīng)濟(jì)領(lǐng)域、博弈論與網(wǎng)絡(luò)工程領(lǐng)域，并在數(shù)學(xué)規(guī)劃中發(fā)展成為一門行之有效的學(xué)科.為了反映出許多實(shí)際問題中的不確定數(shù)據(jù)，隨機(jī)形式的互補(bǔ)問題在近年來(lái)得到了廣泛關(guān)注.本研究關(guān)注如下一類特殊的隨機(jī)廣義垂直線性互補(bǔ)問題 (SEVLCP)：尋找x∈n使得

(1)

其中,Mi(·):m→n×n,qi(·):m→n,i=1,2為隨機(jī)映射 ，ξ:Ω→Ξ∈m是定義在概率空間(Ω,F,P)上的隨機(jī)向量，E表示的是數(shù)學(xué)期望，極小化函數(shù) min表示對(duì)每個(gè)分量求極小.在本研究中, 假定Mi(ξ(ω)),qi(ξ(ω)),i=1,2是可測(cè)函數(shù).為了方便, 常把ξ(ω)簡(jiǎn)記為ξ.

在本研究中，用到一個(gè)數(shù)值方法來(lái)解決(1). 關(guān)鍵問題在于處理Mi(ξ)和qi(ξ)的期望值.如果問題(1)涉及數(shù)學(xué)期望的多重積分可以準(zhǔn)確計(jì)算，那么問題(1)可以被視為確定型廣義垂直線性互補(bǔ)問題(EVLCP)，因此它可以被現(xiàn)有的數(shù)值方法所解決.然而，如文獻(xiàn)[1]所示，在大多數(shù)情形中，如果想準(zhǔn)確地得到期望值會(huì)付出很大地代價(jià)，很多學(xué)者建議使用樣本均值近似(SAA)方法去解決這一問題，可參照文獻(xiàn)[2-5]以及 Shapiro 的綜述文獻(xiàn)[6]. SAA 方法的主要思想是生成一組ξ的獨(dú)立同分布樣本ξ1,…,ξN，并且構(gòu)造樣本均值近似期望值.

在本研究中，SEVLCP(1) 可以被下式近似：

(2)

x≥0,M(ξ(ω))x+q(ξ(ω))≥0, [M(ξ(ω))x+q(ξ(ω))]Tx=0, a.e.ω∈Ω

并在一定適當(dāng)條件下給出收斂結(jié)果.受 ERM 方法的啟發(fā)，本研究中把 SAA 方法與一種新的基于CHKS 函數(shù)的光滑化函數(shù)相結(jié)合，提出了一種光滑化SAA方法來(lái)解決式(1).也就是說(shuō)，基于這種新的光滑化函數(shù)的特性，把 SAA 問題轉(zhuǎn)化為無(wú)約束優(yōu)化問題，然后通過求解一系列這樣的 SAA 優(yōu)化問題，獲得式(1)的解.

關(guān)于這個(gè)方法，有兩個(gè)重要的理論問題：為了確保 SAA 優(yōu)化問題當(dāng)樣本量足夠大時(shí)解的存在性和所提出的光滑化方法幾乎處處收斂性.證明在適當(dāng)條件下，當(dāng)樣本量趨于無(wú)窮大時(shí)一系列的 SAA 解以概率 1 收斂到一個(gè)真問題的解.

下面給出一些記號(hào)說(shuō)明：‖·‖表示一個(gè)向量的歐氏范數(shù)或一個(gè)矩陣的Frobenius 范數(shù).B(x,δ)表示中心在x，半徑為δ>0的閉單位球，I為單位矩陣.對(duì)于連續(xù)可微映射F:n→m，JF(x)表示F的雅可比矩陣，對(duì)于集合D,coD表示D的凸包.

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

定義1.1[8]令F:n→m在n附近是Lipschitz連續(xù)函數(shù)，wF表示F的不可微點(diǎn)的集合.稱集合

基于文獻(xiàn)[9]中提出的CHKS函數(shù)：

提出了一種求解廣義垂直線性互補(bǔ)問題的光滑化函數(shù)：

命題1.1gt(·,·,·)有如下的一些性質(zhì).

(i)g0(a,b,c)=0?min {a,b,c}=0.

(ii) 當(dāng)t≥0時(shí)， min {a,b,c}-2t≤gt(a,b,c)≤min {a,b,c}.

證(i)由定義可知

g0(a,b,c)=0?min {φCHKS(a,b,0),c}=0?min {min {a,b},c}=0?min {a,b,c}=0.

(ii)由φCHKS(·,·,·)的性質(zhì)可得

min {a,b}-t≤φCHKS(a,b,t)≤min {a,b}.

所以

min{φCHKS(a,b,t),c}-t≤gt(a,b,c)≤min{φCHKS(a,b,t),c}.

而

min {φCHKS(a,b,t),c}≤min {min {a,b},c}=min {a,b,c}

且

min {φCHKS(a,b,t),c}≥min {min {a,b}-t,c}≥min {a,b,c}-2t.

所以結(jié)論成立.

2 問題構(gòu)造

基于CHKS函數(shù)，提出了一種光滑化函數(shù)來(lái)近似

w(x)=min {w1(x),w2(x),w3(x)}.

當(dāng)wi:n→,i=1,2,3是連續(xù)函數(shù)，很明顯w·在n中是連續(xù)的，但不是在所有點(diǎn)處都可微.對(duì)于任何t>0,給出了一類w(x)的光滑化函數(shù)，以w(t,x):n+1→來(lái)表示，被定義為

由命題 1.1可得w(t,x)的一個(gè)特征為：-2t≤w(t,x)-w(x)≤0.表明limt↓0w(t,x)=w(x)相對(duì)于x的收斂性是一致的.從定義可知如果wi是光滑函數(shù)，則w(t,x),t>0是關(guān)于x的光滑函數(shù)，利用此特征，定義：

其中,

易知，當(dāng)SEVLCP(1)有解時(shí)，上述優(yōu)化問題的最優(yōu)值為零，因此求解SEVLCP(1)等同于此時(shí)求無(wú)約束優(yōu)化問題的全局最優(yōu)解.采用獨(dú)立同分布隨機(jī)樣本ξj,j=1,…,N,一個(gè)確定的參數(shù)tN>0并引入光滑化函數(shù)gt(·),得到以下近似問題：

其中,

3 解的存在性與收斂性分析

現(xiàn)在給出矩陣B的一些性質(zhì).

定義3.1[10]考慮如上給出的B，則B有

min{B0x,B1x,…,Bkx}=0?x=0.

(b)滿足以下條件之一則有行W性質(zhì)， (i)如果B的所有行表示的行列式是正的. (ii)如果B的所有行表示的行列式是負(fù)的.

對(duì)于確定型 EVLCP，Gowda 和 Sznajder在文獻(xiàn)[11]中引入了0性質(zhì).由文獻(xiàn)[11]中的定理17可直接得到任何滿足行W性質(zhì)的B也滿足0性質(zhì).

令

(3)

當(dāng)v→+∞時(shí). 令v→+∞，以概率α≠0,由式(3) 有

(4)

反之，通過命題 1.1，可得當(dāng)v→+∞時(shí)，

(5)

由于當(dāng)N→+∞時(shí)，

(6)

對(duì)于i=1,2和l=1,2,…,n,有

這就意味著

(7)

通過引理 3.2，存在L>0 使得N足夠大時(shí)，對(duì)于每個(gè)l,

(8)

當(dāng)N→+∞時(shí)，結(jié)合式(5)、式(7)和式(8)，得到當(dāng)N→∞時(shí)，

(9)

同理，當(dāng)N→∞時(shí)，

因此，有

證明完成.

[1] JIANG H,XU H.Stochastic approximation approaches to the stochastic variational inequality problem[J].IEEE Transactions on Automatic Control,2008,53(6):1462-1475.

[2] RUSZCZYNSKI A， SHAPIRO A. Stochastic programming, handbooks in operations research and management science[M].Amsterdam:Elsevier,2003:1-682.

[3] XU H ,ZHANG D.Smooth sample average approximation of stationary points in nonsmooth stochastic optimization and applications[J].Math Program,2009,119:371-401.

[4] ZHANG L,ZHANG J ,WU Y.On the convergence of coderivative of SAA solution mapping for a parametric stochastic generalized equation[J].Set-valuedAnal,2011,19:107-134.

[5] ZHANG J, ZHANG L, PANG L P.On the convergence of coderivative of SAA solution mapping for a parametric stochastic Variational Inequality[J].Set-valued Anal,2012,20:75-109.

[6] SHAPIRO A,DENTCHEVA D,RUSZCZYNSKI A.Lectures on stochastic programming:modeling and theory[M].Philadelphia: SIAM,2009:1-307.

[7] CHEN X,FUKUSHIMA M.Expected residual minimization method for stochastic linear complementarity problems[J].Mathematics of Operations Research,2005,30(4):1022-1038.

[8] CLARKE F H.Optimization nonsmooth analysis,classics applied mathematics[M].2nd edition. Philadelphia:SIAM,1990:27-28.

[9] CHEN B,HARKER P T.Smooth approximations to nonlinear complementarity problems[J].Siam Journal on Optimization,1997,7(2):403-420.

[10] COTTLE R W,DANTZIG G B.A generalization of the linear complementarity problem[J].Journal of Combinatorial Theory,1970,2(1):79-90.

[11] GOWDA M S,SZNAJDER R.The generalized order linear complementarity problem[J].Siam Journal on Matrix Analysis & Applications,1994,15(3):779-795.

[12] ROCKAFELLAR T,WETS R J B.Variational analysis[M].Berlin,Heidelberg:Springer,1998:11-12.

AsmoothingSAAmethodforaspecialcaseofstochasticgeneralizedverticallinearcomplementaryproblem

ZHANGJie,SHANWenbai,SHINan,CHIHongyang

(School of Mathematics, Liaoning Normal University, Dalian 116029, China)

The stochastic generalized vertical linear complementary problem is a kind of stochastic equilibrium problem，which plays an important role in some areas for instance，financial engineering、management science transportation equilibrium and games theory. In this paper, based on the CHKS function, a smoothing function for a special case of generalized vertical linear complementary problem is proposed and then a smoothing sample average approximation method for solving this kind of stochastic generalized vertical complementary problem based on the CHKS function is studied. Under certain conditions, the sufficient conditions ensuring existence of solution of smoothed sample average approximation problem are obtained when the sample size is large enough and the convergence analysis of this method is established, that is, the optimal solution of smoothed sample average approximation problem approximates the solution of stochastic generalized vertical complementary problem when the sample size is large enough.

stochastic generalized vertical linear complementary problem；sample average approximation method;smoothing

O224

:A

2017-05-26

國(guó)家自然科學(xué)基金資助項(xiàng)目(11201210)

張杰(1982- )，男(蒙古族),遼寧朝陽(yáng)人，遼寧師范大學(xué)副教授，博士.

1000-1735(2017)03-0301-06

10.11679/lsxblk2017030301