魯棒優(yōu)化的方法與應(yīng)用

1、魯棒優(yōu)化的方法及應(yīng)用威在實(shí)際的優(yōu)化中決策過程中，我們經(jīng)常遇到這樣的情形，數(shù)據(jù)是不確定的或者是非精確 的；最優(yōu)解不易計(jì)算，即使計(jì)算的非常精確，但是很難準(zhǔn)確的實(shí)施；對于數(shù)據(jù)的一個(gè)小的擾動(dòng)可能導(dǎo)致解是不可行。魯棒優(yōu)化是一個(gè)建模技術(shù)，可以處理數(shù)據(jù)不確定但屬于一個(gè)不確定 集合的優(yōu)化問題。早在 19世紀(jì)70年代，Soyster就是最早開始研究魯棒優(yōu)化問題的學(xué)者之 一，他的文章給出了當(dāng)約束矩陣的列向量屬于一個(gè)橢球形不確定的集合時(shí)的魯棒線性優(yōu)化問 題。幾年以后 Falk沿著這條思路做了非精確的線性規(guī)劃。在以后的很長的一段時(shí)間里，魯 棒優(yōu)化方面都沒有新的成果出現(xiàn)。直到19世紀(jì)末，Ben-Tal,Nemirovs

2、ki的工作以及這時(shí)計(jì)算技術(shù)的發(fā)展，尤其是對于半定優(yōu)化和凸優(yōu)化點(diǎn)算法的發(fā)展，使得魯棒優(yōu)化又成為一個(gè)研究的熱點(diǎn)。一個(gè)一般的數(shù)學(xué)規(guī)劃的形式為min nxo : fo(x, ) % 0, fi(x, ) 0,i1,mXo R,x R其中x為設(shè)計(jì)向量，f0為目標(biāo)函數(shù)，f1, f2,，fm是問題的結(jié)構(gòu)元素。表示屬于特定問題的數(shù)據(jù)。U是數(shù)據(jù)空間中的某個(gè)不確定的集合。對于一個(gè)不確定問題的相應(yīng)的魯棒問題為min nx0: f°(x, ) x0 0, fi(x, ) 0,i 1,m, U x R,x R這個(gè)問題的可行解和最優(yōu)解分別稱為不確定問題的魯棒可行和魯棒最優(yōu)解。這篇文章主要回顧了魯棒優(yōu)化的基本算法

3、，目前的最新的研究結(jié)果及在經(jīng)濟(jì)上的應(yīng)用。1魯棒優(yōu)化的基本方法1.1魯棒線性規(guī)劃一個(gè)不確定線性規(guī)劃mincTx:Ax b (c,A,b) U Rn Rm n Rm所對應(yīng)的魯x棒優(yōu)化問題為 mint:t cTx,Ax b,(c,A,b) U,如果不確定的集合是一個(gè)計(jì)算上易處 理的問題，則這個(gè)線性規(guī)劃也是一個(gè)計(jì)算上易處理的問題。并且有下列的結(jié)論：假設(shè)不確定的集合由一個(gè)有界的集合Z RN的仿射像給出，如果 Z是1線性不等式約束系統(tǒng)構(gòu)成P p ,則不確定線性規(guī)劃的魯棒規(guī)劃等價(jià)于一個(gè)線性規(guī)劃問題。2由錐二次不等式系統(tǒng)給出|Ppi|2 qTji 1,.,M ,則不確定線性規(guī)劃的魯棒規(guī)劃等價(jià)于一個(gè)錐二次的問題

4、。dim3由線性矩陣不等式系統(tǒng)給出P0iP 0,則所導(dǎo)致的問題為一個(gè)半定規(guī)劃問題。1 11.2 魯棒二次規(guī)劃考慮一個(gè)不確定的凸二次約束問題min cTx: xT Aix 2biT x q ,i1,m (Ai, bi,q)m1U對于這樣的一個(gè)問題，即使不確定集合的結(jié)夠很簡單，也會(huì)導(dǎo)致 于這種問題的處理通常是采用它的近似的魯棒規(guī)劃問題。考慮一個(gè)不確定的優(yōu)化問題P min cTx: F(x, ) 0xNP難的問題，所以對U，假設(shè)不確定集合為U n V,而n表示名義的數(shù)據(jù)，而 V表示一個(gè)擾動(dòng)的集合，假設(shè)V是一個(gè)包含原點(diǎn)的凸緊集。不確定問題 P可以看成是一個(gè)不確定問題的參數(shù)族P min cTx: F(x

5、, ) 0 x0表示不確定的水平。具有橢圓不確定性的不確定的凸二次規(guī)劃問題的近似魯棒問題U (G,A,bi) (cn,AnE)TQj1,j1,，kk其中 Qj 0, Qj f 0j 1則問題可一轉(zhuǎn)化為一個(gè)半定規(guī)劃問題. T min c xs.t2xTbjn1Ci2Lt 1 qx . -2biLAnxT1Cl2MLCi.2T. 1x biT L x bikQij 3i j 11 "AxML JA x0,i1,，mAinx.1LA xL Ai x具有橢圓不確定集合的不確定錐二次問題的近似魯棒規(guī)劃 考慮不確定錐二次規(guī)劃min cTx: Ax biT x i,i 1,m(Ahi)im1U它的

