劉晉紋，韓有攀

（西安工程大學(xué)理學(xué)院，西安 710600）

現(xiàn)實(shí)生活中，一些事件雖然發(fā)生的概率很小，但是一旦發(fā)生就會產(chǎn)生很大的影響，例如金融危機(jī)、自然災(zāi)害等.而大偏差理論為計算稀有事件的概率提供了一個很好的方法.因此作為概率論極限理論重要分支的大偏差理論，受到了越來越多學(xué)者的廣泛重視.大偏差理論最早起源于19世紀(jì)70年代的Boltzmann理論，隨后得到不斷發(fā)展，其中最有影響力的人物是2007年度“阿貝爾獎”獲得者、美籍印度數(shù)學(xué)家、紐約大學(xué)教授Varadhan，他為概率論研究方面作出了突出貢獻(xiàn)，特別是他的大偏差理論成為現(xiàn)代概率論的基石.他與Stroock關(guān)于擴(kuò)散過程的研究成果以及與Donsker在大偏差方面的合作研究成果尤為出色.目前的大偏差理論體系較為豐富，重要性結(jié)論有：有限維、獨(dú)立同分布隨機(jī)變量的大偏差原理，即Cramér定理［1］；有限維、非獨(dú)立同分布隨機(jī)變量的大偏差原理，即G?rtner-Ellis定理［2］；測度空間的大偏差原理，即Sanov定理［3］；函數(shù)空間的大偏差原理，即Schilder定理［4］等.

隨機(jī)規(guī)劃所研究的對象是含有隨機(jī)因素的數(shù)學(xué)規(guī)劃問題，是運(yùn)籌學(xué)的一個重要分支.最早提出隨機(jī)規(guī)劃問題的是線性規(guī)劃創(chuàng)始人之一Dantzig，他在航班最優(yōu)次數(shù)的問題中發(fā)現(xiàn)客流量是個隨機(jī)變量，最先提出了二階段有補(bǔ)償隨機(jī)規(guī)劃問題.目前關(guān)于隨機(jī)規(guī)劃的成果很多，可參看著作［5-9］和綜述論文［10-14］等.用樣本均值逼近（SAA）方法去解決隨機(jī)規(guī)劃問題是一種十分有效的方法，其基本思想是用樣本均值來估計目標(biāo)函數(shù)的期望函數(shù).2016年，Yang等［15］采用CVaR逼近將模型等價轉(zhuǎn)化為凸優(yōu)化模型，然后運(yùn)用樣本平均逼近方法進(jìn)行求解，證明了算法的收斂性，數(shù)值結(jié)果表明了模型和算法的有效性；2017年，Pour等［16］應(yīng)用樣本平均近似技術(shù)來解決標(biāo)準(zhǔn)人員分配問題的一個實(shí)際推廣問題；2019年，Yang等［17］提出了一種基于SAA的不可行內(nèi)點(diǎn)算法的隨機(jī)互補(bǔ)問題，研究了算法的收斂性和計算復(fù)雜度；2008年，Homem-de-Mello［18］曾結(jié)合LHS抽樣和擬蒙特卡羅方法研究了非獨(dú)立同分布樣本下原問題與樣本平均逼近問題最優(yōu)值、最優(yōu)解的收斂性.

