王博, 初麗

(1. 福州大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院，福建 福州 350108； 2. 福建工程學(xué)院計算機科學(xué)與數(shù)學(xué)學(xué)院，福建 福州 350118)

0 引言

本研究分析一類較為一般的含有二階錐互補約束(SSOCMPCC)的隨機優(yōu)化模型:

min{E[f(z,ξ(ω))]|KmE[G(z,ξ(ω))]⊥E[H(z,ξ(ω))]∈Km}

SSOCMPCC模型是有實際意義的. 其中隨機變量的引入可以源于數(shù)據(jù)的誤差和未來的不確定性； 互補約束可以來自于逆問題[1-2]或雙層規(guī)劃問題[3]的轉(zhuǎn)化.

SSOCMPCC模型在所有二階錐維數(shù)都為1(即m1=m2=…=mn=1)時，退化為隨機互補模型(SMPCC):

min{E[f(z,ξ(ω))]|0≤E[G(z,ξ)]⊥E[H(z,ξ)]≥0}

關(guān)于相對簡單的隨機互補模型的理論研究和求解方法，可參考相關(guān)文獻[4-7]. 需要指出，SSOCMPCC模型并非SMPCC模型的平凡推廣. SSOCMPCC模型可行集合不再有多面體性質(zhì)，其一階必要性條件更為復(fù)雜. 穩(wěn)定性理論可參考Zhang等[8]、 Liang等[9]和Ye等[3]的工作. 需要注意關(guān)于C穩(wěn)定點的定義是有歧義的，具體可以參見Chu等[10]的工作.

本研究希望構(gòu)造一個求解SSOCMPCC模型的不依賴具體光滑化函數(shù)的光滑化SAA方法的一般框架. 該框架的構(gòu)造對SSOCMPCC模型有效算法的研究具有積極作用.

假設(shè)E[f(z,ξ(ω))]、E[G(z,ξ(ω))]和E[H(z,ξ(ω))]對所有的z∈Rm都是有定義的.ξ(ω)簡記為ξ.對應(yīng)于錐Km，映射G(z,ξ)和H(z,ξ)可以進行如下分塊，即：

假設(shè)可以抽樣得到隨機向量ξ的N個獨立同分布的樣本ξ1,ξ2, …,ξN.由此可構(gòu)造SSOCMPCC模型的近似問題:

(1)

問題(1)依賴于ε的解z(ε)是隨機變量.期望當(dāng)ε→0時，z(ε)在某種概率意義下能接近SSOCMPCC模型的解.若Γε(·)為CHKS 光滑化函數(shù)時，由文獻[10]知，上述期望是成立的.后續(xù)討論將指出較一般的一類光滑化函數(shù)也有類似的性質(zhì).

1 預(yù)備知識

給定x=(x1;x2)∈Rt，在二階錐Kt意義下的譜分解為：

x=λ1(x)c1(x)+λ2(x)c2(x)

(2)

其中:i=1, 2,λi(x)和ci(x)分別為x的特征值與特征向量，即：

(3)

SK(x)=[λ1(x)]+c1(x)+[λ2(x)]+c2(x)

SSOCMPCC模型的拉格朗日函數(shù)可定義為：

計算可得其關(guān)于z的梯度為：

為了建立收斂性理論，還需要如下約束規(guī)范成立：

(4)

(5)

(6)

(7)

注意C穩(wěn)定性強于弱穩(wěn)定性[10]. 穩(wěn)定性定義中需要計算投影算子Sj的B次微分的具體形式. 此處可利用Zhang等[8]文獻中的引理2.1. 而廣義雅克比可由公式?Sj=conv?BSj得到.

接下來的討論需要假設(shè)隨機向量ξ的樣本ξ1, …,ξN是獨立同分布的，且滿足下述條件.

條件1映射f(·,ξ)、G(·,ξ)和H(·,ξ)在Rm上對幾乎所有的ξ∈Ξ都二階連續(xù)可微.