6、約束為逐側(cè)的不確定U(A,bi, i, i)m1A,bi1 Uleft i, i1 U right它的左側(cè)的不確定的集合是一個(gè)橢圓Uleft ( A,b) (Ain,bin)Ll(Al,H)m1TQj1,j 1,k其中 Qj 0, Qj f 0 j i右側(cè)的不確定集合是有界的，它的半定表示為RU right ( i, i)( in, in) r( ir, ：)1| Vr 1u:P() Q(u)R 0, P( ),Q(u)為線性映射。則半定規(guī)劃為mincT xkj 1 jks.t.ijQij 1AinxbinA1xLAiLxnn i TAi xbi 11 T TAi xbi M0, i 1,，m

7、AiLxbiLTij 0,i 1,m, j 1,kxT in in Tr(RV),i 1,，m*其中P (Vi)M ,i1,.,mQ (Vi)0,i 1,mVi0,i 1,m1.3 魯棒半定規(guī)劃一個(gè)不確定的半定規(guī)劃的魯棒規(guī)劃為min cTx:AxiA0( A。,., An) m1 u由一個(gè)箱式不確定集合影響的不確定半定規(guī)劃的近似魯棒問題LU ( A0,.,An)(An,., A1)1(A0,., An)| IIl 11 o則半定規(guī)劃的近似的魯棒優(yōu)化為minx,XlnX1 Ax A0xjAj,l1,.,Lj 1cTx:X1 Ax,l 1,.,LLnX1A0xj,l 1,.,L由一個(gè)球不確定集合影

8、響的不確定半定規(guī)劃的近似魯棒問題LU(Ao,An)(An,W)1(A0,., An)| |2 1。l 1則半定規(guī)劃問題為G AxA2xLAixmin cTx: A2x FMAlxnM 0,F G 2( AnxjAjn)j iAlx具有易處理的魯棒counterparts的不確定線性規(guī)劃。如果多胞形是由有限集合的凸包給出的，則魯棒規(guī)劃為nmincTx:A0xjAlj 0, l 1,Lx j 12魯棒優(yōu)化的幾種新的方法魯棒規(guī)劃的最近的研究包括了對于可調(diào)節(jié)的魯棒優(yōu)化的研究以及對于魯棒凸優(yōu)化的研究。2.1不確定的線性規(guī)劃的可調(diào)節(jié)的魯棒解不確定線性規(guī)劃為 LPZmjin cTu:Uu Vv b u,V,

9、bZ，其中不確定集合ZRn Rmn Rm是一個(gè)非空的緊的凸集，V稱為recourse矩陣。當(dāng)V是確定的情況下,則稱相應(yīng)的不確定線性規(guī)劃為固定recourse的。定義：線性規(guī)劃 LPz的魯棒counterpart為(RC):mincTu: v ( U ,V,b Z):Uu Vv b, 則它的可調(diào)節(jié)的魯棒 counterpart為(ARC):muincTu: ( U ,V, b Z), v:Uu Vv b。可調(diào)節(jié)的魯棒規(guī)劃比一般的魯棒規(guī)劃靈活，但是同時(shí)它也比一般的魯棒規(guī)劃難解。對于一個(gè)不確定線性規(guī)劃的魯棒規(guī)劃是一個(gè)計(jì)算上易處理的問題，然而它相應(yīng)的可調(diào)節(jié)的魯棒規(guī)劃卻是不易處理的問題。但是如果不確定集

10、合是有限集合的凸包，則固定recourse的ARC是通常的線性規(guī)劃。從實(shí)際的應(yīng)用來看，只有當(dāng)原不確定問題的魯棒counterpart在計(jì)算上容易處理的時(shí)候，魯棒優(yōu)化方法才有意義。當(dāng)可調(diào)節(jié)的變量是數(shù)據(jù)的仿射函數(shù)時(shí)，可以得到一個(gè)計(jì)算上易處理的魯棒 counterpart.對于LPz的仿射可調(diào)節(jié)的魯棒 counterpart (AARC)可以表示為(AARC): min cTu :Uu V(w W ) b, ( U ,V,b Z)。u,w,W如果Z是一個(gè)計(jì)算上易處理的集合，則在固定recourse的情況下，LPz的仿射可調(diào)節(jié)counterpart (AARC) 是一個(gè)計(jì)算上易處理的問題。如果Z 是這

11、樣的一個(gè)集合，IZ U,V,b U 0,V0,b0lUl ,Vl,bl: ， 是一個(gè)非空的凸緊集。II在固定的recourse 的情況下，AARC 具有這樣的形式T0l0l0l0m1in Lc u :UlU u Vvlv blb ,u ,v0 ,v1 ,.,vL如果不確定的集合是一個(gè)錐表示的，則LPZ的仿射可調(diào)節(jié)的魯棒counterpart (AARC)是一個(gè)錐二次或半定規(guī)劃。如果 recourse 也是可變的，則AARC 是不易處理的問題，這時(shí)采用它的近似形式。在簡單橢圓不確定集合的情況下，AARC 等價(jià)于一個(gè)半定規(guī)劃。當(dāng)擾動(dòng)的集合是一個(gè)中心在原點(diǎn)的箱式集合或者是一個(gè)關(guān)于原點(diǎn)對稱的多胞形集合

