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

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

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

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

5、, ) 0 x0表示不確定的水平。具有橢圓不確定性的不確定的凸二次規劃問題的近似魯棒問題U (G,A,bi) (cn,AnE)TQj1,j1,，kk其中 Qj 0, Qj f 0j 1則問題可一轉化為一個半定規劃問題. 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具有橢圓不確定集合的不確定錐二次問題的近似魯棒規劃 考慮不確定錐二次規劃min cTx: Ax biT x i,i 1,m(Ahi)im1U它的

6、約束為逐側的不確定U(A,bi, i, i)m1A,bi1 Uleft i, i1 U right它的左側的不確定的集合是一個橢圓Uleft ( A,b) (Ain,bin)Ll(Al,H)m1TQj1,j 1,k其中 Qj 0, Qj f 0 j i右側的不確定集合是有界的，它的半定表示為RU right ( i, i)( in, in) r( ir, ：)1| Vr 1u:P() Q(u)R 0, P( ),Q(u)為線性映射。則半定規劃為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 魯棒半定規劃一個不確定的半定規劃的魯棒規劃為min cTx:AxiA0( A。,., An) m1 u由一個箱式不確定集合影響的不確定半定規劃的近似魯棒問題LU ( A0,.,An)(An,., A1)1(A0,., An)| IIl 11 o則半定規劃的近似的魯棒優化為minx,XlnX1 Ax A0xjAj,l1,.,Lj 1cTx:X1 Ax,l 1,.,LLnX1A0xj,l 1,.,L由一個球不確定集合影

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

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

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

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

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

13、存在著相應的vi 滿足上面的問題。則問題可以轉化為一個等價的單層優化問題inf tu,v1,.,vk,ts.t. f(u,vi , pi ) t, i1,.,ku U ,vi V(u, pi ),i 1,.,k這樣的一個單層的優化問題對于許多類的函數f 和集合 V (u, p) ，這是一個易處理的問題。比如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在這種情況下，問題等價于一個二次約束的優化問題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的凸包conv(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)。則問題轉化為一v Vu (p)p conv(P)p P個單層的優化問題。2.2 一個錐二次問題的魯棒解一個錐二次約束的形式為| Ax b|2 cTx d, A Rmn,b Rm,c Rn,d R,或者是等價的形式Ax b m 1TL , L 是 Lorentz 錐。c x d假設不確定參數屬于一個有界的集合。兩種類型的不確定集合常常用到，一個是數有界的不確定集合，一個是擾動的向量屬于一個有界的擾動集合時的結構不確定集合。對于參數的結構不確定為LS ( A, b,c,d) (A0,b0,c0,d0)i(Al,bl ,cl,dl),V,其中 是描述1 1擾動的向量，

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

17、l等研究了逐側不確定的錐二次約束，即對于影響左側的不確定獨立于影響右側的不確定。(A,b,c,d) (A,b,c,d) (A,b) U ,(c,d) U , U ,U 是相互獨立的集合。則x是問題| Ax b|2 cTx d的可行解，但且僅當存在，使得IIAx bl2, A,b U和cTx d, c,d U 成立。在具有橢球交集的結構不確定的集合的情況下，這兩個問題是易處理的。在很多的情況下，影響兩側的不確定集合是相互依存的。比如考慮一個不確定的錐二次約束|A x b |2 cTx d , V,(*)其中Az,bz,cz,dz關于z是仿射的。V是中心在原點的橢圓的交集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表示不可調節的變量，v表示可調節的變量。假設目標函數是確定的，獨立于可調節的變量V,則相應的錐優化問題為mincTuUu Zv b K,K是一個錐。則相應于不

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

