隨機(jī)二階錐互補(bǔ)約束優(yōu)化模型的一般光滑化SAA方法

王博, 初麗

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

0 引言

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

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

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

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

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

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

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

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

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

(1)

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

1 預(yù)備知識(shí)

給定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ù)可定義為：

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

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

(4)

(5)

(6)

(7)

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

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

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

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

2 SSOCMPCC問(wèn)題的光滑化SAA方法

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

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

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

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

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

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

(8)

(9)

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

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

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

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

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

(10)

設(shè)

則簡(jiǎn)單驗(yàn)證可得：

(11)

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

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

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

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

3 應(yīng)用

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

(12)

(13)

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

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

4 結(jié)論

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