12、，則AARC 可以有一個(gè)半定規(guī)劃來近似。對于多期的決策問題也是一個(gè)可調(diào)節(jié)的魯棒優(yōu)化問題。考慮一個(gè)兩期的決策問題inf inf f(u,v,p)uUvV其中 p 是不確定的，但屬于一個(gè)閉的有界的不確定集合?？尚屑疺 依賴于 u 和參數(shù) p 。則可以表示為V(u, p) ，或Vu( p) ?？烧{(diào)節(jié)的魯棒counterpart 問題可以表示為uinUf,tt: p P, v V(u, p) : f(u,v, p) t ，可以等價(jià)的表示為inf sup inf f (u,v, p)。u U p P v V(u,p)如果 P 包含有限數(shù)量的元素，P p1, p2,., pk ， 則對于每個(gè)piP ， 都

13、存在著相應(yīng)的vi 滿足上面的問題。則問題可以轉(zhuǎn)化為一個(gè)等價(jià)的單層優(yōu)化問題inf tu,v1,.,vk,ts.t. f(u,vi , pi ) t, i1,.,ku U ,vi V(u, pi ),i 1,.,k這樣的一個(gè)單層的優(yōu)化問題對于許多類的函數(shù)f 和集合 V (u, p) ，這是一個(gè)易處理的問題。比如f (u,vi, pi)f0(u,vi, pi) ，U u : gl(u) 0,l1,., m,V(u, pi) vi : fl(u,vi, pi ) 0,l 1,.,m2其中 fl(u,vi, pi)fl(wi, pi) wiT Ql (pi)wiql( pi)Twi bl (pi), l

14、 0,., m2gl (u) uTRlu rlTu dl , l1,., m1 ， wi(u,vi )T ,i1,., k在這種情況下，問題等價(jià)于一個(gè)二次約束的優(yōu)化問題inf tU,Vi，.,Vk ,ts.t wTQioWi qioTWibiot, i 1,kuT Ru rlTu dl0,l1,.,m1,wTQilwiqTilTwihl0,i1,.,k,l1,.,m2如果不確定集合是有限集合P pi, P2,., pj的凸包c(diǎn)onv(P),則考慮下面的問題inff (u,V, p)sup infp conv( P) v V(u，p)如果gu(p)inf f (u,v, p)是擬凸的，則 max

15、 gu (p) maxg/p)。則問題轉(zhuǎn)化為一v Vu (p)p conv(P)p P個(gè)單層的優(yōu)化問題。2.2 一個(gè)錐二次問題的魯棒解一個(gè)錐二次約束的形式為| Ax b|2 cTx d, A Rmn,b Rm,c Rn,d R,或者是等價(jià)的形式Ax b m 1TL , L 是 Lorentz 錐。c x d假設(shè)不確定參數(shù)屬于一個(gè)有界的集合。兩種類型的不確定集合常常用到，一個(gè)是數(shù)有界的不確定集合，一個(gè)是擾動(dòng)的向量屬于一個(gè)有界的擾動(dòng)集合時(shí)的結(jié)構(gòu)不確定集合。對于參數(shù)的結(jié)構(gòu)不確定為LS ( A, b,c,d) (A0,b0,c0,d0)i(Al,bl ,cl,dl),V,其中 是描述1 1擾動(dòng)的向量，

16、0是表示擾動(dòng)幅度的向量，V是擾動(dòng)集合，A0,b0,c0,d0是名義數(shù)值，Al,bl,cl,dl為擾動(dòng)方向。V是橢圓的交集V RL： TQk1,k 1,.,K,KQk k 1,., K為對稱的正半定矩陣，且Qk是正定的。k 1對于一個(gè)單側(cè)不確定的錐二次約束，曰Ghaoui和Lebret證明了在不確定集合是數(shù)有界的情況下，問題等價(jià)于一個(gè)錐二次約束。Ben-Tal,Nemirovski給出了在擾動(dòng)集合是橢圓集合的交集的結(jié)構(gòu)不確定的情況下，如果是簡單的橢圓不確定集合，則相應(yīng)的魯棒counterpart為一個(gè)線性矩陣不等式，在一般的情況下，問題是 NP難的，但是可以用線性矩陣不等式來 近似。Ben-Ta

17、l等研究了逐側(cè)不確定的錐二次約束，即對于影響左側(cè)的不確定獨(dú)立于影響右側(cè)的不確定。(A,b,c,d) (A,b,c,d) (A,b) U ,(c,d) U , U ,U 是相互獨(dú)立的集合。則x是問題| Ax b|2 cTx d的可行解，但且僅當(dāng)存在，使得IIAx bl2, A,b U和cTx d, c,d U 成立。在具有橢球交集的結(jié)構(gòu)不確定的集合的情況下，這兩個(gè)問題是易處理的。在很多的情況下，影響兩側(cè)的不確定集合是相互依存的。比如考慮一個(gè)不確定的錐二次約束|A x b |2 cTx d , V,(*)其中Az,bz,cz,dz關(guān)于z是仿射的。V是中心在原點(diǎn)的橢圓的交集L TK 一 一V R :

18、Qk1,k 1,，K,Qkk 1,，K為對稱的正半定矩陣，且 一Qk是k 1正定的。如果存在著k 0,0,且滿足下式，則 x滿足(*)式。v(x) k kwTxuTxwxk kQkUTx0uxUx I其中 vx (c0)Tx d°,wx 1(c1)Tx d1,.,(cL)Tx dLT,ux ：A°x b0,111 L LUx -A1x b1,.,ALx bL.如果向量x被分成兩部分，x (uT , vT )T ,其中u表示不可調(diào)節(jié)的變量，v表示可調(diào)節(jié)的變量。假設(shè)目標(biāo)函數(shù)是確定的，獨(dú)立于可調(diào)節(jié)的變量V,則相應(yīng)的錐優(yōu)化問題為mincTuUu Zv b K,K是一個(gè)錐。則相應(yīng)于不

