一類期望值模型的SAA法收斂性分析及應用

胡伯霞，陳 源，李 龍

（衡陽師范學院 數學與計算科學系，湖南 衡陽 421002）

0 引 言

本文考慮如下隨機規劃問題：

這里X是一非空凸集，x是決策變量，ξ：Ω→Ξ?Rk是定義在概率空間（Ω，F，P）上的隨機變量，E［·］是期望值算子，f：Rn×Rk→R，g：Rn×Rk→Rm是局部Lipschitz連續函數。

在許多情形下，對于給定的決策x，精確求解（1）中的期望值或不可能或代價太高，為了克服這一困難，我們可以考慮運用眾所周知的采樣平均近似SAA法來求解［1－3］。Wang和Ahmed［4］考慮了一類隨機規劃模型：

Xu和Zhang［5］考慮了一類隨機規劃模型：

Liu和Xu［6］還考慮了一類具有隨機二階占優約束的隨機規劃問題：

受上述方法的啟發，本文研究（1）的數值求解方法。設通過計算模擬或從歷史數據已獲得ξ的采樣ξ1，ξ2，…，ξN，考慮（1）的如下采樣平均近似問題：

稱（2）為SAA問題，而稱（1）為原問題。SAA問題的主要優點是無需計算期望值。

1 精確罰方法

假設已獲得（2）的一個最優解，記為xN，我們需要分析隨著樣本規模N的增大，xN的收斂性。顯然直接從（2）分析將會非常復雜，因為（2）的約束個數也會隨著N的增大而增大，為了避免這一問題，我們把（1）和（2）運用精確罰技術將問題歸結為在約束確定的情況下，分析目標函數的逼近性質上來。記

對應于原問題（1）的精確罰規劃為：

其中λ是罰參數。在適當的假設下（1）與（3）的最優解等價。

假設1.f（x，ξ）和g（x，ξ）關于x是局部Lipschitz連續，且它們的模由一可測正函數κ（ξ）界定。

類似于文獻［5］的證明，我們有下面的最優解等價性定理：

定理1.假設原問題（1）滿足Slater條件且X是緊集，若假設1成立，則存在一個正數，使得對任意λ＞，（1）與（3）的最優解集相同。

對應于SAA問題（2）的精確罰規劃為：

其中λN是罰參數。

對于（2）與（4）的最優解有如下等價性定理：

定理2.若定理1的假設成立，那么存在正數N＊和λ＊使得對任意N＞N＊和λN＞λ＊，（2）與（4）的最優解集w.p.1一致。

2 收斂性結果

本小節主要研究FN（x）→F（x）的一致指數收斂性，同時這也得出了xN→x＊∈X＊，N→∞，而X＊為原問題（1）或SAA問題（3）的最優解集。另外從計算方面來講，也需要在給定誤差界d（xN，X＊）的情況下估計采樣樣本數N。在采樣為獨立同分布（iid）或非獨立同分布（non－iid）的情況下，應用大偏差理論（LD）分析統計量的指數收斂性，請參看文獻［2］［3］［7］。這里假設采樣為廣義采樣。

定義下面兩個矩量母函數：

引理1【逐點指數收斂】若假設2成立，則對任意x∈X和小正數ε＞0，只要N充分大則有

在上述假設和引理下，有下面的一致指數收斂性定理。

定理3.若假設1，2，3成立，且λN→λ＊，N→∞。則?ε＞0，存在與N無關的正常數c（ε）和β（ε），使得

證明：首先有：

接下來，估計

由文獻［8］，存在cl（ε），βl（ε），l＝1，2，3，使得

聯合上面五式，有

其中c（ε）＝c1（ε）＋c2（ε）＋c3（ε），β（ε）＝min｛β1（ε），β2（ε），β3（ε）｝。得證。

引理2 考慮一般優化問題

這里p：RN→R，X?RN，和一個擾動規劃問題

根據上述引理仿文獻［5］的證明可得如下收斂性結果。

定理4.假設如定理3.若x｛N｝是SAA問題的最優解序列，而X＊是原問題的最優解集，則對任意ε＞0，存在正常數c（ε）和β（ε），使得

3 數值實驗

例 考慮如下期望值優化問題：

圖1 SAA問題的收斂性（σ＝0.5）

［1］S M ROBINSON.Analysis of sample－path optimization［J］.Math.Oper.Res.，1996，21：513－528.

［2］A DEMBO，O ZEITOUNI.Large Deviations Techniques and Applications［M］.New York：Springer－Verlag，1998.

［3］A SHAPIRO.Monte Carlo sampling methods，in：A.Rusczynski and A.Shapiro（editors），Stochastic Programming［M］.Handbooks in OR ＆MS，Amsterdam：North－Holland Publishing Company，2003.

［4］W WANG，S AHMED.Sample average approximation of expected value constrained stochastic programs［J］.Oper.Res.Letters，2008，36：515－519.

［5］H XU，D ZHANG.Monte Carlo Methods for Mean－Risk Optimization and Portfolio Selection［EB／OL］.［2010－6－3］.Comput.Manag.Sci.，http：／／www.2010，DOI 10.1007／s10287－010－0123－6.

［6］Y LIU，H XU.Stability and Sensitivity Analysis of Stochastic Programs with Second Order Dominance Constraints［EB／OL］.［2010－6－17］.http：／／eprints.soton.ac.uk／182199／1／Liu－Xu－17－June－2010.pdf

［7］A SHAPIRO and H XU.Stochastic mathematical programs with equilibrium constraints，modeling and sample average approximation［J］.Optimization，2008，57：395－418.

［8］H XU.Uniform exponential convergence of sample average random functions under general sampling with applications in stochastic programming［J］.J.Math.Anal.Appl.，2010，368：692－710