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

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

(遼寧師范大學 數學學院， 遼寧 大連 116029)

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

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

(遼寧師范大學 數學學院， 遼寧 大連 116029)

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

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

有限維互補問題廣泛應用于工程領域、經濟領域、博弈論與網絡工程領域，并在數學規劃中發展成為一門行之有效的學科.為了反映出許多實際問題中的不確定數據，隨機形式的互補問題在近年來得到了廣泛關注.本研究關注如下一類特殊的隨機廣義垂直線性互補問題 (SEVLCP)：尋找x∈n使得

(1)

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

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

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

(2)

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

并在一定適當條件下給出收斂結果.受 ERM 方法的啟發，本研究中把 SAA 方法與一種新的基于CHKS 函數的光滑化函數相結合，提出了一種光滑化SAA方法來解決式(1).也就是說，基于這種新的光滑化函數的特性，把 SAA 問題轉化為無約束優化問題，然后通過求解一系列這樣的 SAA 優化問題，獲得式(1)的解.

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

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

1 預備知識

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

基于文獻[9]中提出的CHKS函數：

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

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

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

(ii) 當t≥0時， 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(·,·,·)的性質可得

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.

所以結論成立.

2 問題構造

基于CHKS函數，提出了一種光滑化函數來近似

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

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

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

其中,

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

其中,

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

現在給出矩陣B的一些性質.

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

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

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

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

令

(3)

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

(4)

反之，通過命題 1.1，可得當v→+∞時，

(5)

由于當N→+∞時，

(6)

對于i=1,2和l=1,2,…,n,有

這就意味著

(7)

通過引理 3.2，存在L>0 使得N足夠大時，對于每個l,

(8)

當N→+∞時，結合式(5)、式(7)和式(8)，得到當N→∞時，

(9)

同理，當N→∞時，

因此，有

證明完成.

[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

國家自然科學基金資助項目(11201210)

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

1000-1735(2017)03-0301-06

10.11679/lsxblk2017030301