19、確定集合S的魯棒counterpart為mjMcTu v:Uu Zv b K, (U,Z,b) S 則可調(diào)節(jié)的魯棒規(guī)劃為mincTu (U ,Z,b) S, v v(U,Z,b):Uu Zv b K,。uv w W ,這樣得到了可調(diào)節(jié)的魯棒規(guī)劃比一般的魯棒靈活一些。但是這樣會(huì)導(dǎo)致所得到的問題是不易處理的。克 服計(jì)算上缺點(diǎn)的一個(gè)方法是限制可調(diào)節(jié)的變量為一個(gè)仿射函數(shù)。仿射可調(diào)節(jié)的魯棒規(guī)劃為min cTu Uuu,wWZ(w W ) b K,(U,Z,b) S對于結(jié)構(gòu)不確定的錐二次約束可表示為IIA x 可|2 cTx d,如果則上面的約分別用u,v表示x的子向量，并且分別對應(yīng)于不可調(diào)節(jié)的部分和可調(diào)

20、節(jié)的部分,束可以表不為|U u Z v b ， eTu 門v d (*),若v w W ,則上面的約束即為仿射可調(diào)節(jié)的約束。下面分成兩種情況來討論，一種是固定的recourse,即Z是確定的，一種是可變的recourse ,即Z是不確定的。在第一種情況下，如果約束由(*)表達(dá)，擾動(dòng)集合為中心在原點(diǎn)的橢圓的交集，如果存在k 0,k 1,K和0使得下式成立，則會(huì)存在一個(gè)解u,v w W 滿足(*),對于所有的擾動(dòng)V成立，T1 Tu,w,W k k - Tu,w,W- %u,w,W-u,w,Wk kQk- %u,w,W01 %u,w,W%,w,WI2 2其中 U0u Zw b0,% Ulu ZW(

21、bl,l 1,.,L0TT . 0e u f w d ,l elTu fTWl dl,l 1,.,L在第二種情況下，如果擾動(dòng)很小，使得二次項(xiàng)可以被忽略，則可以用上面的半定規(guī)劃來近似。如果二次項(xiàng)不能夠被忽略，則需要增加一些變量后能夠用一個(gè)半定規(guī)劃來近似。2.3魯棒凸優(yōu)化2.3.1 魯棒凸二次約束的規(guī)劃問題一個(gè)凸二次約束的規(guī)劃問題為mincTxTTs.tx Qix 2qi x i 0,i 1,., p其中x為決策向量，c Rn, i R,qiRn,Qi Rn n。 0為參數(shù)。上面的這個(gè)問題可以轉(zhuǎn)化為一個(gè)二階的錐規(guī)劃問題 .Tmin c x1 i2qTx, i 1,., p2Vix s.tt(1 i

22、 2qi x)由于上述的模型對于參數(shù)很敏感，所以有必要研究其對應(yīng)的魯棒問題 一個(gè)一般的魯棒凸二次規(guī)劃問題為mins.txTQix 2qiTx0,Q,qi，i)Si，i1,，p當(dāng)不確定的集合 Si,i 1,., p是橢球時(shí)，上面的問題可以轉(zhuǎn)化為一個(gè)半定規(guī)劃問題，這里我們來確定Si的結(jié)構(gòu)，使它能夠轉(zhuǎn)化為一個(gè)二階錐規(guī)劃。分成以下的三種情況1離散集合和多邊形不確定集合對于離散形式的集合定義為Sa (Q,q, )：(Q,q,)(Qj,qj, j),Qj 0, j 1,.,k,魯棒約束xTQx 2qTx0, (Q,q, ) Sa等價(jià)于K個(gè)凸二次約束xTQix 2qTxi 0, j 1,.,k o或者等價(jià)的

23、k個(gè)二階錐約束。 對于離散集合的凸包為kkSa (Q,q, ):(Q,q, ) j(Qj,qj, j),Qj 0, j 0, j,j 1xTQx 2qTx0, (Q,q, ) Sa 等價(jià)于j 1,則魯棒約束j 1kjx Qix 2qi x i 0, j j 1k0, j, j 1j 1將上面的兩種情況下的集合推廣到多邊形的不確定集合kSb (Q,q, )：(Q,q, )j(Qj,qj, j),Qj 0, j 1,.,k,A b, 0j 1如果決策向量x Rn滿足魯棒約束xTQx 2qTx0 ,對于所有的(Q,q,)Sb,當(dāng)且僅當(dāng)存在著Rk ,使得bT02Vx stT T(1 i 2qTx AT

24、 )2qTx AT , i 1,.,p其中 Aj 是 A的第 j 列，Qj VjTVj, j1,.,ko2數(shù)約束的不確定的集合Sc (Q,q, ):(Q,q, ) (Q。，0)Uj(Qj,qj, j 1j),Qj0,u0, u p 1一個(gè)決策向量x Rn滿足魯棒約束xTQx 2qTx0 ,對于所有的(Q,q, ) Sc,當(dāng)且k_僅當(dāng)存在f R和 0,滿足2Vix(1 i 2qTx fj)1 i 2qTx fj, i 1,p2V0X11 V, flqT2q°x. 11_ T0 ，其中一一1 , Qj Vj Vj , j 0,., k pq二次項(xiàng)和錐項(xiàng)的不確定性是獨(dú)立的，即kSd (Q,

25、q, ):(Q,q, ) (Qq, 0)Uj(Qj,qj, j),Qj 0, j 1,k, Up 1j 1k(q, ) (q0, 0) Vj(qj, j),|vr 1j 1一個(gè)決策向量x Rn滿足魯棒約束xTQx 2qTx0,對于所有的（Q,q, ） Sd ,當(dāng)且k_僅當(dāng)存在f, g R和 0 ,滿足gj 2qTx j, j 1,.,k,fj, i 1,.,k2VoX11 V, f q g s一個(gè)決策向量x Rn滿足魯棒約束xTQx 2qTx0,對于所有的（Q,q, ） Se,當(dāng)且僅當(dāng)存在n,v, , r R,u R , wRm,tRm,使得下式成立0,v1Tt,1 rmax(H)iUi,Uj

