魏 瀟

(西安電子科技大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，陜西西安 710126)

考慮概率空間(Ω，F(xiàn)，P)，其中，Ω∈Rm是相應(yīng)的樣本空間，P是已知的概率分布。隨機(jī)線性互補(bǔ)問(wèn)題［1－7］(SLCP)定義為，求 x∈Rn滿足

其中，ω∈Ω 是隨機(jī)變量;M(ω)∈Rn×n和q(ω)∈Rn分別是關(guān)于ω的隨機(jī)矩陣和隨機(jī)向量;a.s.表示幾乎必然成立。

通常，不存在x使得對(duì)所有的ω∈Ω，式(1)均有解。解決式(1)常用的方法是尋求適當(dāng)?shù)脑俣ㄐ问?，將其轉(zhuǎn)化為約束優(yōu)化問(wèn)題。Gürkan等［1］提出了期望值(EV)模型Rn滿足

此外，Chen和Fukushima［2］提出了求解SLCP的期望殘差(ERM)模型:求極小化問(wèn)題

的最優(yōu)解。其中

這里 Ψ∶R2→R 是一個(gè) NCP 函數(shù)，Ψ(a，b)=0 ??a≥0，b≥0，ab=0。

常用的NCP函數(shù)有min函數(shù)Ψmin(a，b)=min(a，b)和 Fischer－Burmeister(FB)［8］函數(shù) ΨFB(a，b)=a+

Chen和Zhang等［6］指出，由 ERM 模型所得到的數(shù)值解具有魯棒性。本文考慮隨機(jī)線性互補(bǔ)問(wèn)題的ERM模型

其中，ΨFB(x，ω)是由函數(shù) ΨFB(·)對(duì)應(yīng)形如式(4)的向量。

Zhang和Chen［3］提出了求解 ERM 模型的光滑投影梯度(SPG)算法。該算法借助經(jīng)典的求解約束極小化問(wèn)題的投影梯度法［9］對(duì)ERM模型進(jìn)行求解。通過(guò)數(shù)值實(shí)驗(yàn)可發(fā)現(xiàn)，算法中求解投影梯度方向時(shí)耗時(shí)較大。因此，需研究求解該模型更有效的算法。

文中假設(shè)M(ω)和q(ω)是ω的可測(cè)函數(shù)，且

定理 1［4，10－11］f(x)在 Rn上是連續(xù)可微的。

定義1［7］稱 M(·)是隨機(jī) R矩陣，若 x≥0，0M(ω)x≥0，xTM(ω)x=0，a.e.?x=0。

引理 2［6］若是R矩陣，則M(·)是隨機(jī)R00矩陣。

定理 2［6］對(duì)任意的q(·)，ERM(M(·)，q(·))的解集非空有界，當(dāng)且僅當(dāng)M(·)是隨機(jī)R0矩陣。

1 Barzilai－Borwein算法

借鑒 Liu 等［12－13］提出的求解 SLCP 的 Barzilai－Borwein(BB)算法，借助有效集策略，文中給出了求解SLCP的ERM模型BB算法。算法旨在求模型(5)的極小點(diǎn)，由引理1可知，在極小點(diǎn)處必有xki和▽f(xk)i(i=1～n)至少其中之一為0。據(jù)此可定義有效集

其中，N={1，2，L，n}。顯然，集合 U(xk)和 S(xk)所對(duì)應(yīng)的元素不滿足局部極小點(diǎn)條件，因此可對(duì)該部分元素進(jìn)行迭代更新。定義搜索方向

在此，γk即 Barzilai－Borwein步

其中，sk－1=xk－xk－1，yk－1=▽f(xk)－ ▽f(xk－1)，γmax＞γmin＞0。

算法1

步驟1 選擇參數(shù) ρ，σ∈(0，1)，令 x0≥0，k:=0。

步驟2 (非單調(diào)線搜索)記mk為滿足下式的最小非負(fù)整數(shù)。

令λk= ρmdk，xk+1=xk+ λkdk。

步驟3 令k:=k+1，轉(zhuǎn)步驟2。

2 數(shù)值結(jié)果

其中，Nl表示所選取的樣本數(shù)，ω1，ω2，L，ωNl是由Monte Carlo法得到的獨(dú)立同分布樣本。進(jìn)一步可計(jì)算其梯度的近似值

其中，VΨ(x，ωi)為 Ψ(x，ωi)在 x處的廣義雅克比矩陣，其計(jì)算方法如文獻(xiàn)［4］所示。

生成測(cè)試問(wèn)題的步驟如文獻(xiàn)［6］。對(duì)每個(gè)測(cè)試問(wèn)題，向量x%∈Rn+均是隨機(jī)生成的，其中，有n0(＜n)個(gè)元素在區(qū)間(0，c1)上，c1＞0，且期望矩陣正定。若c3=0，則x%是式(5)的一個(gè)解;若c3＞0，則x%不一定是式(5)的解，且測(cè)試問(wèn)題本身可能無(wú)解。由于是正定矩陣，故其是一個(gè)R0矩陣［8］，根據(jù)引理2及定理2，式(5)的解集為非空有界。

