張 軒,韓有攀

(西安工程大學(xué) 理學(xué)院,陜西 西安 710048)

0 引 言

近來(lái),分布式魯棒優(yōu)化成為解決不確定問(wèn)題的一個(gè)研究熱點(diǎn)．該優(yōu)化問(wèn)題為:在不能準(zhǔn)確得到隨機(jī)變量概率分布的情況下,將概率分布限定在由分布的一些特征所構(gòu)造的不確定集合(一階矩、二階矩信息、邊際分布或者支撐集合的信息等)中,從而在該不確定集合下求最優(yōu)．其關(guān)鍵是不確定集的構(gòu)造,其構(gòu)造遵循(1)包含真實(shí)數(shù)據(jù),具有高置信度的分布．(2)應(yīng)該在排除病態(tài)分布的情況下集合足夠小．(3)易于參數(shù)化數(shù)據(jù)．理想情況下,應(yīng)該易于轉(zhuǎn)化為一個(gè)可求解的數(shù)學(xué)模型,可以用現(xiàn)成的優(yōu)化軟件求解．

分布式魯棒優(yōu)化首次應(yīng)用是在1958年,Scarf[1]用于研究單個(gè)項(xiàng)目報(bào)童的分布問(wèn)題,其中模糊集合由具有相同均值和方差的概率分布族組成．隨后,該模型被Breton[2]推廣到動(dòng)態(tài)極大極小隨機(jī)規(guī)劃問(wèn)題中．在文獻(xiàn)[3-4]中，不確定集包含某些給定約束條件的單峰分布,且在一定條件下最壞分布為均勻分布．文獻(xiàn)[5]推廣了以前無(wú)分布假設(shè)的報(bào)童問(wèn)題,假設(shè)分布是關(guān)于均值和標(biāo)準(zhǔn)差的概率分布函數(shù),給出了一個(gè)優(yōu)化程序計(jì)算任意訂貨量下的最優(yōu)訂單．文獻(xiàn)[6]提出優(yōu)化問(wèn)題中不確定集的分布形式可以由離散分布(高斯分布、指數(shù)分布等)和矩信息(均值和協(xié)方差)兩種變量假設(shè),并將該優(yōu)化問(wèn)題通過(guò)對(duì)偶原理等轉(zhuǎn)化為可求解模型．文獻(xiàn)[7-8]研究了帶矩約束的二階段分布式魯棒優(yōu)化模型,分別在有線性決策規(guī)則和無(wú)線性決策規(guī)則下,運(yùn)用對(duì)偶原理將帶矩約束的二階段分布式魯棒優(yōu)化轉(zhuǎn)化為可求解模型．Gao等[9]在前人研究的基礎(chǔ)上引入高階矩約束,用半無(wú)限規(guī)劃方法求解帶高階矩約束的二階段分布式魯棒優(yōu)化問(wèn)題．

本文研究二階段分布式魯棒優(yōu)化問(wèn)題,在不確定集合由二階矩構(gòu)成且隨機(jī)變量的樣本空間由線性不等式構(gòu)成情況下的可求解模型．分別對(duì)決策變量在線性決策規(guī)則和無(wú)線性決策規(guī)則兩種不同情形下,通過(guò)對(duì)偶理論,給出相應(yīng)的可求解等價(jià)模型．

1 二階段分布式魯棒優(yōu)化

考慮模型

(1)

其中：式(1)中′為轉(zhuǎn)置,第一階段初始決策x=(x1,x2,…,xn),X={x:Bx=b,x≥0}?Rn,B∈Rq×n,b=(b1,b2,…,bq)∈Rq,Γ為不確定集．

第二階段優(yōu)化問(wèn)題為

Q(x,z)= mind′y
s.t.A(z)x+D(z)y=b(z)
y≥0

(2)

其中：d=(d1,d2,…,dk)∈Rk,D(z)∈Rl×k為補(bǔ)償矩陣,A(z)為技術(shù)矩陣,b(z)為右端項(xiàng)．

其不確定集由一階矩和二階矩約束確定

2 線性決策下的等價(jià)模型

在上述條件假設(shè)下,考慮其中Q(x,z)為式(3)優(yōu)化問(wèn)題的最優(yōu)值,即

Q(x,z)= mind′y
s.t.A(z)x+Dy=b(z)
y≥0

(3)

D∈Rl×k為固定的補(bǔ)償矩陣．利用凸性、對(duì)偶理論、極大極小原理將優(yōu)化問(wèn)題式(1),(3)等價(jià)轉(zhuǎn)化為可求解模型,其結(jié)果如下:

定理1 在線性決策下二階段分布式魯棒優(yōu)化問(wèn)題式(1),(3)等價(jià)于

證明利用線性對(duì)偶

其中,s=(s1,s2,…,sk)．則式(1),(3)變型為

將矩約束代入則為

根據(jù)文獻(xiàn)[10]中無(wú)窮維線性規(guī)劃對(duì)偶理論知,其對(duì)偶規(guī)劃為

