一類期望值模型的SAA法收斂性分析及應(yīng)用

胡伯霞，陳 源，李 龍

（衡陽師范學(xué)院 數(shù)學(xué)與計(jì)算科學(xué)系，湖南 衡陽 421002）

0 引 言

本文考慮如下隨機(jī)規(guī)劃問題：

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

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

Xu和Zhang［5］考慮了一類隨機(jī)規(guī)劃模型：

Liu和Xu［6］還考慮了一類具有隨機(jī)二階占優(yōu)約束的隨機(jī)規(guī)劃問題：

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

稱（2）為SAA問題，而稱（1）為原問題。SAA問題的主要優(yōu)點(diǎn)是無需計(jì)算期望值。

1 精確罰方法

假設(shè)已獲得（2）的一個(gè)最優(yōu)解，記為xN，我們需要分析隨著樣本規(guī)模N的增大，xN的收斂性。顯然直接從（2）分析將會(huì)非常復(fù)雜，因?yàn)椋?）的約束個(gè)數(shù)也會(huì)隨著N的增大而增大，為了避免這一問題，我們把（1）和（2）運(yùn)用精確罰技術(shù)將問題歸結(jié)為在約束確定的情況下，分析目標(biāo)函數(shù)的逼近性質(zhì)上來。記

對(duì)應(yīng)于原問題（1）的精確罰規(guī)劃為：

其中λ是罰參數(shù)。在適當(dāng)?shù)募僭O(shè)下（1）與（3）的最優(yōu)解等價(jià)。

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

類似于文獻(xiàn)［5］的證明，我們有下面的最優(yōu)解等價(jià)性定理：

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

對(duì)應(yīng)于SAA問題（2）的精確罰規(guī)劃為：

其中λN是罰參數(shù)。

對(duì)于（2）與（4）的最優(yōu)解有如下等價(jià)性定理：

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

2 收斂性結(jié)果

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

定義下面兩個(gè)矩量母函數(shù)：

引理1【逐點(diǎn)指數(shù)收斂】若假設(shè)2成立，則對(duì)任意x∈X和小正數(shù)ε＞0，只要N充分大則有

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

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

證明：首先有：

接下來，估計(jì)

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

聯(lián)合上面五式，有

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

引理2 考慮一般優(yōu)化問題

這里p：RN→R，X?RN，和一個(gè)擾動(dòng)規(guī)劃問題

根據(jù)上述引理仿文獻(xiàn)［5］的證明可得如下收斂性結(jié)果。

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

3 數(shù)值實(shí)驗(yàn)

例 考慮如下期望值優(yōu)化問題：

圖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