求解隨機(jī)線性互補(bǔ)問題的光滑牛頓投影算法

單錫泉

（山東科技大學(xué)數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，山東 青島266590）

0 引言

線性互補(bǔ)問題（LCP）[1]定義為：尋求x∈Rn，滿足

其中M∈Rn×n是一個(gè)n×n實(shí)矩陣，q∈Rn是一個(gè)n維矢量。

當(dāng)我們研究實(shí)際問題時(shí)，總會(huì)受到許多不確定因素的影響，使得線性互補(bǔ)問題包含了不確定的數(shù)據(jù)，這就是隨機(jī)線性互補(bǔ)問題（SLCP）[2-9]。本文研究一類特殊的隨機(jī)線性互補(bǔ)問題，即樣本空間Ω只包含有限個(gè)不確定因素ω。假設(shè)Ω=｛ω1，ω2，…，ωm｝，該問題描述為：尋求x∈Rn，滿足

其中。于是求解問題(1)等價(jià)于求解下列問題

下面我們引入幾個(gè)概念。

如果κ不依賴于x，則稱Hμ（·）為H的一致光滑逼近函數(shù)。

定義1.2 設(shè)M∈Rn×n，若M的所有主子式皆為非負(fù)，則稱M為P0矩陣。

定義1.3 函數(shù)φ∶R2→R稱為NCP函數(shù)，如果它滿足

懲罰FB函數(shù)[10]

其中對(duì)任意的標(biāo)量c，c+=max｛0，c｝是一類常見的NCP函數(shù)。下面我們構(gòu)造懲罰FB函數(shù)的光滑逼近函數(shù)

其中

因此，若問題(1)有解，問題(1)等價(jià)于問題(3)。

令w=（μ，z），系統(tǒng)(4)的價(jià)值函數(shù)可以定義為

若問題(1)有解，求解系統(tǒng)(3)等價(jià)于尋求下列優(yōu)化問題的全局解

其中γ＞0是一個(gè)與w有關(guān)的常數(shù)，則問題(5)的一個(gè)穩(wěn)定點(diǎn)可以用來衡量[11]?，F(xiàn)在基于問題(5)，給出其相應(yīng)的算法。

1 光滑投影牛頓算法

該算法通過運(yùn)用一些擾動(dòng)技術(shù)和選擇恰當(dāng)?shù)乃阉鞣较虿呗裕ＷC了在相應(yīng)最優(yōu)化問題的任何非穩(wěn)定點(diǎn)處光滑化變量嚴(yán)格為正這一關(guān)鍵點(diǎn)。對(duì)于μ＞0，算法通過使用一個(gè)擾動(dòng)策略，可以保證在迭代中μ＞0。令α∈（0，1）為一常數(shù)，。對(duì)k=1，2，…，定義序列｛βk｝為

算法2.1

步1：令

步2：(計(jì)算擾動(dòng)方向)

如果線性系統(tǒng)

有解并且有

步3：(線搜索)

記滿足下式的最小非負(fù)整數(shù)m為mk：

其中對(duì)任意的λ∈（0,1］，

參考文[11]，可得

其中

值得注意的是，因?yàn)閃=R×Z，這暗示了算法中式(13)的投影計(jì)算只作用于任何點(diǎn)w=（μ，z）的分量z。

2 算法分析

引理3.1[12]對(duì)任意的凸集，投影算子滿足

(i)對(duì)任意的w∈W，

(ii)

是不增的。

下面的性質(zhì)顯然成立。

性質(zhì)3.2[13]由式(7)定義的序列｛βk｝有如下性質(zhì)：

(i)序列｛βk｝是不增的；

(ii)對(duì)所有的k，βk滿足

以下結(jié)果表明算法在迭代過程中能保持μ＞0。

證明：該性質(zhì)可以通過歸納法來證。

對(duì)k=0,由算法2.1和β0的選擇可知

假設(shè)式(16)對(duì)k成立，接下來證明在k+l處結(jié)論依然成立。

注意到，算法中的擾動(dòng)搜索方向可以看成是由兩部分組成的：

其中λk是在第k次迭代中可接受的步長?，F(xiàn)在考慮方向針對(duì)變量μ的部分。從式(4)和(13)中，有

其中Gk表示G（wk）。根據(jù)搜索方向d（λk）的計(jì)算，即有

其中不等式是由γk的定義(8)得到的。從而有

其中第二個(gè)不等式是由性質(zhì)3.2中βk的單調(diào)性決定的，最后一個(gè)不等式則來自于前一點(diǎn)wk處的假設(shè)。因而，可以得到

另外，如果wk和wk+1不是問題的穩(wěn)定點(diǎn)，則由性質(zhì)知βk≥βk+1＞0.因此，式(16)在點(diǎn)wk+1處也成立，即證。

令｛wk｝是由算法2.1產(chǎn)生的迭代序列。該性質(zhì)表明如果算法不在有限步內(nèi)停止于一個(gè)穩(wěn)定點(diǎn)，則對(duì)任意的k，有μk＞0。這個(gè)結(jié)果暗示了由算法產(chǎn)生的迭代值H（w）和ψ（w）在任何點(diǎn)處是連續(xù)可微的。