20、節的部分,束可以表不為|U u Z v b ， eTu 門v d (*),若v w W ,則上面的約束即為仿射可調節的約束。下面分成兩種情況來討論，一種是固定的recourse,即Z是確定的，一種是可變的recourse ,即Z是不確定的。在第一種情況下，如果約束由(*)表達，擾動集合為中心在原點的橢圓的交集，如果存在k 0,k 1,K和0使得下式成立，則會存在一個解u,v w W 滿足(*),對于所有的擾動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在第二種情況下，如果擾動很小，使得二次項可以被忽略，則可以用上面的半定規劃來近似。如果二次項不能夠被忽略，則需要增加一些變量后能夠用一個半定規劃來近似。2.3魯棒凸優化2.3.1 魯棒凸二次約束的規劃問題一個凸二次約束的規劃問題為mincTxTTs.tx Qix 2qi x i 0,i 1,., p其中x為決策向量，c Rn, i R,qiRn,Qi Rn n。 0為參數。上面的這個問題可以轉化為一個二階的錐規劃問題 .Tmin c x1 i2qTx, i 1,., p2Vix s.tt(1 i

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

23、k個二階錐約束。 對于離散集合的凸包為kkSa (Q,q, ):(Q,q, ) j(Qj,qj, j),Qj 0, j 0, j,j 1xTQx 2qTx0, (Q,q, ) Sa 等價于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,當且僅當存在著Rk ,使得bT02Vx stT T(1 i 2qTx AT

24、 )2qTx AT , i 1,.,p其中 Aj 是 A的第 j 列，Qj VjTVj, j1,.,ko2數約束的不確定的集合Sc (Q,q, ):(Q,q, ) (Q。，0)Uj(Qj,qj, j 1j),Qj0,u0, u p 1一個決策向量x Rn滿足魯棒約束xTQx 2qTx0 ,對于所有的(Q,q, ) Sc,當且k_僅當存在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二次項和錐項的不確定性是獨立的，即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一個決策向量x Rn滿足魯棒約束xTQx 2qTx0,對于所有的（Q,q, ） Sd ,當且k_僅當存在f, g R和 0 ,滿足gj 2qTx j, j 1,.,k,fj, i 1,.,k2VoX11 V, f q g s一個決策向量x Rn滿足魯棒約束xTQx 2qTx0,對于所有的（Q,q, ） Se,當且僅當存在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二次約束的二次規劃的魯棒解對于一個非凸的二次約束

27、的二次優化問題min f0(x)s.t fk(x) 0,k 1,.,m,x C其中C Rn是一個多面體，并且包含在a,b a x b Rn中，每個fk(x),k 0,1，mRn的形式為kk 2kfk(x)qxxjc xidix a。i jii任何一個二次多項式可以寫成兩個正系數的二次多項式的差，一個一般的(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,則問題可以轉化為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 ,所有的系數為正的。g(x) min (Uk (x) Vk(x),并且Uk(x), Vk(x)為單調遞增的二次函數使得 k 1,.,mi d'xibk因為它對一個小的擾動非常的不穩kk 2gk(x)jCijXxjiCi x由于孤立的最優解即使是可計算的，但是它是難于實施，定，因而，從實際的觀點來看，只有非孤立的可行解有意義。Essential最優解f(x ) min f (x) x S, S表示所以非孤立的可行解的集合。Essen

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

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

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

32、的投資組合集合則兩階段的效用極大化投資模型為mmi i*T ijmax i ju( r )i1 j1s.tTe 1rijRn表示如果scenario i出現在第一階段，scenario j出現在第二階段ij 表示條件概率scenario j 出現在第二階段在scenario i 出現在第一階段的條件下的概率。i 第二階段允許的投資組合則上面的問題可以寫成*是第二階段的recourse問題的最優解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假設可行集為凸集T i iiT令 ( 1,., m ) ，( 1 ,., m ) ， 且由定義可知為非負的向量Te 1, iT e 1問題(P2)是可分的，則可得mmaxi1mi iT ijmax ju( r )i i1s.t.iT Tr,i iTi 1,2,., m1,u(g) 是凹的，則上面的問題為凸規劃。單階段模型的魯棒規劃模型確定的情景樹有兩個缺點：一個是每個情境中收益的模糊性，一個是每個情景發生的條件概率的模糊性。實際上在我們的模型中用到的收益向量為估計值。并且我們并不知道確切我們可以得到的收益為多少，但是根據統計分析，我們知道實際的值離我們估計的值不遠

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

35、R w)。模糊集合是橢球形的：Rm Te1,%,ViriRn(rii%)TQi(ri幽i2,i 1,m為了簡便，假設 Qi是單位矩陣U y Rm yTe0, yi i nV r Rri%i, i1,m則原模型可變形為max(R Tr%)2s.t則相應的魯棒規劃模型為maxs.t進一步變形為利用結論t0m1(%將上面的規劃變為i 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對于一個一般的模型通過增加變量變為如果DTHmin 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,個凸集，則它的齊次錐是則可以得到如下的凸表示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映射到區間T%i| |, T% i| |,則上述模型等價于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 給出一個基于 worse-case的方法。在一個簡單的情況下，相 應魯棒優化問題是一個標準的二次規劃問題，在大多數情況下，這個問題可以轉化為一個鞍點問題。利用 2003年Handors

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

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

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

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

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

43、表示一階段和二階段結束后的凈資產收益。是有限概率空間上(，F , P)的離散的隨機變量。假設市場的發展是離散的scenario樹。1rn表不隨機變重r相應于第一層scenario樹的第n個干點的頭現。基于最大的期望 end-of-horizon組合值的沒有交易費用的兩階段組合選擇模型的隨機規劃為：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的可分性，上面的優化問題等價

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以上的模型假設決策者是風險中立的，Mulvey,Vanderbei and Zenios建議通過由一個參數控制給目標函數增加一個風險項得到兩階段的魯棒隨機規劃。他們的模型為mgxPnQn(x0)f (ri2)Tx1,(r；)Tx1(N) eTx0 1,x00(4)x n N2則可分離的魯棒優化模型為./ 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 ,上式對能夠給出當兩階段的組合決策問題對于recourse問題不是最優時的最優解。 如果f是一個非減的函數， 0 ,則上面的兩個問題時等價的。Takriti and Ahmed利用了一個分段二次的方差度量f(t) n(R tn)2 ,其中R*是目標函數值。t是一組離散的隨機變量，具有實 n

46、 N2現 t1,t2,.,tN2 ,而 1, 2，.，N 是相應的概率。為了是計算方便是所得的問題是一個線性規劃，采用一個分段線性的方差測度f(t) n(R tn) n心它仍然滿足非減的條件。則我們的問題變為2、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可以將上面的模型推廣到三階段的情況。在這篇文章中作者還給出了包含線性交易費用的模型。1，

47、一 yn表示一階段買入資產的數量，1 ,i表示一階段買入一美元的資產的交易費1Zn表示一階段賣出資產的數量，1Vi1表示一階段賣出一美元的資產的交易費11xni表示x：的第i個分量則對于風險資產 x：i rnix°i y：i z；i, i 1,.,mmm對于無風險資產 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）：滿足上面的三個方程帶有交易成本的魯棒兩階段的投資組合選擇的模型為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給出 了一個多階段的組合選擇問題的魯棒建模方法。假設有n種類型的資產i 1,.,n和現金（n 1）。L個投資階段。目標是控制這些資產的一個投資組合。x'表示投資組合中資產i在階段l開始時的數量。xl可以有下列的方程給出:.l l 1 l 1 l li n 時，xi n xi小 Zil 1 l 1l 1 一ri xi是來自前一個階段的數量，ri0表示資產收益。£表示在階

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