對(duì)算法1與文獻(xiàn)［3］中的SPG算法分別在c3=0和c3＞0時(shí)進(jìn)行比較。算法1和SPG算法的終止條件為。當(dāng)終止條件滿足或迭代次數(shù)超過(guò)100時(shí)，終止計(jì)算。

通過(guò)實(shí)驗(yàn)，算法1中所用到的參數(shù)取值為ρ=0.25，σ =10－4，C=5，γmax=106，γmin=10－6。測(cè)試問(wèn)題的參數(shù)選取 c1=20，μ =10，c4=15。

對(duì)所有的測(cè)試問(wèn)題，初始迭代點(diǎn)均選為

對(duì)每個(gè)初始迭代點(diǎn)，隨機(jī)生成10個(gè)問(wèn)題，表1和表 2 中，測(cè)試問(wèn)題記為(Nl，n，n0，c2，c3)，Itr表示平均迭代次數(shù)，Time表示平均CPU運(yùn)行時(shí)間，x1和x2分別表示SPG算法和算法1的數(shù)值解，f(·)代表對(duì)應(yīng)的函數(shù)值。通過(guò)計(jì)算迭代點(diǎn)處r(·)的值來(lái)檢驗(yàn)其最優(yōu)性。對(duì)于c3=0的情況，計(jì)算所得數(shù)值解x的相對(duì)誤差圖1和圖2中分別記錄了c=03和c3＞0時(shí)一定規(guī)模問(wèn)題的迭代時(shí)間Time與迭代點(diǎn)處最優(yōu)性度量r(·)的變化情況。

表1 算法SPG和算法1的比較(c3=0)

表2 算法SPG和算法1的比較(c3＞0)

圖1 c3=0，規(guī)模為Nl=1 000，n=50的數(shù)值結(jié)果

圖2 c3＞0，規(guī)模為Nl=1 000，n=100的數(shù)值結(jié)果

通過(guò)表1與表2及圖1與圖2的對(duì)比可發(fā)現(xiàn)，兩算法所求得的最優(yōu)值相差較小。算法1雖在一些問(wèn)題上比SPG算法的迭代次數(shù)略多，但卻能在更短的時(shí)間內(nèi)達(dá)到與SPG算法相近的效果，因此表明算法1的單步迭代耗時(shí)更少，并能更快地收斂到極小點(diǎn)。而導(dǎo)致這一結(jié)果的原因是SPG算法在計(jì)算投影梯度時(shí)耗費(fèi)較大，而算法1借助有效集策略，使用BB步進(jìn)行迭代，縮短了計(jì)算時(shí)間。

［1］Gürkan G，?zge A Y，Robinson SM.Sample－ path solution of stochastic variational inequalities［J］.Mathematical Programming，1999，84(6):313 －333.

［2］Chen Xiaojun，F(xiàn)ukushima M.Expected residual minimization method for stochastic linear complementarity problems［J］.Math Operation Result，2005，30(6):1022 －1038.

［3］Zhang Chao，Chen Xiaojun.Smoothing projected gradient method and its application to stochastic linear complementarity problems［J］.SIAM Journal Optimization，2009，20(3):627 －649.

［4］Zhou Guanglu，Caccetta L.Feasible semismooth newton method for a class of stochastic linear complementarity problems［J］.Journal Optimization Throry Application，2008，13(9):379－392.

［5］Lin Guihua，F(xiàn)ukushima M.Stochastic equilibrium problem and stochastic mathematical programs with equilibrium constrains:A survey［R］.Kyoto:Department of Applied Mathematics and Physics，Kyoto University，2009.

［6］Chen Xiaojun，Zhang Chao，F(xiàn)ukushima M.Robust solution of monotone stochastic linear complementarity problems ［J］.Math Program，2009，117(3):51 －80.

［7］Fang Haitao，Chen Xiaojun，F(xiàn)ukushima M.Stochastic R_0 matrix linear complementarity problems［J］.SIAM Journal Optimization，2007(18):482 －506.

［8］韓繼業(yè)，修乃華，戚厚鐸.非線性互補(bǔ)理論與算法［M］.上海:上?？萍汲霭嫔?，2006.

［9］袁亞湘，孫文瑜.最優(yōu)化理論與方法［M］.北京:科學(xué)出版社，1997.

［10］Sun Defeng，Qi Liqun.On NCP functions［J］.Computational Optimization Application，1999(13):201 －220.

［11］Chen Bintong，Chen Xiaojun，Christian Kanzow，et al.On NCP functions［J］.Computational Optimization Application，2000，88，(3):211 －216.

［12］Li Xiangli，Liu Hongwei，Sun Xiaojun.Feasible smooth method based on Barzilai－Borwein method for stochastic linear complementarity problem ［J］.Numerical Algorithms，2011，57(6):207－215.

［13］Huang Yakui，Liu Hongwei，Zhou Sha.A barzilai－ borwein type method for stochastic linear complementarity problems［J］.Complementarity Problem Numerical Algorithms，2011，57(2):207－215.