26、xj,Ujxj, j 1,.,n1S 2xv 2qTx02qT x 0，其中一一1 , 1 , Qj VjTVj,p q r sj 0,.,k3因子化的不確定的集合如果不確定的集合定義為Q VTFV , F Rmm,VRm nF F0, T, N 2 N 2,Fo 0,N 0Se(Q,q, 0):V V0,|Wi|g MTGWii, i,G 0q q。Rn,| i s .飛-,S 02r1其中H GF0max(H) max1 i2wiN)G12,Hi)QTm i，i),i 1,，mQ是H的譜分解,diag(),w QTF 2G2V0x。2.3.2二次約束的二次規(guī)劃的魯棒解對于一個(gè)非凸的二次約束

27、的二次優(yōu)化問題min f0(x)s.t fk(x) 0,k 1,.,m,x C其中C Rn是一個(gè)多面體，并且包含在a,b a x b Rn中，每個(gè)fk(x),k 0,1，mRn的形式為kk 2kfk(x)qxxjc xidix a。i jii任何一個(gè)二次多項(xiàng)式可以寫成兩個(gè)正系數(shù)的二次多項(xiàng)式的差，一個(gè)一般的(QQP)可以寫成minf0 (x) f0 (x)s.tfk (x) fk (x) 0,k 1,.,m, x C由于f0 (a)f0 (x)f0 (b), x a,b,則問題可以轉(zhuǎn)化為min f0 (x) tst t f0 (x) 0fk (x) fk (x) 0,k 1,.,m,x Cf0

28、(b) tf0 (a)通過變換記號，可以得到這樣的形式minf(x)g(x) 0,x a,b其中f (x) i jcijxxj 'x2i di xi ,所有的系數(shù)為正的。g(x) min (Uk (x) Vk(x),并且Uk(x), Vk(x)為單調(diào)遞增的二次函數(shù)使得 k 1,.,mi d'xibk因?yàn)樗鼘σ粋€(gè)小的擾動(dòng)非常的不穩(wěn)kk 2gk(x)jCijXxjiCi x由于孤立的最優(yōu)解即使是可計(jì)算的，但是它是難于實(shí)施，定，因而，從實(shí)際的觀點(diǎn)來看，只有非孤立的可行解有意義。Essential最優(yōu)解f(x ) min f (x) x S, S表示所以非孤立的可行解的集合。Essen

29、tial 可行解：0, x a, b滿足 g(x) 。一個(gè)非孤立的可行解 X稱為是Essential最優(yōu)解，如果它滿足f(x) inf(f(x)g(x) ,x a,b)尋找Essential最優(yōu)解的方法是：從一個(gè)初始的Essential可行解，尋找一個(gè)更好的Essential可行解，直到不能獲得比當(dāng)前的可行解更好的可行解為止。假設(shè) 為一個(gè)Essential可行解的目標(biāo)函數(shù)值，給定0:如果f(a) ,由于f(x)單調(diào)遞增，則f(x) , x a,b如果f(a), g(a) 0 ,則a即為一個(gè)Essential可行解如果f(a), g(a) 0 ,則需要考慮一個(gè)輔助的問題(Q/ ) maxg(x)

30、 f (x) ,x a,b(Q/ )求解采用分支定界的方法。這篇文章中給出了一個(gè) successive incumbent transcending(SIT)算法。3魯棒優(yōu)化的應(yīng)用魯棒優(yōu)化現(xiàn)在已經(jīng)應(yīng)用到了各個(gè)研究領(lǐng)域，這里我們主要給出了在金融上的應(yīng)用。1. Ruijun Shen和Shuzhong Zhang 將魯棒的觀點(diǎn)應(yīng)用于基于 scenario樹的投資組合的 選擇問題中，給出了一階段和兩階段的組合選擇模型相應(yīng)的魯棒規(guī)劃問題。這里允許概率分布存在ambiguity.這樣的一個(gè)問題能夠轉(zhuǎn)化為一個(gè)有限的錐形式凸規(guī)劃問題。并且在不允許賣空的情況下，效用函數(shù)采用下半方差的負(fù)值， 參數(shù)的不確定集合是

