王歡，張杰，洪志曼

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

求解隨機二階錐線性互補問題的一種光滑化SAA方法

王歡，張杰*，洪志曼

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

研究了隨機二階錐線性互補問題的收斂性問題并基于收斂性分析進(jìn)行了數(shù)值實驗.文章利用Chen-Harker-Kanzow-Smale（CHKS）光滑函數(shù)和SAA方法，提出了求解隨機二階錐線性互補問題的光滑化SAA方法.基于P性質(zhì)，建立了收斂性分析，然后通過數(shù)值實驗驗證了算法的有效性.

隨機二階錐線性互補問題；CHKS光滑函數(shù)；Cartesian P性質(zhì)

考慮如下隨機線性錐互補問題：尋找到一個向量x∈K，使得：

其中F（x）=E［M（ξ（ω））］x+E［q（ξ（ω））］，M（·）∶Rm→Rn×n，q（·）∶Rm→Rn是隨機映射，ξ∶Ω→Ξ?Rm是定義在概率空間（Ω，F(xiàn)，P）上的隨機變量，E表示數(shù)學(xué)期望，K是Rn中的閉凸錐，表示為

是二階錐（SOC），也稱為冰激凌錐，定義為

其中‖·‖表示歐幾里得范數(shù).如果ni=1，則Kni是非負(fù)實數(shù)集R+.在本文中，假設(shè)M（ξ（ω）），q（ξ（ω））滿足

由于問題（1）含有隨機變量，稱問題（1）隨機二階錐線性互補問題（SSOCLCP）這個模型屬于隨機均衡模型，在經(jīng)濟、力學(xué)、控制領(lǐng)域等中有重要的應(yīng)用，尤其是當(dāng)ni=1，i=1，2，…，m時，這個問題退化為如下的隨機線性互補問題（SLCP）：尋找x∈Rn使得Gürkan、?zge和Robinson［1］在隨機變分不等式的框架下提出了樣本路徑優(yōu)化（SPO）方法求解SLCP，并通過數(shù)值試驗驗證了此方法的收斂性.Xu［2］提出了樣本均值近似（SAA）方法求解SLCP問題，研究了樣本平均近似問題的解的存在性和收斂性，并應(yīng)用到求解帶有隨機約束的隨機規(guī)劃問題中.Zhang等［3］提出了一類光滑化SAA方法求解SLCP問題.如果期望值可以準(zhǔn)確得到，則可用求解確定性二階錐互補問題的方法如內(nèi)點法［4-5］，光滑化牛頓法［6］等進(jìn)行求解.但在實際問題中準(zhǔn)確得到期望值的代價很大，很多學(xué)者建議采用SAA方法來求解，如Xu［2］，Wang［7］等.SAA方法的主要思想是產(chǎn)生一組獨立同分布樣本ξ1，…，ξn構(gòu)造樣本均值近似期望值.本文提出一種求解SSOCLCP的方法，這種方法的基本思想是首先利用SAA方法和光滑化函數(shù)，把SSOCLCP轉(zhuǎn)化為光滑的無約束優(yōu)化問題，然后通過求解一系列的光滑優(yōu)化問題來得到SSOCLCP的解.利用若當(dāng)代數(shù)和Car?tesian P性質(zhì)對這種方法的收斂性進(jìn)行了分析，并分別利用matlab工具箱和非精確牛頓法進(jìn)行了數(shù)值實驗，驗證了方法的有效性.

為了建立方法的收斂性分析，首先介紹一下歐幾里得若當(dāng)代數(shù)［8］.歐幾里得若當(dāng)代數(shù)（H0，°，〈·，·〉）是定義在實數(shù)域上的有限維內(nèi)積空間，（x，s）→x° s∶H0×H0→H0是雙線性映射，并滿足下列幾個條件：

其中〈·，·〉表示歐幾里得內(nèi)積.此時記x2?x°x，x+s為通常的向量加法，則可知對所有的x∈Rn，x2∈K，而且如果x∈K，則存在K中的唯一向量使得

1　光滑化SAA問題構(gòu)造

定義WL是問題（2）的解.是問題（3）的解且W0是SSOCLCP的解.為了確保解的近似程度比較好，這里考慮樣本容量充分大時的情形.

2　收斂性分析

3　數(shù)值實驗

結(jié)合上面的收斂性分析給出兩個例子，并分別用Matlab中的fminsearch函數(shù)和非精確牛頓法對光滑化的SAA問題進(jìn)行求解，下面給出非精確牛頓法求解

如果上述系統(tǒng)不兼容或者下面情況

ξ=（ξ（1ω），ξ（2ω），ξ（3ω）），ξ（1ω），ξ（2ω），ξ（3ω）是獨立隨機變量，并且ξ（1ω）是服從EXP（λ=2.5）的指數(shù)分布，ξ（2ω）是服從［0，1］的均勻分布，ξ（3ω）是服從N（μ，σ2）的正態(tài)分布，μ=0.5，σ=0.1.對于上述問題在Mat?lab中采用fminsearch函數(shù)進(jìn)行求并取光滑化參數(shù)t= 0.01，并用N，，Obj，liter分別表示光滑SAA問題的樣本量，最優(yōu)解集，最優(yōu)值及迭代次數(shù).計算結(jié)果見表1.