3 算法的收斂性

定理4.1 對(duì)于算法2.1，下面的結(jié)果成立：

(i)令｛wk｝?W是由算法2.1產(chǎn)生的迭代序列，則｛wk｝的任意聚點(diǎn)是問題(5)的穩(wěn)定點(diǎn)；

(ii)設(shè)w*是｛wk｝的一個(gè)聚點(diǎn)，若期望矩陣是P0矩陣，則由算法2.1得到的序列｛wk｝超線性收斂到w*。

證明：(i)反證法。設(shè)w˙∈W是序列｛wk｝的聚點(diǎn)，但不是問題(5)的穩(wěn)定點(diǎn)。不妨仍以｛wk｝表示收斂的子列，即有，對(duì)于J acobian矩陣H′（wk），存在一常數(shù)κ2＞0，使得對(duì)所有的k≥0，都有κ2。而由式子(7)和性質(zhì)3.2可知，對(duì)所有的k≥0，||βk||≤α。

因此，從算法2.1的步2可得

利用式(14)，有

因?yàn)椋鹷k｝和對(duì)τ，λ是有界的，且在任何緊集上是一致連續(xù)的，則對(duì)任意給定的ε＞0，存在一個(gè)常數(shù)，使得對(duì)所有的k≥0和λ∈［0，λ］，有下列式子成立：

因此，從式(18)可以進(jìn)一步得到，對(duì)所有的k≥0和λ∈［0，λ］，

對(duì)任意的wk和λ∈（0，1］,有

因?yàn)閣˙不是問題(5)的穩(wěn)定點(diǎn)，則存在一個(gè)常數(shù)κ4＞0，使得

令

由式(17)，(19)和(20)的關(guān)系以及事實(shí)γk≤1可知，對(duì)所有的k≥0和λ∈［0，λ′］，有

因此，由上式及算法2.1中步3所選取的線搜索可知，對(duì)所有的k≥0，有。而由不等式(11)和(20)可得，當(dāng)k→∞時(shí)，有

這里

其中

及

其中

因此，對(duì)角矩陣Di（x）是正定的。另一方面，是p0矩陣，即有的所有主子式均為非負(fù)數(shù)，所以所有主子式非負(fù)，從而是正定的，因而是非奇異的。而非奇異的矩陣是BD-正則的，進(jìn)而可通過文獻(xiàn)[14]中的定理4.2相同的方法證之。

4 結(jié)束語

本文考慮了一類特殊的隨機(jī)線性互補(bǔ)問題，通過使用光滑化的懲罰FB函數(shù)和松弛變量，將問題轉(zhuǎn)化為帶有非負(fù)約束的方程組，然后提出了求解這類問題的光滑投影牛頓算法，并證明了算法的全局收斂性。下一步我們將通過數(shù)值算例驗(yàn)證算法的有效性，并且要與已有的算法進(jìn)行比較。

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

［2］H.F.Chen.Stochastic approximation and its applications[M].Dordrecht：Kluwer Academic Publishers,2003.

［3］X.Chen and M.Fukushima.Expected residual minimization method for stochastic linear complementarity problems[J].Mathematics of Operations Research.2005,30：1022-1038.

［4］H.Fang,X.Chen and M.Fukushima.Stochastic R0matrix linear complementarity problems[J].SIAM Journal on Optimization.2007,18：482-506.

［5］X.Chen,C.Zhang and M.Fukushima.Robust solution of monotone stochastic linear complementarity problems[J].Mathematical Programming,2009,117：51-803.

［6］G.L.Zhou and L.Caccetta.Feasible semismooth Newton method for a class of stochastic linear complementarity problems[J].Journal of Optimization Theory and Applications.2008,139：379-392.

［7］C.Zhang and X.Chen.Smoothing projected gradient method and its application to stochastic linear complementarity problems[J].SIAM Journal on Optimization.2009,20：627-649.

［8］G.H.Lin,X.Chen and M.Fukushima.New restricted NCP function and their applications to stochastic NCP and stochastic MPEC[J].Optimization.2007,56：641-753.

［9］C.Zhang and X.Chen.Stochastic nonlinear complementarity problem and applications to traffic equilibrium under uncertainty[J].Journal of Optimization Theory and Applications.2008,137：277-295.

［10］B.T.Chen,X.Chen and C.Kanzow.A penalized Fischer-Burmeister NCPfunction[J].Mathematical Programming.2000,88：211-216.

［11］D.Sun,R.S.Womersley and H.Qi.A feasible semismooth asymptotically Newton method for mixed complementary problems[J].Mathematical Programming.2002,94：167-187.

［12］P.H.Calamai and J.J.More.Projected gradient methods for linear constrained problems[J].Mathematical Programming.1987,39：93-116.

［13］楊少君.一類隨機(jī)互補(bǔ)問題的算法研究[D].西安：西安電子科技大學(xué),2011.

［14］X.Tong and S.Zhou.A smoothing projected Newton-type method for semismooth equations with bound constraints [J].Journal of Industrial and Management Optimization.2005,1：235-250.