31、橢球形的， 則相應(yīng)的問 題可以轉(zhuǎn)化成一個(gè)二階錐規(guī)劃問題。假設(shè)想從n種資產(chǎn)中選擇一個(gè)投資組合并且持有一段時(shí)間，假設(shè)初始的財(cái)富為1,持有期末有m種可能的結(jié)果。即所有的可能的 scenario可以通過一個(gè)具有 m個(gè)葉子的一階段樹 來表示。假設(shè)收益向量的第 i個(gè)元素表示表示第i種資產(chǎn)的收益。則基于 scenario的單階段 的組合選擇模型為m一, T八maxiu( r )i 1s.tTe 1n是股票的數(shù)量，m是每個(gè)節(jié)點(diǎn) scenario的數(shù)量Rn是持有的股票，是模型中的決策向量r i Rn是如果scenario i出現(xiàn)的話n個(gè)股票的收益是scenario i出現(xiàn)的概率eRn 是分量全為1 的向量是允許

32、的投資組合集合則兩階段的效用極大化投資模型為mmi i*T ijmax i ju( r )i1 j1s.tTe 1rijRn表示如果scenario i出現(xiàn)在第一階段，scenario j出現(xiàn)在第二階段ij 表示條件概率scenario j 出現(xiàn)在第二階段在scenario i 出現(xiàn)在第一階段的條件下的概率。i 第二階段允許的投資組合則上面的問題可以寫成*是第二階段的recourse問題的最優(yōu)解mi iT ijmax ju( r )i1iT T is.t. e r , i 1,2,., mmaxmmi iT iji max ju(r )i1i i1iT T is.te r , i 1,2,.,

33、 m(P2)s.t. Te 1假設(shè)可行集為凸集T i iiT令 ( 1,., m ) ，( 1 ,., m ) ， 且由定義可知為非負(fù)的向量Te 1, iT e 1問題(P2)是可分的，則可得mmaxi1mi iT ijmax ju( r )i i1s.t.iT Tr,i iTi 1,2,., m1,u(g) 是凹的，則上面的問題為凸規(guī)劃。單階段模型的魯棒規(guī)劃模型確定的情景樹有兩個(gè)缺點(diǎn)：一個(gè)是每個(gè)情境中收益的模糊性，一個(gè)是每個(gè)情景發(fā)生的條件概率的模糊性。實(shí)際上在我們的模型中用到的收益向量為估計(jì)值。并且我們并不知道確切我們可以得到的收益為多少，但是根據(jù)統(tǒng)計(jì)分析，我們知道實(shí)際的值離我們估計(jì)的值不遠(yuǎn)

34、, 某些置信區(qū)間。ri Vi (收益的模糊性)(概率分布的模糊性)假設(shè)所有的集合為凸的，緊的，非空的。令%, U則魯棒模型為max mins.tvi,y uTe 1m(%i 1yi)u(Tri)兩階段的魯棒規(guī)劃模型兩階段的模型中的估計(jì)量為%, %,%，令%, U%, Ui%,yimax minri Vi,y U(%yi) max mini rj Vj ,yiUii iT j、 yj)u(r )s.tiTei 1,2,., mTe 1單階段魯棒模型的有限表示假設(shè)條件：1沒有賣空Rn2 一個(gè)半方差的非效用函數(shù) d(w) (R w)2相當(dāng)于一個(gè)給定的基準(zhǔn)組合的下方風(fēng)險(xiǎn)，相應(yīng)2的效用函數(shù)為u(w) (

35、R w)。模糊集合是橢球形的：Rm Te1,%,ViriRn(rii%)TQi(ri幽i2,i 1,m為了簡便，假設(shè) Qi是單位矩陣U y Rm yTe0, yi i nV r Rri%i, i1,m則原模型可變形為max(R Tr%)2s.t則相應(yīng)的魯棒規(guī)劃模型為maxs.t進(jìn)一步變形為利用結(jié)論t0m1(%將上面的規(guī)劃變?yōu)閕 miinri Vi,y UTe 1m(%yi)min,t1 ,t0s.tmin,t1 ,t0s.tyi )ai, yt0t。tit0tOti(R T%)2max( %max(Rri Vi1,y)TtTr%)2max( % y)Tt2 i ,max(R0T%)21,t。(

36、a%aaTesoc(m 1)e一)m對于一個(gè)一般的模型通過增加變量變?yōu)槿绻鸇THmin to,t1 ,t0t0%aT/ a e、(a e)m0,max minris.tmax t0Stt0UiWisoc(mti 11), ti 1 soc(3)T%0,vi,y uTe 1(%U(Wi),1,個(gè)凸集，則它的齊次錐是則可以得到如下的凸表示mint0對于多階段的魯棒模型soc(n1)(%yi)u(yi)4,%tt。Wi0,H(D)clH(U) ,UiH(Vi)Te 1x0,； DU(Wi),max minri Vi,y U(%x)maxirijminVij,yi Uis.tiT T ie r ,i/

37、iiT ij、2(% yj)(R rj)1,2,., mi 0,Te 1因此Wi：riTri把千Vi映射到區(qū)間T%i| |, T% i| |,則上述模型等價(jià)于iT% i )2mmmax minri V i,y U(% yi) max min max ( % yij)( Riji 1yj 1iT _s.t. e Wi, i 1,2,m i 0,T% iWiT% i|2. R.h.tutuncu, M.Koenig 給出一個(gè)基于 worse-case的方法。在一個(gè)簡單的情況下，相 應(yīng)魯棒優(yōu)化問題是一個(gè)標(biāo)準(zhǔn)的二次規(guī)劃問題，在大多數(shù)情況下，這個(gè)問題可以轉(zhuǎn)化為一個(gè)鞍點(diǎn)問題。利用 2003年Handors

38、son和Tutuncu給出的方法求解。作者給出了在不確定集合 為區(qū)間時(shí)的魯棒MVO模型，和魯棒最大夏普比率問題。一個(gè)資產(chǎn)分配問題可以表示為在期望收益的下限上極小化方差或最大化一個(gè)風(fēng)險(xiǎn)調(diào)節(jié) 的期望收益min xT Qxx Rmax TxxTQxs.t Tx R, （1）x Rn（2）s.t xxn其中 x RnX 1,x 0i 1對于期望收益的向量和協(xié)方差矩陣Q分別取成區(qū)間的形式U : LUUq Q:QL Q QU,Q 0U （ ,Q）: U ,Q Uq采用區(qū)間型數(shù)據(jù)的原因：（1）區(qū)間的端點(diǎn)對應(yīng)于歷史數(shù)據(jù)中相應(yīng)的統(tǒng)計(jì)的極值，在分 析估計(jì)和Scenarios中。（2）建模者可以選擇置信水平，以預(yù)測

39、區(qū)間的形式產(chǎn)生收益和協(xié)方 差的估計(jì)。給定不確定集合U ,優(yōu)化問題（1） （2）對應(yīng)的魯棒優(yōu)化為minmax xTQx x Rni Q UqJs.tminUTx R, (7)max minxU ,Q UqTxxTQx (8)）是（8） 一個(gè)給定正值的最優(yōu)解，則* x （）也是（7）的最優(yōu)解對于T *，、R min x ()。UUS財(cái)政證券可以認(rèn)為是無風(fēng)險(xiǎn)投資。如果這樣的資產(chǎn)包含于資產(chǎn)類中，則有效的投資組合是這個(gè)無風(fēng)險(xiǎn)資產(chǎn)和一個(gè)風(fēng)險(xiǎn)組合的線性組合。這個(gè)最優(yōu)的組合是具有最高夏普比率的T,“ 一、 x rf組合。h(x) _ , %為無風(fēng)險(xiǎn)的已知收益。假設(shè) Q是正定的。因?yàn)?Q是正半定的, x Qx若