(4)

其中：v0∈R,v=(v1,v2,…,vl)∈Rl,V=(V1,V2,…,Vl)∈Rl,μ=(μ1,μ2,…,μl),η=(η1,η2,…,ηl).

由于Ω是一個(gè)凸的多面體集合,并且第二階段優(yōu)化問(wèn)題是線性優(yōu)化,其解集是凸集,參考文獻(xiàn)[8],則式(4)中第一個(gè)約束條件?z∈Ω.

即

(5)

利用文獻(xiàn)[11]中凸二次規(guī)劃的Wolfe對(duì)偶性和變量的可分離性,式(5)等價(jià)于

整理為

(6)

其中,λj為新引入的對(duì)偶變量．

如果Vj>0,由2Vjzj+(vj-d′yj+Mjλj)=0得zj=-(vj-d′yj+Mjλj)/2Vj,

將其帶入式(6)即

引入輔助變量rj,令rj=(vj-d′yj+Mjλj)2/4Vj,上式等價(jià)于

(7)

如果Vj=0,從式(6)直接推出式(7)．

因此,式(1)，(3)轉(zhuǎn)化為

易得定理1．

定理1推廣了帶矩約束的二階段分布式魯棒優(yōu)化,給出在更為復(fù)雜的情形下的可求解模型．不僅豐富了相應(yīng)的理論成果,還為進(jìn)一步解決復(fù)雜的實(shí)際問(wèn)題提供了可行方法．

3 無(wú)線性決策下的等價(jià)模型

Q(x,z)考慮僅僅右端項(xiàng)隨機(jī)的二階段分布式魯棒優(yōu)化模型:

(8)

為了將優(yōu)化問(wèn)題式(1)，(8)轉(zhuǎn)化為易求解模型,需要假設(shè)以下3個(gè)條件:

條件2

條件3

條件1是對(duì)單純形頂點(diǎn)的假設(shè)．條件2是極大極小值原理,若X是緊集時(shí)成立,詳見(jiàn)文獻(xiàn)[12]．條件3是期望的最小值等于最小值的期望,若第二階段函數(shù)有最優(yōu)值且其解的集合為嚴(yán)格封閉的凸可測(cè)集時(shí)其成立,詳見(jiàn)文獻(xiàn)[13]的定理14.60．

引理1 在假設(shè)條件1-3成立情況下,下列等式成立

(9)

證明由條件2,3,優(yōu)化問(wèn)題式(1),(8)可進(jìn)行變形:

結(jié)合條件1知上式等價(jià)于

(10)

由Γ表達(dá)形式可得

根據(jù)文獻(xiàn)[10]中無(wú)窮維線性規(guī)劃對(duì)偶理論,其對(duì)偶形式為

minv0,v,Vv0+μ′v+η′V,
s.t.v0+z′v+(z2)′V≥max1≤i≤m(z′ωi+b′ui),
v,V≥0,
z∈Ω.

(11)

其中,v0∈R,v=(v1,v2,…,vl)∈Rl,V=(V1,V2,…,Vl)∈Rl,μ=(μ1,μ2,…,μl),η=(η1,η2,…,ηl).

由于z是一個(gè)凸的多面體集合,并且其第二階段優(yōu)化問(wèn)題的解集是凸集,式(11)等價(jià)于

min{v0+μ′v+η′V:v0+z′v+(z2)′V≥z′wi+b′ui,1≤i≤m,z∈Ω}.

證畢．

利用引理1將僅僅右端項(xiàng)隨機(jī)的二階段分布式魯棒優(yōu)化模型轉(zhuǎn)化后,可以看出其類似于定理1中的式(5)．通過(guò)凸二次規(guī)劃的Wolfe對(duì)偶性和變量的可分離性,將其轉(zhuǎn)化為可求解模型．

定理2 假設(shè)條件1～3成立,二階段分布式魯棒優(yōu)化沒(méi)有線性決策條件的優(yōu)化式(1),(8)等價(jià)于一個(gè)二階錐規(guī)劃問(wèn)題,即

證明由引理1知,式(11)約束條件為

v0+z′v+(z2)′V≥z′wi+b′ui,1≤i≤m,v≥0,V≥0,z∈Ω

對(duì)于固定的i,由Ω={z∈Rl:Mz≤g}得

(12)

與定理1證明類似,上式等價(jià)于

即定理2得證．

4 結(jié)束語(yǔ)

在樣本空間為多面體集合時(shí),探討決策變量服從線性決策規(guī)則和第二階段問(wèn)題中僅僅右端項(xiàng)為隨機(jī)變量的情形,并給出了在這兩種情形下二階段分布式魯棒優(yōu)化問(wèn)題等價(jià)于相應(yīng)的二階錐優(yōu)化問(wèn)題．為求解相應(yīng)的帶矩約束的二階段分布式魯棒優(yōu)化問(wèn)題提供了方法,而且為其應(yīng)用到實(shí)際問(wèn)題中奠定了基礎(chǔ)．