利用大偏差原理來研究隨機(jī)規(guī)劃問題的收斂性也取得了一系列成果.假設(shè)樣本為獨(dú)立同分布（independently identically distribution，i.i.d）時對隨機(jī)規(guī)劃模型的研究：1995年，Kaniovski等［19］利用大偏差理論導(dǎo)出了隨機(jī)優(yōu)化問題近似解收斂的幾個指數(shù)界，基本結(jié)果表明，用經(jīng)驗分布代替原分布得到的解為求解隨機(jī)規(guī)劃問題提供了有效的工具；2000年，Dai等［20］考慮了兩階段隨機(jī)規(guī)劃問題，用其經(jīng)驗平均值代替要優(yōu)化的性能函數(shù)，利用大偏差技術(shù)建立了經(jīng)驗最優(yōu)與性能函數(shù)最優(yōu)的偏差概率的指數(shù)收斂性；2008年，Shapiro［21］研究了i.i.d樣本下極大極小隨機(jī)優(yōu)化問題與其樣本均值逼近問題最優(yōu)值的漸進(jìn)性并舉例討論了風(fēng)險規(guī)避隨機(jī)規(guī)劃SAA的漸進(jìn)性半偏差風(fēng)險度量，隨后利用大偏差原理證明最優(yōu)值一致指數(shù)收斂性；Shapiro和Xu［22］研究了帶有均衡約束的隨機(jī)規(guī)劃問題的最優(yōu)解集和最優(yōu)值的收斂性，且證明了原問題與其SAA問題的一致指數(shù)收斂性；2011年，Ralph和Xu［23］探討了針對一系列僅僅是上半連續(xù)和從上部逐點(diǎn)Calm的隨機(jī)函數(shù)的一致指數(shù)速率收斂，并且應(yīng)用于兩階段隨機(jī)優(yōu)化問題的穩(wěn)定性分析中.假設(shè)樣本為非i.i.d時對隨機(jī)規(guī)劃模型的研究：2010年，Xu［24］將i.i.d樣本推廣到一般情況下，證明了通常的隨機(jī)規(guī)劃問題與其SAA問題的一致指數(shù)速率收斂；2013年，孫海琳［25］在Xu的基礎(chǔ)上將一致全局H?lder連續(xù)條件弱化為局部H?lder連續(xù)，研究了一般樣本下隨機(jī)規(guī)劃問題與其SAA問題的一致指數(shù)速率收斂.

在此基礎(chǔ)上，當(dāng)樣本為非獨(dú)立同分布時，我們研究通常的隨機(jī)優(yōu)化問題和極小極大隨機(jī)優(yōu)化問題最優(yōu)值的指數(shù)收斂性.

1 預(yù)備知識

考慮如下隨機(jī)優(yōu)化問題：

其中X是Rn中的非空閉集，ξ是一個概率分布支撐集為D∈Rd的隨機(jī)向量，F(xiàn)(x,ξ):X×D→R是Caratheodóry函數(shù)，即集合X上連續(xù)且在D上可測.期望函數(shù)f(x)是確定的并且在所有x∈X的值是有限的.

取一組隨機(jī)向量ξ的樣本ξ1,ξ2,…,ξN對此函數(shù)進(jìn)行估計.得到SAA問題：

由文獻(xiàn)［26］中的定理2可知以下引理.

證明見文獻(xiàn)［27］中的第5章.

定義1 給定兩個集合A，B，則A與B之間的偏差表示為

若A是空的，則dist(x,A)=+∞，因此若B是空的，則dist(A,B)=+∞.

2 隨機(jī)規(guī)劃問題

引理3 若存在緊集C?RN使得：

1）問題（1.1）的最優(yōu)解集S*非空且S*?C.

2）f(x)是有限值函數(shù)且在C上連續(xù).

為研究隨機(jī)規(guī)劃問題的指數(shù)收斂性，我們做以下假設(shè)：

（A-1）存在一個可測函數(shù)L:D→R+使得E[L(ξ)2]有限且

對任意的x，x′∈X，a.e.ξ∈D成立.

注：這個條件是研究隨機(jī)規(guī)劃收斂性的一個基本假設(shè)，如文獻(xiàn)［21，24，28］.當(dāng)F(x,ξ)為線性隨機(jī)規(guī)劃或二次隨機(jī)規(guī)劃問題的目標(biāo)函數(shù)時，這個條件成立.

其極限

在0點(diǎn)的一個鄰域內(nèi)所有的t是有限的.

（A-3）隨機(jī)變量L(ξ)的矩母函數(shù)

在0點(diǎn)的一個鄰域內(nèi)的所有的t是有限的.

注：（A-1）在給定的ξ下，目標(biāo)函數(shù)在X上是一致Lipschitz連續(xù)的.（A-2）和（A-3）是在研究隨機(jī)規(guī)劃問題收斂性標(biāo)準(zhǔn)假設(shè)，如文獻(xiàn)［18-21］.

定理1 假設(shè)條件（A-1）～（A-3）成立并且樣本非i.i.d，則對任意ε＞0，存在正實(shí)數(shù)β=β(ε)與N無關(guān)，使得滿足下列不等式：

證明 由G?rtner-Ellis大偏差定理可知，對任意的ε＞0

類似可得

因此

且由（A-2）可知Ix(ε)，Ix(-ε)對任意的ε都是正的.