由條件1和條件2可知，E[f(z,ξ)]、E[G(z,ξ)]和E[H(z,ξ)]是二階連續(xù)可微的(參見文獻[4]定理7.44).根據(jù)大數(shù)定律，如下引理成立(參見文獻[4]定理 7.48).

2 SSOCMPCC問題的光滑化SAA方法

求解問題(1)時，需要選擇適當(dāng)?shù)墓饣成洇＆?·). 本研究中光滑化映射的構(gòu)建基于 Fukushima等[13]研究的如下一類光滑化函數(shù).

滿足條件3的光滑化函數(shù)具有非常良好的性質(zhì).

引理3設(shè)ψε(·)為如上定義的映射，則有：Jψε(x)是正定的，且I-Jψε(x)可逆.

接下來討論收斂性. 下述結(jié)果是文獻[10]中引理3.2的推廣.

證明 給定正數(shù)εN和任意固定向量ω=(ω1; …;ωJ)∈Rm，設(shè)其譜分解為：

可以按下述方式構(gòu)造(αN,βN)：

(8)

(9)

上述命題證明方式類似于文獻[10]中的命題1. 受篇幅所限，具體證明過程略去. 此結(jié)果總結(jié)了SSOCMPCC模型和問題(1)之間可行集的關(guān)系. 接下來的定理描述了其解之間的收斂性關(guān)系.

SSOCMPCC模型可以通過序列問題(1)近似. 具體的近似關(guān)系，可由如下結(jié)論刻畫.

上述結(jié)論可以利用專著[14]中的定理7.31簡單得到，此處不再贅述.

實踐中最優(yōu)解幾乎無法取得，接下來的討論總結(jié)了SSOCMPCC模型與問題(1)穩(wěn)定點之間的關(guān)系. 較之于最優(yōu)解間的關(guān)系，此類似結(jié)論更實用.

證明 KKT對(zN,σN)滿足：

(10)

設(shè)

則簡單驗證可得：

(11)

由上述定理的證明過程稍加修改，不難證明在更強的假設(shè)下有如下結(jié)論成立：

基于上述分析，可得求解SSOCMPCC模型的一般光滑化SAA算法框架如下：

算法 一般光滑化SAA算法框架取N為充分大的整數(shù), g (·)為適當(dāng)?shù)墓饣瘮?shù). 步驟1 令εN=10-N. 取隨機向量ξ的N個獨立同分布樣本, 記為ξi, i=1, 2, …, N. 步驟2 求解SAA子問題min{f^N(z)Φ^εN(z)=0}得到穩(wěn)定點zN. 步驟3 若滿足終止條件則終止迭代; 否則增大N并轉(zhuǎn)步1.

實際執(zhí)行算法時，需要提前確定終止條件. 注意由于本研究討論的是數(shù)學(xué)期望沒有顯示表達式的情況，確定已得到的向量是否是解是幾乎不可能的. 具體的終止條件可取兩次迭代之間的差別足夠小，也可以在N充分大時終止.

3 應(yīng)用

本研究提出的一般性框架可以視為基于特殊光滑化函數(shù)的光滑化方法的推廣. 光滑化函數(shù)可分別取CHKS函數(shù)[15-17]和S形函數(shù)1/(1+e-x)的積分:

(12)

(13)

根據(jù)本研究的結(jié)論，易得如下收斂性結(jié)論：

光滑化函數(shù)取為式(12)時，該結(jié)論和文獻[10]中給出的一致. 若加強假設(shè)條件，則可以保證收斂到更強的M穩(wěn)定點[10]. 光滑化函數(shù)取為式(13)時，得到的具體算法較為新穎. 上述結(jié)論保證了算法基本的收斂性.

4 結(jié)論

提出一種求解SSOCMPCC問題的一般光滑化SAA方法框架. 本框架中，只要選取的光滑化函數(shù)滿足Fukushima等[13]提出的條件，在適當(dāng)?shù)募僭O(shè)下，就可以保證子問題的穩(wěn)定點以概率1收斂到SSOCMPCC的C穩(wěn)定點. 本研究給出了兩個具體的光滑化函數(shù)并討論了對應(yīng)的收斂性結(jié)論，由此驗證框架的實用性.