張 軒,韓有攀

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

0 引 言

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

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

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

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)化問題為

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為補償矩陣,A(z)為技術(shù)矩陣,b(z)為右端項．

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

2 線性決策下的等價模型

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

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

(3)

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

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

證明利用線性對偶

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

將矩約束代入則為

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

(4)

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

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

即

(5)

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

整理為

(6)

其中,λj為新引入的對偶變量．

如果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,上式等價于

(7)

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

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

易得定理1．

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

3 無線性決策下的等價模型

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

(8)

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

條件2

條件3

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

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

(9)

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

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

(10)

由Γ表達形式可得

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

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是一個凸的多面體集合,并且其第二階段優(yōu)化問題的解集是凸集,式(11)等價于

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

證畢．

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

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

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

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

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

(12)

與定理1證明類似,上式等價于

即定理2得證．

4 結(jié)束語

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