由（3）式兩邊同時取期望可得

類似可得

由（A-1）可知L′=E[ ]

L(ξ)是有限的，所以由G?rtner-Ellis大偏差可知，對任意的L?＞L′，存在正常數(shù)λ使得

接著，我們來估計最優(yōu)值之間的關(guān)系，即有

3 極小極大隨機(jī)優(yōu)化問題

本節(jié)考慮下面極小極大隨機(jī)優(yōu)化問題：

其中F(x,y,ξ):X×Y×D→R，ξ=ξ(w)是一個概率分布支撐集為D∈Rd的隨機(jī)向量.相應(yīng)的SAA問題為：

（B-1）F(x,y,ξ)是Caratheodóry函數(shù).

（B-2）集合X,Y是非空的并且是緊的.

（B-3）集合X,Y是凸的，函數(shù)F(·,·,ξ)在X×Y是凸-凹的，a.e.ξ∈D，即函數(shù)F(·,y,ξ)關(guān)于X為凸函數(shù)，函數(shù)F(x,·,ξ)關(guān)于Y上為凹函數(shù).

（B-4）期望值函數(shù)E[F(x,y,ξ)2]對于任意的(x,y)∈X×Y是有限的，并且存在一個可測函數(shù)L:D→R+使得對于所有(x,y)，(x′,y′)∈X×Y，E[L(ξ)2]有限且滿足不等式

a.e.ξ∈D成立.

證明 見文獻(xiàn)［28，定理2.10］.

定理2 已知條件（B-2）～（B-4）成立，則 |φ(x)-φ(x′)|≤L′‖x-x′‖，其中L′=E[L(ξ)].

證明 由（8）式兩邊取期望可得

|f(x,y)-f(x′,y′)|≤L′(‖x-x′‖+‖y-y′‖)，L′=E[L(ξ)].

設(shè)y是φ(x)的最優(yōu)解，y′是φ(x′)的最優(yōu)解，即

φ(x)=f(x,y)，φ(x′)=f(x′,y′)，

則

|φ(x)-φ(x′)|= |f(x,y)-f(x′,y′)|≤ |f(x,y)-f(x′,y)|≤L′‖x-x′‖.

為了建立極小極大隨機(jī)優(yōu)化問題最優(yōu)值之間的一致指數(shù)收斂性，還需以下條件：

其極限

在0的一個鄰域內(nèi)的所有的t是有限的.

（B-6）隨機(jī)變量L(ξ)的矩母函數(shù)

在0點(diǎn)的一個鄰域內(nèi)的所有的t是有限的.

注：條件（B-5）和（B-6）是在研究隨機(jī)規(guī)劃問題的指數(shù)收斂性時所做出的的假設(shè)，如文獻(xiàn)［20，21-23］等.當(dāng)隨機(jī)變量為正態(tài)或亞高斯（sub-Gaussian）隨機(jī)變量，我們可以有如下估計：

由此，我們可以推出（B-5）和（B-6）說成立的.

在上述假設(shè)條件下，我們給出以下定理.

定理3 假設(shè)條件（B-1）～（B-6）成立并且樣本非i.i.d，則對任意ε＞0，存在正實(shí)數(shù)β=β(ε)與N無關(guān)，使得滿足下列不等式：

證明 取x*∈Sx，使得

由（B-6）可知L′=E[L(ξ)]是有限的，所以由G?rtner-Ellis大偏差定理可知，對任意的L″＞L′，存在正常數(shù)λ使

又因為

由（12）式可得

類似定理1可知

因此

因此

得證.

4 結(jié)論

在樣本非獨(dú)立同分布時，對隨機(jī)規(guī)劃問題和極小極大隨機(jī)規(guī)劃問題最優(yōu)值的指數(shù)收斂進(jìn)行研究.當(dāng)隨機(jī)規(guī)劃問題目標(biāo)函數(shù)滿足全局Lipschitz條件時，利用G?rtner-Ellis大偏差定理建立了兩類隨機(jī)規(guī)劃問題最優(yōu)值一致指數(shù)收斂的結(jié)論.這些結(jié)論不僅豐富了隨機(jī)規(guī)劃理論的內(nèi)容，還為求解隨機(jī)規(guī)劃問題的算法奠定了理論基礎(chǔ).