40、它是正定的，則意味著沒有冗余的資產(chǎn)。具有最高夏普比率的組合可以通過解決下面的優(yōu)化問題給出：(11)max h(x) s.t x這個(gè)目標(biāo)函數(shù)是一個(gè)非線性，非凹的目標(biāo)函數(shù)，難以解決。利用 lifting技術(shù)對進(jìn)行齊次化:xRn,Rx0, U (0,0),增加(0,0)是為了或得一個(gè)凸集。個(gè)錐，當(dāng)個(gè)環(huán)的時(shí)候,是一個(gè) ice-cream錐，若是一個(gè)多面體,x Axb,cxx Ax b 0,cxd 0,0。h(x)rf/ TXT( rfe) xxT Qx,xT Qx:g(x)xg(一),0,由于g(x)是齊次的，則問題等價(jià)于 max g(x)s.t (x,),由于g(x)是齊次的，則增加規(guī)化的約束不會(huì)影

41、響最優(yōu)解則問題等價(jià)于1 max xTQxSt (x,),(rfe)T1結(jié)論：給定一個(gè)可行的具有 eT x1性質(zhì)的組合集x ,這個(gè)集合中具有最大夏普比率的解可以通過下面的規(guī)劃來解:max xTQxs.t (x,),(15)(x,k)是(15)的解，則x 父/。松弛問題如下:minmax xTQxs.tmin( rfe)T 1(x,)魯棒有效前沿的算法:minmax xTQx1利用SP算法解決沒有期望收益約束的問題xRn QUQ ，令表示他的最優(yōu)解，令s.txLT .令xmax表示他的最優(yōu)解，Rmax() xmax ,Rmin()xmin2 ,解決問題max minxU ,Q Uq3選才IK,有效

42、前沿上點(diǎn)的數(shù)量,R Rmin/(K1),Rmin2/(K1),，Rmin(n 1) /(K 1),解決問題minmax xTQxx Rn，Q Uq. Ts.tminx R,Ux3. Mustafa C.Pinar給出了多階段的組合選擇模型。目標(biāo)是最大化最終期望收益和最小 化與一個(gè)給定的財(cái)富水平的偏差。他們之間是通過一個(gè)非負(fù)參數(shù)來平衡的。利用一個(gè)分段的線性罰函數(shù)，能夠得到線性規(guī)劃模型，并且能夠確保如下階段的最優(yōu)性。假設(shè)有m+1#資產(chǎn)，前m種為風(fēng)險(xiǎn)的股票，第 m 1種為無風(fēng)險(xiǎn)資產(chǎn)，比如現(xiàn)金。x0表示1階段初的決策向量，x0i表示相應(yīng)的組合種第i種資產(chǎn)的市值。1x1表示2階段初的決策向量，r1,r2