表1　例1的計算結(jié)果Tab.1Calculation results of case 1

通過簡單計算可知這個問題有唯一解s*=（1.0000，1.0000）T.表1的實驗結(jié)果表明本文的方法可以得到問題的一個很好的近似解.

例2考慮隨機二階錐線性互補問題（1），其中

q（ξ（ω））=（-4ξ3（ω），-1，0，-5ξ1（ω）），ξ=（ξ1（ω），ξ2（ω），ξ3（ω）），ξ1（ω），ξ2（ω），ξ3（ω）是獨立隨機變量，ξ1（ω）是服從EXP（λ=2.5）的指數(shù)分布，ξ2（ω）是服從［0，1］的均勻分布且ξ3（ω）是服從N（μ，σ2）的正態(tài)分布，μ=0.5，σ=0.1.對于上述問題，分別用Matlab中的fminsearch函數(shù)和非精確牛頓法LSINA來進(jìn)行求解，實驗中取t=0.01，計算結(jié)果見表2.

通過簡單計算可知這個問題有唯一解s*=（2.0000，1.0000，0.0000，1.0000）T.表2的實驗結(jié)果表明本方法可以得到問題的一個很好的近似解.通過表2，發(fā)現(xiàn)在采用fminsearch函數(shù)所得的解更精確，但非精確牛頓方法迭代次數(shù)相對較少.

表2　例2的計算結(jié)果Tab.2Calculation results of case 2

4　結(jié)論

本文提出了一個求解隨機二階錐線性互補問題的光滑化樣本均值近似方法，建立了算法的收斂性理論并通過數(shù)值實驗驗證了方法的有效性.

［1］Gurkan G，Ozge A，Robinson S.Sample-path solution of stochastic variational Inequalities［J］.Mathematical Program?ming，1999，84：313-333.

［2］Xu H.Sample average approximation methods for a class of stochastic variational inequality problems［J］.Asia-Pacific Journal of Operational Research，2010，27：103-119.

［3］Zhang J.A class of smoothing SAA methods for a stochastic linear complementarity problem［J］.Numerical algebra，Control and optimization，2012，2：145-156.

［4］Monteiro R，Tsuchiya T.Polynomial convergence of pri?mal-dual algorithms for the second-order cone programs based on the MZ-family of directions［J］.Mathematical Programming，2000，88：61-83.

［5］Chen J，Tseng P.An unconstrained smooth minimization re?formulation of the second-order cone complementarity problem［J］.Mathematical Programming，2005，104：293-327.

［6］Pan S，Chen J.A regularization method for the second-or?der cone complement-arity problem with the Cartesian P0-property［J］.Nonlinear Analysis，2009，70：1475-1491.

［7］Wang M，Lin G，Gao Y，et al.Sample average approxima?tion method for a class of stochastic variational inequality problems［J］.Systems Science and Complexity，2001，24：1143-1153.

［8］Faraut J，Korabyi A.Analysis on symmetric cones［M］.Ox?ford：Clarendon Press，1994.

［9］Chen C，Mangasarian O.A class of smoothing functions for nonlinear and mixedcomplementarity problems［J］.Compu?tational Optimization and Applications，1996，5：97-138.

［10］Fukushima M，Luo Z，Tseng P.Smoothing functions for second-order-cone complementarity problems［J］.SIAM J Optim，2002，12（2）：436-460.

［11］Facchinei F，F(xiàn)ischer A，Kanzow C.Inexact Newton meth?ods for semismooth equations with applications to variation?al inequality problems［J］.Di Pillo G，Giannessi F.Nonlin?ear Optimization and Applications.New York：Plenum Press，1996：125-139.

責(zé)任編輯：劉紅

A Smoothing SAA Method for a Stochastic Second-order Cone Linear Complementarity Problem

WANG Huan，ZHANG Jie*，HONG Zhiman
（School of Mathematics，Liaoning Normal University，Dalian 116029，China）

In this paper，we studied the convergence of the random second-order cone linear complementary problems and experiments were carried out based on convergence analysis.Based on the Chen-Harker-Kanzow-Smale（CHKS）smooth?ing function and sample average approximation（SAA）method，a smoothing SAA method was proposed for solving a stochas?tic second-order cone linear complementarity problem.Convergence analysis was established by the P property.At last，the efficiency of the method was verified by some numerical tests.

stochastic second-order cone linear complementarity problem；CHKS smoothing function；Cartesian P property

O 221

A

1674-4942（2015）04-0355-04

2015-09-17

國家自然科學(xué)基金項目（11201210）；遼寧省高等學(xué)校杰出青年學(xué)者成長計劃（LJQ2015059）