張 軒,韓有攀
(西安工程大學(xué) 理學(xué)院,陜西 西安 710048)
近來,分布式魯棒優(yōu)化成為解決不確定問題的一個(gè)研究熱點(diǎn).該優(yōu)化問題為:在不能準(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)童的分布問題,其中模糊集合由具有相同均值和方差的概率分布族組成.隨后,該模型被Breton[2]推廣到動(dòng)態(tài)極大極小隨機(jī)規(guī)劃問題中.在文獻(xiàn)[3-4]中,不確定集包含某些給定約束條件的單峰分布,且在一定條件下最壞分布為均勻分布.文獻(xiàn)[5]推廣了以前無分布假設(shè)的報(bào)童問題,假設(shè)分布是關(guān)于均值和標(biāo)準(zhǔn)差的概率分布函數(shù),給出了一個(gè)優(yōu)化程序計(jì)算任意訂貨量下的最優(yōu)訂單.文獻(xiàn)[6]提出優(yōu)化問題中不確定集的分布形式可以由離散分布(高斯分布、指數(shù)分布等)和矩信息(均值和協(xié)方差)兩種變量假設(shè),并將該優(yōu)化問題通過對(duì)偶原理等轉(zhuǎn)化為可求解模型.文獻(xiàn)[7-8]研究了帶矩約束的二階段分布式魯棒優(yōu)化模型,分別在有線性決策規(guī)則和無線性決策規(guī)則下,運(yùn)用對(duì)偶原理將帶矩約束的二階段分布式魯棒優(yōu)化轉(zhuǎn)化為可求解模型.Gao等[9]在前人研究的基礎(chǔ)上引入高階矩約束,用半無限規(guī)劃方法求解帶高階矩約束的二階段分布式魯棒優(yōu)化問題.
本文研究二階段分布式魯棒優(yōu)化問題,在不確定集合由二階矩構(gòu)成且隨機(jī)變量的樣本空間由線性不等式構(gòu)成情況下的可求解模型.分別對(duì)決策變量在線性決策規(guī)則和無線性決策規(guī)則兩種不同情形下,通過對(duì)偶理論,給出相應(yīng)的可求解等價(jià)模型.
考慮模型
(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為補(bǔ)償矩陣,A(z)為技術(shù)矩陣,b(z)為右端項(xiàng).
其不確定集由一階矩和二階矩約束確定
在上述條件假設(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為固定的補(bǔ)償矩陣.利用凸性、對(duì)偶理論、極大極小原理將優(yōu)化問題式(1),(3)等價(jià)轉(zhuǎn)化為可求解模型,其結(jié)果如下:
定理1 在線性決策下二階段分布式魯棒優(yōu)化問題式(1),(3)等價(jià)于
證明利用線性對(duì)偶
其中,s=(s1,s2,…,sk).則式(1),(3)變型為
將矩約束代入則為
根據(jù)文獻(xiàn)[10]中無窮維線性規(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)化問題是線性優(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í)際問題提供了可行方法.
Q(x,z)考慮僅僅右端項(xiàng)隨機(jī)的二階段分布式魯棒優(yōu)化模型:
(8)
為了將優(yōu)化問題式(1),(8)轉(zhuǎn)化為易求解模型,需要假設(shè)以下3個(gè)條件:
條件2
條件3
條件1是對(duì)單純形頂點(diǎn)的假設(shè).條件2是極大極小值原理,若X是緊集時(shí)成立,詳見文獻(xiàn)[12].條件3是期望的最小值等于最小值的期望,若第二階段函數(shù)有最優(yōu)值且其解的集合為嚴(yán)格封閉的凸可測(cè)集時(shí)其成立,詳見文獻(xiàn)[13]的定理14.60.
引理1 在假設(shè)條件1-3成立情況下,下列等式成立
(9)
證明由條件2,3,優(yōu)化問題式(1),(8)可進(jìn)行變形:
結(jié)合條件1知上式等價(jià)于
(10)
由Γ表達(dá)形式可得
根據(jù)文獻(xiàn)[10]中無窮維線性規(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)化問題的解集是凸集,式(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ī)劃的Wolfe對(duì)偶性和變量的可分離性,將其轉(zhuǎn)化為可求解模型.
定理2 假設(shè)條件1~3成立,二階段分布式魯棒優(yōu)化沒有線性決策條件的優(yōu)化式(1),(8)等價(jià)于一個(gè)二階錐規(guī)劃問題,即
證明由引理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得證.
在樣本空間為多面體集合時(shí),探討決策變量服從線性決策規(guī)則和第二階段問題中僅僅右端項(xiàng)為隨機(jī)變量的情形,并給出了在這兩種情形下二階段分布式魯棒優(yōu)化問題等價(jià)于相應(yīng)的二階錐優(yōu)化問題.為求解相應(yīng)的帶矩約束的二階段分布式魯棒優(yōu)化問題提供了方法,而且為其應(yīng)用到實(shí)際問題中奠定了基礎(chǔ).