43、表示一階段和二階段結(jié)束后的凈資產(chǎn)收益。是有限概率空間上(，F(xiàn) , P)的離散的隨機(jī)變量。假設(shè)市場的發(fā)展是離散的scenario樹。1rn表不隨機(jī)變重r相應(yīng)于第一層scenario樹的第n個(gè)干點(diǎn)的頭現(xiàn)?；谧畲蟮钠谕?end-of-horizon組合值的沒有交易費(fèi)用的兩階段組合選擇模型的隨機(jī)規(guī)劃為：mgxPnQn(x0) eTx01,x0 0x2n N2-t-P,1,z- /° r/ 2T 1/_T 1/ 1T 01c,其中 Qn(x )mxax( rn ) x (n)(e) x (n)(r (n) x ,x 0由于recourse問題Qn(x0), nN2的可分性，上面的優(yōu)化問題等價(jià)

44、于r - z2xT 1 T 0. z xT 1z1 XT 0_ Kl 0 c 1 c, °max Pn(rn) x (n) e x 1,(e) x (r (n) x , n N1,x 0, xn 0 x xn,n N1 n N 2以上的模型假設(shè)決策者是風(fēng)險(xiǎn)中立的，Mulvey,Vanderbei and Zenios建議通過由一個(gè)參數(shù)控制給目標(biāo)函數(shù)增加一個(gè)風(fēng)險(xiǎn)項(xiàng)得到兩階段的魯棒隨機(jī)規(guī)劃。他們的模型為mgxPnQn(x0)f (ri2)Tx1,(r；)Tx1(N) eTx0 1,x00(4)x n N2則可分離的魯棒優(yōu)化模型為./ 2、T 1r / 2、T 1/2、T 1、/ 01一、

45、 、0max Pn(rn) x (n)f (1 ) *(1),.,(木)x(N)(x,xn, n N1)xXn，n N1 n N201T 0T 1/ 1T 001(x ,xn, nN1) :e x 1,(e) xn(%)x, nN1，x0,xn 0Takriti and Ahmed證明了對于任意的方差測度f ,上式對能夠給出當(dāng)兩階段的組合決策問題對于recourse問題不是最優(yōu)時(shí)的最優(yōu)解。 如果f是一個(gè)非減的函數(shù)， 0 ,則上面的兩個(gè)問題時(shí)等價(jià)的。Takriti and Ahmed利用了一個(gè)分段二次的方差度量f(t) n(R tn)2 ,其中R*是目標(biāo)函數(shù)值。t是一組離散的隨機(jī)變量，具有實(shí) n

46、 N2現(xiàn) t1,t2,.,tN2 ,而 1, 2，.，N 是相應(yīng)的概率。為了是計(jì)算方便是所得的問題是一個(gè)線性規(guī)劃，采用一個(gè)分段線性的方差測度f(t) n(R tn) n心它仍然滿足非減的條件。則我們的問題變?yōu)?、T 12、T 10 10max Pn(rn ) x (n)Pn(R* "n ) x (n) ) (x , xn, n N1)xXn，n N1 n N2n N201T 0T 1/ 1T 001(x ,xn, n N1) :e x 1,(e) xn (%) x , n N1,x 0,xn 0可以將上面的模型推廣到三階段的情況。在這篇文章中作者還給出了包含線性交易費(fèi)用的模型。1，

47、一 yn表示一階段買入資產(chǎn)的數(shù)量，1 ,i表示一階段買入一美元的資產(chǎn)的交易費(fèi)1Zn表示一階段賣出資產(chǎn)的數(shù)量，1Vi1表示一階段賣出一美元的資產(chǎn)的交易費(fèi)11xni表示x：的第i個(gè)分量則對于風(fēng)險(xiǎn)資產(chǎn) x：i rnix°i y：i z；i, i 1,.,mmm對于無風(fēng)險(xiǎn)資產(chǎn) x1m 1 r；m 1x°：m 1(11)丫：1(1 vjz3i 1i 1m初始的資金要求為(1i°)x°i 1 x0m 1則可行集為T （ x0,x：, y1, z1, n N1）：滿足上面的三個(gè)方程帶有交易成本的魯棒兩階段的投資組合選擇的模型為0 MaxPn（r；）Tx1（n）Pn（R

48、*（心丁父）（x0, xn, y：, z：, n N1） Tx xn ,yn,zn,n N1 n N2n N24. Aharon Ben-Tal, Tamar Margalit Arkadi Nemirovski給出 了一個(gè)多階段的組合選擇問題的魯棒建模方法。假設(shè)有n種類型的資產(chǎn)i 1,.,n和現(xiàn)金（n 1）。L個(gè)投資階段。目標(biāo)是控制這些資產(chǎn)的一個(gè)投資組合。x'表示投資組合中資產(chǎn)i在階段l開始時(shí)的數(shù)量。xl可以有下列的方程給出:.l l 1 l 1 l li n 時(shí)，xi n xi小 Zil 1 l 1l 1 一ri xi是來自前一個(gè)階段的數(shù)量，ri0表示資產(chǎn)收益。£表示在階

49、段l初買入的資產(chǎn)數(shù)量。yl表示在階段l初賣出的資產(chǎn)數(shù)量。nl、 ll、 l)yi (1 vMi 1nll 1 l 1i n 1 時(shí)，xn1 rn 1xn 1(1i 1l 1 l irn 1xn 1是從前一個(gè)階段得到的現(xiàn)金流;（1 il） y：是在階段l賣出資產(chǎn)i得到的資產(chǎn)數(shù)量，：表示交易成本（1 v：） Zil表示在階段l買入資產(chǎn)i得到的資產(chǎn)數(shù)量，Vil表示交易成本應(yīng)該滿足約束l yiiz 為假設(shè)約束為簡單的約束，即下界為目標(biāo)是極大化期末財(cái)富的總價(jià)值vmax vi i 1 ix ri xi1 1yiy”1,.,n, 二lZZi ,i1,.,n,l-lVxi ,i1,.,n0,上界為無窮大n 1Jx；?？傻玫骄€性規(guī)劃模型為 i 1n 1 L Lri xii 11