求解隨機線性互補問題的光滑牛頓投影算法

單錫泉

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

0 引言

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

其中M∈Rn×n是一個n×n實矩陣，q∈Rn是一個n維矢量。

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

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

下面我們引入幾個概念。

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

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

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

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

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

其中

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

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

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

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

1 光滑投影牛頓算法

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

算法2.1

步1：令

步2：(計算擾動方向)

如果線性系統(tǒng)

有解并且有

步3：(線搜索)

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

其中對任意的λ∈（0,1］，

參考文[11]，可得

其中

值得注意的是，因為W=R×Z，這暗示了算法中式(13)的投影計算只作用于任何點w=（μ，z）的分量z。

2 算法分析

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

(i)對任意的w∈W，

(ii)

是不增的。

下面的性質顯然成立。

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

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

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

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

證明：該性質可以通過歸納法來證。

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

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

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

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

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

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

其中第二個不等式是由性質3.2中βk的單調性決定的，最后一個不等式則來自于前一點wk處的假設。因而，可以得到

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

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

3 算法的收斂性

定理4.1 對于算法2.1，下面的結果成立：

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

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

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

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

利用式(14)，有

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

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

對任意的wk和λ∈（0，1］,有

因為w˙不是問題(5)的穩(wěn)定點，則存在一個常數(shù)κ4＞0，使得

令

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

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

這里

其中

及

其中

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

4 結束語

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

［1］韓繼業(yè)，修乃華，戚厚鐸.非線性互補理論與算法[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］楊少君.一類隨機互補問題的算法研究[D].西安：西安電子科技大學,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.