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

魯棒優(yōu)化的方法及應(yīng)用楊威在實際的優(yōu)化中決策過程中，我們經(jīng)常遇到這樣的情形，數(shù)據(jù)是不確定的或者是非精確的；最優(yōu)解不易計算，即使計算的非常精確，但是很難準確的實施；對于數(shù)據(jù)的一個小的擾動可能導致解是不可行。魯棒優(yōu)化是一個建模技術(shù)，可以處理數(shù)據(jù)不確定但屬于一個不確定集合的優(yōu)化問題。早在19世紀70年代，Soyster就是最早開始研究魯棒優(yōu)化問題的學者之一，他的文章給出了當約束矩陣的列向量屬于一個橢球形不確定的集合時的魯棒線性優(yōu)化問題。幾年以后Falk沿著這條思路做了非精確的線性規(guī)劃。在以后的很長的一段時間里，魯棒優(yōu)化方面都沒有新的成果出現(xiàn)。直到19世紀末，Ben-Tal,Nemirovski的工作以及這時計算技術(shù)的發(fā)展，尤其是對于半定優(yōu)化和凸優(yōu)化內(nèi)點算法的發(fā)展，使得魯棒優(yōu)化又成為一個研究的熱點。一個一般的數(shù)學規(guī)劃的形式為minxoeR，xeRnminxoeR，xeRn{Xo：fo(匕)-i其中x為設(shè)計向量，f為目標函數(shù)，f，f，???，f是問題的結(jié)構(gòu)元素。g表示屬于0 1 2m特定問題的數(shù)據(jù)。U是數(shù)據(jù)空間中的某個不確定的集合。對于一個不確定問題的相應(yīng)的魯棒問題為min{x:f(x,g)-x<0,f(x,g)<0,i=1,...,m,VgwU}xeR,xeRn0 0 0 ，0這個問題的可行解和最優(yōu)解分別稱為不確定問題的魯棒可行和魯棒最優(yōu)解。這篇文章主要回顧了魯棒優(yōu)化的基本算法，目前的最新的研究結(jié)果及在經(jīng)濟上的應(yīng)用。魯棒優(yōu)化的基本方法1.1魯棒線性規(guī)劃—個不確定線性規(guī)劃{min{CTx:Ax>b}|(C,A,b)eUuRnXRmxnxRm}所對應(yīng)的魯x棒優(yōu)化問題為min{t:t>cTx,Ax>b,(c,A,b)eU}，如果不確定的集合是一個計算上易處x理的問題，則這個線性規(guī)劃也是—個計算上易處理的問題。并且有下列的結(jié)論：假設(shè)不確定的集合由一個有界的集合Z={g}uRn的仿射像給出，如果Z是1線性不等式約束系統(tǒng)構(gòu)成Pg<P，則不確定線性規(guī)劃的魯棒規(guī)劃等價于一個線性規(guī)劃問題。2由錐二次不等式系統(tǒng)給出||pg-P<q疋-r,i=h…,M，則不確定線性規(guī)劃的魯棒規(guī)i i2i i劃等價于—個錐二次的問題。3由線性矩陣不等式系統(tǒng)給出P0+^gP>0，則所導致的問題為一個半定規(guī)劃問題。0 iii=1魯棒二次規(guī)劃

考慮一個不確定的凸二次約束問題{min{cTx:xtAx<2bTx+c,i=1,...,m}(A,b,c)meU}i i i iiii=1x對于這樣的一個問題，即使不確定集合的結(jié)夠很簡單，也會導致NP難的問題，所以對于這種問題的處理通常是采用它的近似的魯棒規(guī)劃問題?？紤]一個不確定的優(yōu)化問題P={min{cTx:F(xg)<0}|geU}，假設(shè)不確定集合為xU=gn+V，而gn表示名義的數(shù)據(jù)，而V表示一個擾動的集合，假設(shè)V是一個包含原點的凸緊集。不確定問題P可以看成是一個不確定問題的參數(shù)族P={min{cTx:F(x,g)<0}geU=gn+pV}，p>0表示不確定的水平p 一具有橢圓不確定性的不確定的凸二次規(guī)劃問題的近似魯棒問題m|gTQg<1,j=1,…,k}i=1 jU={{(c,A,b)=(cn,Am|gTQg<1,j=1,…,k}i=1 jiii iii liiil=1其中Q>0,丈Qf0jjj=1則問題可一轉(zhuǎn)化為一個半定規(guī)劃問題mincTx2XTbn+cnmincTx2XTbn+cn一藝九ii ijj=1C+xTbi...二+XTbL2i2[AnX]TiC+xTbi2iM二+XTbL2 iAnxi藝九Qijij=1[A1x]T

iM[ALx]T

iA1xLALx

ii具有橢圓不確定集合的不確定錐二次問題的近似魯棒規(guī)劃考慮不確定錐二次規(guī)劃{min{cTx:||Ax+b||<atx+P,i=1,...,m}{(A,b,a,P)}meU}X i i2 i i iiiii=1它的約束為逐側(cè)的不確定U=<(A,b,a,卩)}miiiii=1TOC\o"1-5"\h\z、U=<(A,b,a,卩)}miiiii=1{a,卩}mii i=1 丿它的左側(cè)的不確定的集合是一個橢圓Uleft={{(A,b)=(An,bn)+ii ii liii=1 jl=1

其中Q>0,丈Qf0jjj=1右側(cè)的不確定集合是有界的，它的半定表示為(ar,3r)}mhwV}riii=1U(ar,3r)}mhwV}riii=1ii iir=1V={n|3u:Pm)+Q(u)-RV={n|3u:Pm)+Q(u)-R>0},pm）,Q（u）為線性映射。則半定規(guī)劃為min/T-Il九ijj=1[AnX+bn]Tiij=i九Qiji[Aix+bi]tii

MAnX+bniiA1xL

iALx

i[Alx+bL]tiiTIi九>0,i=1,...,m,j=1,...,kijt=xtan+3n+Tr(RV),i=1,...,mi ii i'xta1+31'其中p*其中p*(V)=iXTaR+3R

'i i丿Q*(V)=0,i=1,...,miV>0,i=1,...,mi魯棒半定規(guī)劃一個不確定的半定規(guī)劃的魯棒規(guī)劃為{min{cTx{min{cTx:A+LxA>0}{(A A)}0 ii ~x i=1半定規(guī)劃的近似魯棒問題m0n i=1GU｝由一個箱式不確定集合影響的不確定U={(AA)=(AnU={(AA)=(AnAn)+Lg0 n 0 nl=1則半定規(guī)劃的近似的魯棒優(yōu)化為Xi>A[x]三Al+LxAl,l=1,...,Ll 0 jjj=1Xl>—A[x],l=1,…,LlXlWAl+xAl,l=1,…，L

0 jjj=1mm<x,X1cTx:l=1(AlAl)|引<1}由一個球不確定集合影響的不確定半定規(guī)劃的近似魯棒問題U={（A，…，A）=（An，…，An）+tg（A1，…，A1）|引<1}n 1 0 n n

l=1則半定規(guī)劃問題為cTx:（GcTx:（GA[x]1A[x]2MA[x]A[x]L12>0,F+G<2（An+FxAn）>0jj

j=1IAL[x]具有易處理的魯棒counterparts的不確定線性規(guī)劃。如果多胞形是由有限集合的凸包給出的，則魯棒規(guī)劃為min0x:Ai+才xAi>0,1=1，...，L}x 0 j=1jj魯棒優(yōu)化的幾種新的方法魯棒規(guī)劃的最近的研究包括了對于可調(diào)節(jié)的魯棒優(yōu)化的研究以及對于魯棒凸優(yōu)化的研究。2.1不確定的線性規(guī)劃的可調(diào)節(jié)的魯棒解不確定線性規(guī)劃為LP{mincTu:Uu+Vv<b}匚=UVbeZ，其中不確定集合Zu，v [U，V，b]ZZuRnXRm“XRm是一>非空的緊的凸集，V稱為recourse矩陣。當V是確定的情況下，則稱相應(yīng)的不確定線性規(guī)劃為固定recourse的。定義：線性規(guī)劃LP的魯棒counterpart為(RC):min{cTu:3vV(?=[U，V，b]eZ):Uu+Vv<b}，u則它的可調(diào)節(jié)的魯棒counterpart為(ARC):min{cTu:V(?=[U，V，b]eZ)，3v:Uu+Vv<b}。u可調(diào)節(jié)的魯棒規(guī)劃比一般的魯棒規(guī)劃靈活，但是同時它也比一般的魯棒規(guī)劃難解。對于一個不確定線性規(guī)劃的魯棒規(guī)劃是一個計算上易處理的問題，然而它相應(yīng)的可調(diào)節(jié)的魯棒規(guī)劃卻是不易處理的問題。但是如果不確定集合是有限集合的凸包，則固定recourse的ARC是通常的線性規(guī)劃。從實際的應(yīng)用來看，只有當原不確定問題的魯棒counterpart在計算上容易處理的時候，魯棒優(yōu)化方法才有意義。當可調(diào)節(jié)的變量是數(shù)據(jù)的仿射函數(shù)時，可以得到一^計算上易處理的魯棒counterpart.對于LP的仿射可調(diào)節(jié)的魯棒counterpart(AARC)可以表示為(AARC):min{cTu:Uu+V(w+W匚)<b，V(匚=[U，V，b]eZ)}。u，w，W如果Z是一個計算上易處理的集合，則在固定recourse的情況下，LPZ的仿射可調(diào)節(jié)

的魯棒counterpart(AARC)是一^計算上易處理的問題。如果Z是這樣的一^集合,Z二{[U,V,b]二[U0,V0,bo]+t勺[U,V1,b]:gwN}，N是一個非空的凸緊集。1=1在固定的recourse的情況下，AARC具有這樣的形式min{cmin{ctu:[Uo+u,v0,v1,...,vLU1]u+V[v0+ vi]<11[bo+bi],Vge^}1如果不確定的集合是一個錐表示的，則LPZ的仿射可調(diào)節(jié)的魯棒counterpart(AARC)是-個錐二次或半定規(guī)劃。如果recourse也是可變的，則AARC是不易處理的問題，這時采用它的近似形式。在簡單橢圓不確定集合的情況下，AARC等價于一個半定規(guī)劃。當擾動的集合是一個中心在原點的箱式集合或者是一個關(guān)于原點對稱的多胞形集合，則AARC可以有一個半定規(guī)劃來近似。對于多期的決策問題也是一個可調(diào)節(jié)的魯棒優(yōu)化問題?？紤]一個兩期的決策問題infinff(u,v,p)mgUvgV其中P是不確定的，但屬于一個閉的有界的不確定集合?？尚屑疺依賴于u和參數(shù)p。則可以表示為V(u,p)，或V(p)?？烧{(diào)節(jié)的魯棒counterpart問題可以表示為uinf{t:VpeP,3veV(u,p):f(u,v,p)<t}，ueU,t可以等價的表示為infsupinff(u,v,p)。ueUpePveV(u,p)如果P包含有限數(shù)量的元素，P={匕,p2，…,p,}，則對于每個p.eP，都存在著相應(yīng)的12kiv滿足上面的問題。則問題可以轉(zhuǎn)化為一個等價的單層優(yōu)化問題iinftu,v1,...,vk,ts.t.f(u,v,p)<t,i=1,...,kii

ueU,veV(u,p),i=1,...,k

ii這樣的一個單層的優(yōu)化問題對于許多類的函數(shù)f和集合V(u,p)，這是一個易處理的問題。比如f(u,v,p)=f(u,v,p)，ii0iiU={u:g(u)<0,1=1,...,m},1V(u,p)={v:f(u,v,p)<0,1=1,...,m}ii1ii2其中f(u,v,p)=f(w,p)=wTQ(p)w+q(p)Tw+b(p),1=0,...,mTOC\o"1-5"\h\z. I ? J J ? J C1i i1 iii 1 ii1 ii 1 i2g(u)=utRu+rru+d,1=1,...,m w=(u,v)t,i=1,...,k1 1 1 1 1i i在這種情況下，問題等價于一個二次約束的優(yōu)化問題inftu,v1,...,vk,ts.twtQw+qtw+b<t,i=1,???,ki i0ii0ii0TOC\o"1-5"\h\zutRu+rTu+d<0,l=1,???,m,

ll l 1wtQw+qTtw+b<0,i=1,???,k,l=1,???,m

iili iliil 2如果不確定集合是有限集合p=｛p,p，…,p｝的凸包conv(P)，則考慮下面的問題1 2 kinfsupinff(u,v,p)ueUpeconv(P)veV(u,P)如果g(“)=inff(u,v,p)是擬凸的，則IJmaxg(p)=maxg(p)。則問題轉(zhuǎn)化為一U vwV/p) peconv(P)U pePU個單層的優(yōu)化問題。2.2一個錐二次問題的魯棒解一個錐二次約束的形式為11Ax+b||<ctx+d,[AeRmxn,beRm,ceRn,deR],2或者是等價的形式'Ax+b)e厶+1,L是Lorentz錐。(ctx+d丿假設(shè)不確定參數(shù)屬于一個有界的集合。兩種類型的不確定集合常常用到，一個是范數(shù)有界的不確定集合，一個是擾動的向量屬于一個有界的擾動集合時的結(jié)構(gòu)不確定集合。對于參數(shù)的結(jié)構(gòu)不確定為S={(A,b,c,d)=(Ao,bo,co,do)+pf (Az,bi,c,d/),eV}，其中:是描述l=1擾動的向量，P>0是表示擾動幅度的向量，V是擾動集合，Ao,bo,co,d0是名義數(shù)值，A1,b,c,di為擾動方向。V是橢圓的交集V=｛匚eRl:匸TQ匸<1,k=1,...,K｝，kQk=1,...,K為對稱的正半定矩陣，且工kq是正定的。k k=1k對于一個單側(cè)不確定的錐二次約束，ElGhaoui和Lebret證明了在不確定集合是范數(shù)有界的情況下，問題等價于一個錐二次約束。Ben-Tal,Nemirovski給出了在擾動集合是橢圓集合的交集的結(jié)構(gòu)不確定的情況下，如果是簡單的橢圓不確定集合,則相應(yīng)的魯棒counterpart為一個線性矩陣不等式，在一般的情況下，問題是NP難的，但是可以用線性矩陣不等式來近似。Ben-Tal等研究了逐側(cè)不確定的錐二次約束，即對于影響左側(cè)的不確定獨立于影響右側(cè)的不確定。(A,b,c,d)=｛(A,b,c,d)|(A,b)eU',(c,d)eU"｝，U',U"是相互獨立的集合。則x是問題||Ax+b<cTx+d的可行解，但且僅當存在i，使得IIAx+州2<T,VA,beU'和e<cTx+d,Vc,dgU"成立。在具有橢球交集的結(jié)構(gòu)不確定的集合的情況下，這兩個問題是易處理的。在很多的情況下，影響兩側(cè)的不確定集合是相互依存的。比如考慮一個不確定的錐二次約束 ||A[PGx+b[pG||<ct[pGx+d[pG,VQeV, (*)2其中A[z],b[z],c[z],d[z]關(guān)于z是仿射的。V是中心在原點的橢圓的交集。V二{?eRl:SQq<1,k=1,...,K},Qk=1,...,K為對稱的正半定矩陣，且工KQ是k k k=1 k正定的。如果存在著九、0,卩、0，且滿足下式，則x滿足(*)式。kv(x)一卩一工九 pWT[x] -UT[x]kkppw[x] 乙九Q -pUT[x]kkk—u[x] —pU[x] |LXI其中v[x]=（co）tx+do,W[x]=2[（C1）Tx+dj'（CL）Tx+dL]T,u[x]= [Aox+bo],2U[x]= [Aix+bi,...,Alx+bL].2如果向量x被分成兩部分，x=(UT,VT)t，其中u表示不可調(diào)節(jié)的變量，v表示可調(diào)節(jié)的變量。假設(shè)目標函數(shù)是確定的，獨立于可調(diào)節(jié)的變量v,則相應(yīng)的錐優(yōu)化問題為min{cTu|Uu+Zv—beK}，uK是一^錐。則相應(yīng)于不確定集合S的魯棒counterpart為min{cTu日v:Uu+Zv—beK,V(U,乙b)eS}u則可調(diào)節(jié)的魯棒規(guī)劃為min{cTu|V(U,Z,b)eS,3v=v(U,Z,b):Uu+Zv—beK,}。u可調(diào)節(jié)的魯棒規(guī)劃比一般的魯棒靈活一些。但是這樣會導致所得到的問題是不易處理的?？朔嬎闵先秉c的一個方法是限制可調(diào)節(jié)的變量為一個仿射函數(shù)。v=w+W:，這樣得到了仿射可調(diào)節(jié)的魯棒規(guī)劃為min{cTu|Uu+Z(w+WQ)—beK,VQ=(U，乙b)eS}u,w,W對于結(jié)構(gòu)不確定的錐二次約束可表示為IIA[pQ]x+b[PQ]||<CT[pQ]x+d[pQ]，如果2分別用u,v表示x的子向量，并且分別對應(yīng)于不可調(diào)節(jié)的部分和可調(diào)節(jié)的部分，則上面的約束可以表示為束可以表示為IU[pGu+Z[pGv+b[pG||<eT[pGu+fT[pGv+d[PG(**),2若v=w+W:，則上面的約束即為仿射可調(diào)節(jié)的約束。下面分成兩種情況來討論，一種是固定的 recourse，即Z是確定的，一種是可變的recourse,即Z是不確定的。在第一種情況下，如果約束由(**)表達，擾動集合為中心在原點的橢圓的交集，如果存在\=0,k二1,…,K和r>0使得下式成立，則會存在一個解ku,V=w+PW?滿足(**)，對于所有的擾動匚eV成立，a[u,w,a[u,w,VW]一r—九kk-2卩[u,w,W]厶-~a%_u,w,w]2p卩T[u,w,W]工九Qkkk-p&[u,w,W]-—a%T[u,w,w]2-[u,w,W]>0^2rI其中a%=Uou+Zw+bo，曲=Uiu+ZW+bi,l=1,...,Lla=e0Tu+fTw+d0,0i=eiTu+ftW+di,l=1,...,Ll在第二種情況下，如果擾動很小，使得二次項可以被忽略，則可以用上面的半定規(guī)劃來近似如果二次項不能夠被忽略，則需要增加一些變量后能夠用一個半定規(guī)劃來近似。魯棒凸優(yōu)化2.3.1魯棒凸二次約束的規(guī)劃問題一個凸二次約束的規(guī)劃問題為TOC\o"1-5"\h\zmin cTxst xtQx+2qTx+y<0,i=1,...,pi i i其中x為決策向量，ceRn,yeR,qeRn,QeRnxn,Q>0為參數(shù)。i i i i上面的這個問題可以轉(zhuǎn)化為一個二階的錐規(guī)劃問題mincTxs.t.<1s.t.<1-y-2qTx, i=1,...,pi(1+y+2qTx)ii由于上述的模型對于參數(shù)很敏感，所以有必要研究其對應(yīng)的魯棒問題一個一般的魯棒凸二次規(guī)劃問題為min cTxs.t xtQx+2qTx+y<0,(Q,q,y)eS,i=1,...,pi i i iii i當不確定的集合S,i=1,...,p是橢球時，上面的問題可以轉(zhuǎn)化為一個半定規(guī)劃問題，這i里我們來確定S的結(jié)構(gòu)，使它能夠轉(zhuǎn)化為一個二階錐規(guī)劃。分成以下的三種情況i1離散集合和多邊形不確定集合對于離散形式的集合定義為S={(Q,q,y)：(Q,q,y)=(Q,q,y),Q>0,j=1,...,k},a jjjj魯棒約束xtQx+2qTx+y<0,(Q,q,y)eS等價于K個凸二次約束axtQx+2qTx+y<0,Vj=1,...,k。TOC\o"1-5"\h\zi i i或者等價的k個二階錐約束。對于離散集合的凸包為S={(Q,q,y)：(Q,q,y)=工九(Q,q,y),Q>0,九>0,Vj,工九=1}，則魯棒約束a jjjjj j jj=1 j=1xTQx+2qTx+y<0,(Q,q,y)eS等價于a工九xtQx+2qTx+y<0,九>0,Vj,工九=1ji i i j jj=1 j=1將上面的兩種情況下的集合推廣到多邊形的不確定集合S={(Q,q,y)：(Q,q,y)=工九(Q,q,y),Q>0,j= k,AX=b,X>0}。b jjjjjj=1如果決策向量xeRn滿足魯棒約束xtQx+2qTx+y<0，對于所有的(Q,q,y)eS，當且b僅當存在著卩丘Rk，使得bT卩<0s.t|[(1+y+2；：-AtA)]卜1-yi-2qiTx+Al i=1,...,p其中A.是A的第j列，Q=VtV,j=1,…,kj jjj2范數(shù)約束的不確定的集合s={(q,q,y)：(Q,q,y)=(Q0,q0,y0)+EUj(Qj,q,y/Qj>0,u>0,Wl<1}j=1—個決策向量xeRn滿足魯棒約束xtQx+2qTx+y<0，對于所有的(Q,q,y)eS，當且c

僅當存在feRk和0，滿足+<1<1-Y-2qTx+f,i=1,...,pi i ji(1+Y+2qTx-f)i i j2Vx1-u<1+v,||f|| <-u-2qrx-Y2Vx1-u<1+v,||f|| <-u-2qrx-Y0，其中-p+*=1Q=VTV，j=0,...,kjjj二次項和錐項的不確定性是獨立的，即S={(Q,q,Y)：(Q,q,Y)=(Q,q,Y)+》u(Q,q,Y),Qd 0 0 0 jjjjjj=1(q,Y)=(q,Y)+》v(q,Y),||v||<1}0 0 jjj rj=1—個決策向量xeRn滿足魯棒約束xtQx+2qTx+丫<0,對于所有的(Q,q,Y)gS,當且d僅當存在f,gRk和vn0，滿足g=2qTx+Y,j=1,...,kjjj2Vx1-u<1+v，f+||g||q3因子化的不確定的集合如果不確定的集合定義為2Vxi(1-f)

j<-u-2qTx-Y，其中-+-=10 0pqQ=VTFV,FgRmxm,VeRmxnF=F+A,A=At,||N-2AN-2<n,F>0,N>0(Q,q,Y)： 00=JWtGW<p,Vi,G>0胃i i iq=q0+geRn，治』=JgTSg<6,S>01s—個決策向量xeRn滿足魯棒約束xtQx+2qTX+Y<0，對于所有的(Q，q,Y)eS，當且eV=V+A,W0僅當存在t,vQ,reR,ueRn,weRm,teRm，使得下式成立+1t>0,v>t+1Tt,c< ,rnpu,u>x,u>-x,j=1,???,n九(H) i=1iijjjjmax26S-2x<-v-2qTx-Y2r<a+2r<a+t,2wi(九-G-T)ii<(九-g+t),i=1,...,mii其中H=G-2(F+nN)G-2,H=QtAq是H的譜分解，A=diag(),11九(H)=max {X}，w=QtF2G2Vx。max 1<i<mi 02.3.2二次約束的二次規(guī)劃的魯棒解對于一個非凸的二次約束的二次優(yōu)化問題minf(x)0s.t.f(x)>0,k=1,...,m,xeCk其中CuRn是一個多面體，并且包含在[a,b]={a<x<b}uRn中，每個+f(x),k=0,1,...,muRn的形式為k+f(x)=工ckxx+工ckx2+工dkx+b。k ijij ii iiki<j i i任何一個二次多項式可以寫成兩個正系數(shù)的二次多項式的差，一個一般的(QQP)可以寫成minf+(x)-f一(x)00s.t f+(x)-f-(x)>0,k=1,.??,m,xeCkk由于f~(a)<f~(x)<f~(b),Vxe[a，b]，則問題可以轉(zhuǎn)化為minf+(x)+t0s.t.t+f-(x)>00f+(x)-f-(x)>0,k=1,...,m,xeCkk-f-(b)<t<-f-(a)00通過變換記號，可以得到這樣的形式min{f(x)|g(x)>0,xe[a,b]}其中f(x)=工cxx+工cx2+工dx，所有的系數(shù)為正的。i<jijij iii iiig(x)=min(u(x)-v(x))，并且u(x),v(x)為單調(diào)遞增的二次函數(shù)使得k k k kk=1,...,mg(x)=工Ckxx+工Ckx2+工dkx+bk i<jijij iii iiik由于孤立的最優(yōu)解即使是可計算的，但是它是難于實施，因為它對一個小的擾動非常的不穩(wěn)定，因而，從實際的觀點來看，只有非孤立的可行解有意義。Essential最優(yōu)解f(x*)=min{f(x)xeS*}，S*表示所以非孤立的可行解的集合?！闑ssentiaI可行解：e?0,xe[a,b]滿足g(x)>￡?！獋€非孤立的可行解X稱為是Essential￡最優(yōu)解，如果它滿足f(X)-￡<inf(f(x)|g(x)>￡,xe[a,b])尋找EssentiaI￡最優(yōu)解的方法是：從—個初始的EssentiaI可行解，尋找—個更好的Essential可行解，直到不能獲得比當前的可行解更好的可行解為止。假設(shè)丫為一個Essential可行解的目標函數(shù)值，給定￡>0:如果f(a)>Y-￡，由于f(x)單調(diào)遞增，則f(x)>Y-￡,Vxe[a,b]如果f(a)<Y-￡，g(a)>0，則a即為一^Essential可行解如果f(a)<Y-￡，g(a)<0，則需要考慮一個輔助的問題(Q/Y)max{g(x)|f(x)<y-￡,xe[a,b]}(Q/Y)求解采用分支定界的方法。這篇文章中給出了一^successiveincumbenttranscending(SIT)算法。魯棒優(yōu)化的應(yīng)用魯棒優(yōu)化現(xiàn)在已經(jīng)應(yīng)用到了各個研究領(lǐng)域，這里我們主要給出了在金融上的應(yīng)用。1.RuijunShen和ShuzhongZhang將魯棒的觀點應(yīng)用于基于scenario樹的投資組合的選擇問題中，給出了一階段和兩階段的組合選擇模型相應(yīng)的魯棒規(guī)劃問題。這里允許概率分布存在ambiguity?這樣的一個問題能夠轉(zhuǎn)化為一個有限的錐形式凸規(guī)劃問題。并且在不允許賣空的情況下，效用函數(shù)采用下半方差的負值，參數(shù)的不確定集合是橢球形的，則相應(yīng)的問題可以轉(zhuǎn)化成一個二階錐規(guī)劃問題。假設(shè)想從n種資產(chǎn)中選擇一個投資組合并且持有一段時間，假設(shè)初始的財富為1,持有期末有m種可能的結(jié)果。即所有的可能的scenario可以通過一個具有m個葉子的—階段樹來表示。假設(shè)收益向量的第i個元素表示表示第i種資產(chǎn)的收益。則基于scenario的單階段的組合選擇模型為max￡兀u(?Tri)ii=1s.. ?Te=1?eAn是股票的數(shù)量,m是每個節(jié)點scenario的數(shù)量?eRn是持有的股票,是模型中的決策向量rieRn是如果scenarioi出現(xiàn)的話n個股票的收益兀是scenarioi出現(xiàn)的概率

eeRn是分量全為1的向量A是允許的投資組合集合則兩階段的效用極大化投資模型為max區(qū)兀憶兀I*TRJ)iji=1 j=ls.t?re=1eARjeRn表示如果seenario1出現(xiàn)在第一階段，seenarioj出現(xiàn)在第二階段兀1表示條件概率seenarioj出現(xiàn)在第二階段在seenario1出現(xiàn)在第一階段的條件下的概j率。Ai第二階段允許的投資組合?*是第二階段的recourse問題的最優(yōu)解max￡兀iu(?irrij)ji=1s.t?ire=?tr,Vi=1,2,...,m則上面的問題可以寫成(P2)?ieAi則上面的問題可以寫成(P2)max max￡兀iu(?irrij)?i?j

i=1 i i=1s.t.?ire=?rri,Vi=1,2,...,m?ieAis.t.?re=1?eA假設(shè)可行集為凸集令兀=(兀，…,兀)r，兀1=(兀1，…,兀1)r,且由定義可知兀,兀1為非負的向量兀Te=兀iTe=11m 1m問題(P2)是可分的，則可得max?￡兀max￡兀iu(?iTrij)i?ji=1 ?i i=1s.t.?iTe=?Tri,Vi=1,2,...,m?ieAi,?Te=1,?eA由于u(g是凹的，則上面的問題為凸規(guī)劃單階段模型的魯棒規(guī)劃模型確定的情景樹有兩個缺點：一個是每個情境中收益的模糊性，一個是每個情景發(fā)生的條件概率的模糊性。實際上在我們的模型中用到的收益向量為估計值。并且我們并不知道確切的收益為多少，但是根據(jù)統(tǒng)計分析，我們知道實際的值離我們估計的值不遠，我們可以得到某些置信區(qū)間。rwVi（收益的模糊性）兀w口（概率分布的模糊性）假設(shè)所有的集合為凸的，緊的，非空的。令y=?！?U=n-T%,xwHoywU則魯棒模型為maxmin (7%+y)u(?Tri)0riwVi,ywU円1 1s.t0Te=10wA兩階段的魯棒規(guī)劃模型兩階段的模型中的估計量為魅加，7,%j，令y=兀-7%，U=n-T%，7w^oywU,令yi=7i-7%'，Ui=口—7%i，7wHOyiwUi.maxmin藝(7%+y)maxmin區(qū)(%+yi)u(0訂訕0riwVi,ywUi=1 0irijwVij,yiwUij=1s.t0iTe=0Tri,Vi=1,2,...,m0iwAi,0Te=10wA單階段魯棒模型的有限表示假設(shè)條件：1沒有賣空A=Rn+2—個半方差的非效用函數(shù)d(w)=(R-w)2相當于一個給定的基準組合的下方風險，相應(yīng)+的效用函數(shù)為u(w)=-(R-w)2。+模糊集合是橢球形的：n={7wRm兀Te=1,7-T%|<0},Vi={riwRn(ri-%)TQi(ri-%)<p2},i=1,...,mi為了簡便，假設(shè)Qi是單位矩陣U={yeRmyTe=0,||y||<9},Vi={rieR^||ri—%』<p},i則原模型可變形為=1,...,mmax0s.t.0Te=10>0藝7%[-(R-0T%)2]ii=1則相應(yīng)的魯棒規(guī)劃模型為maxminrieVi,yeU0Te=10>00s.t.區(qū)(%+y)[—(R—0T%')2]i i +i=1進一步變形為min0,t1,t0s.t.t>max(?%+y)rt0yeUt>max(R—0Tr%i)2irieVi0Te=1,+0>0min0,t1,t0s.t t>max(7%+y)Tt0eyeUt>T2,iiT>max(R—0Tr%i)2irieViT>0i0Te=1,—7%ra、利用結(jié)論t0—7%ra、利用結(jié)論t0江mi=1(7%+y)a,VyeUoiiit09(a—竺)m丿esoc(m+1)將上面的規(guī)劃變?yōu)閙int,t00t—imint,t00t—i%ra0esoc(3)(t+1)iesoc(m+1),t—1ii‘T—R+0T%-)i esoc(n+1)V p.e 丿it>0,0>0,0re=1i對于一個一般的模型maxmin￡(7%+y)u(0rr-)0reV-,yeU 1 1st0re=10eAmaxt0s.t.0s.t.通過增加變量變?yōu)閠<￡(7%+y)u,VyeU0----=1u<u(w),--w<0rr-,Vr-eV--0re=1, 0eAt>0,-et>0,-eD}

t如果D是一個凸集,則它的齊次錐是H(D)=如果D是一個凸集,Vx丿則可以得到如下的凸表示min—t00‘7%rt—t)oeH(U)*,u<u(w),t丿 - -‘—w)丄-eH(V-)*0丿0>0,0re=1對于多階段的魯棒模型maxmin0r-eV-,yeU￡(7%+y)max---=1￡(7%-+y-)(R—0-rr-j)2jj+j=1min0-r-jeV-j,y-eU-s.t. 0-re=0rr-,V-=1,2,...,m0->0,0re=10>0

因此W:rT”ri把球Vi映射到區(qū)間他T%'-P.||e||,e朋+P.||叫|］，則上述模型等價于區(qū)(7%i+yi)(R區(qū)(7%i+yi)(Rj-?iT%j+i||)2jj+j=1maxmin? rieVi,yeUi i ?i ?i yis.t. ?iTe=w,Vi=1,2,...,mi?in0,?t%-p|?||<w<?t%+p||?||i i i2.R.h.tutuncu,M.Koenig給出一^基于worse-case的方法。在一^簡單的情況下，相應(yīng)魯棒優(yōu)化問題是一個標準的二次規(guī)劃問題，在大多數(shù)情況下，這個問題可以轉(zhuǎn)化為一個鞍點問題。利用2003年Handorsson和Tutuncu給出的方法求解。作者給出了在不確定集合為區(qū)間時的魯棒MVO模型，和魯棒最大夏普比率問題。一個資產(chǎn)分配問題可以表示為在期望收益的下限上極小化方差或最大化一個風險調(diào)節(jié)的期望收益max卩txmax卩tx一九xtQxxeRn (2s.t.xeZxeRns.t卩TXnR,(1)xeZ其中Z={xeRn￡x=1,x>0}ii=1對于期望收益的向量卩和協(xié)方差矩陣Q分別取成區(qū)間的形式U={卩：卩L<R<pU}U={Q:QL<Q<QU,Q>0}QU={（卩,Q）：peU,QeU」卩Q采用區(qū)間型數(shù)據(jù)的原因：（1）區(qū)間的端點對應(yīng)于歷史數(shù)據(jù)中相應(yīng)的統(tǒng)計的極值，在分析估計和Scenarios中。（2）建模者可以選擇置信水平，以預(yù)測區(qū)間的形式產(chǎn)生收益和協(xié)方差的估計。給定不確定集合U，優(yōu)化問題（1）（2）對應(yīng)的魯棒優(yōu)化為min{maxxTQx}xeRnQeUQs.tmin卩tx>R, （7） max{min卩tx一九xtQx}（8）MeUy xeZpeU^QeUQxeZ若x*（九）是（8）—個給定正值九的最優(yōu)解，則x*（九）也是（7）的最優(yōu)解對于R=min卩tx*（九）。US財政證券可以認為是無風險投資。如果這樣的資產(chǎn)包含于資產(chǎn)類中，則有效的投資組合是這個無風險資產(chǎn)和一個風險組合的線性組合。這個最優(yōu)的組合是具有最高夏普比率的卩tx-r組合。h(x)= f,rf為無風險的已知收益。假設(shè)Q是正定的。因為Q是正半定的，xTQx f若它是正定的，則意味著沒有冗余的資產(chǎn)。具有最高夏普比率的組合可以通過解決下面的優(yōu)化問題給出：maxh(x)s.txwZ (11)這個目標函數(shù)是一個非線性，非凹的目標函數(shù)，難以解決。利用lifting技術(shù)對Z進行齊次化：x{xeRn,KeRk>0,-旳U(0,0)，增加(O’。)是為了或得一個凸集。心是一"錐，當Z是一"環(huán)的時候，Z+是一"ice-cream錐，若Z是一"多面體，Z={xAx>b,ex=d}，則Z+={x|Ax-bK>0,ex-dk=0,k>0}。TOC\o"1-5"\h\z卩tx-r (卩t-re)Tx xh(x)= f= f =：g(x)=g(—),Vk>0，由于g(x)是齊次的，則問題等\o"CurrentDocument"WQx HQx K價于maxg(x)s.t(x,K)eZ+，由于g(x)是齊次的，則增加規(guī)范化的約束不會影響最優(yōu)解(卩-re)T=1，則問題等價于max^z^ st(x,K)eZ+,(卩一re)=1xTQx f結(jié)論：給定一個可行的具有eTx=1性質(zhì)的組合集Z，VxeZ，這個集合中具有最大夏普比率的解可以通過下面的規(guī)劃來解：maxxtQxst(x,k)eZ+,(卩一re)T=1 (15)f若x*=(x,k)是(15)的解，則x*=x/k。松弛問題如下：min{maxxTQx}QeUQs..min(卩一re)T>1慶作f(x,K)eZ+魯棒有效前沿的算法：

令x表示他的最優(yōu)解，令minmin{maxxTQx}1利用SP算法解決沒有期望收益約束的問題xeRn令x表示他的最優(yōu)解，令mins.txeNR=(pL)TXminmin2，解決問題max{min pTx}，令x表示他的最優(yōu)解，R =(pL)TxxeNpeUp,QeUQ max max maxA=R-Rmaxmin3選擇K，有效前沿上點的數(shù)量，Re{R +A/(K—1),R +2A/(K—1),...,R +(n—1)A/(K—1)}，解決問題minminminmin{maxxTQx}xeRnQeUQs..minptx>R,peUpxeN3．MustafaC.Pinar給出了多階段的組合選擇模型。目標是最大化最終期望收益和最小化與一個給定的財富水平的偏差。他們之間是通過一個非負參數(shù)來平衡的。利用一個分段的線性罰函數(shù)，能夠得到線性規(guī)劃模型，并且能夠確保如下階段的最優(yōu)性。假設(shè)有m+1種資產(chǎn)，前m種為風險的股票，第m+1種為無風險資產(chǎn)，比如現(xiàn)金。x0表示1階段初的決策向量，xo[i]表示相應(yīng)的組合種第i種資產(chǎn)的市值。x1表示2階段初的決策向量,r1,r2表示一階段和二階段結(jié)束后的凈資產(chǎn)收益。是有限概率空間上(°,F,P)的離散的隨機變量。假設(shè)市場的發(fā)展是離散的seenario樹。r1表示隨機變量r1相應(yīng)于第一層seenario樹的第n個節(jié)點的實現(xiàn)。由于recourse由于recourse問題Q(x0),neN的可分性，上面的優(yōu)化問題等價于n2工p(r2)tx1 eTx0=1,(e)Tx1基于最大的期望end-of-horizon組合值的沒有交易費用的兩階段組合選擇模型的隨機規(guī)劃為：max{工pQ(x0)eTx0=1,x0>0}x0 n nx neN2其中Q(xo)=max{(r2)Tx1(e)rx1=(r1)tx0,x1>0}n 1 n 兀(n) 兀(n) 兀(n) 兀(n)=(r=(r1)tx0,VneN,x0>0,x1>0}兀(n) 兀(n) 1 nx0{xn,neN1}neN2以上的模型假設(shè)決策者是風險中立的，Mulvey,VanderbeiandZenios建議通過由一^參數(shù)控制給目標函數(shù)增加一個風險項得到兩階段的魯棒隨機規(guī)劃。他們的模型為4)max{工pQ(xo)一九f((r2)tx1,...,(r2)tx1 )lerxo=1,xo>o}4)n nn 1 兀(1) N 兀(N)1ox ngN2則可分離的魯棒優(yōu)化模型為max{工p(r2)tx1 一九f((r2)tx1,...,(r2)tx1 )(xo,x1,VngN)gN}TOC\o"1-5"\h\zxo{恥竹}nGN2nn “(n) 1 “(1)N “(N) n 1 ⑸N={(xo,x1,VngN):eTxo=1,(e)Tx1=(r1)Txo,VngN,xo>o,x1>o}n 1 n n 1 nTakritiandAhmed證明了對于任意的方差測度f,上式對能夠給出當兩階段的組合決策問題對于recourse問題不是最優(yōu)時的最優(yōu)解。如果f是一個非減的函數(shù)，九>0，則上面的兩個問題時等價的。TakritiandAhmed利用了一^分段二次的方差度量f(t)=工P(R—t)2，其中R*是目標函數(shù)值。t是一組離散的隨機變量，具有實n*n+ *"叫現(xiàn)1,‘2’…''N，而P1，P2,…'PnI是相應(yīng)的概率。。N2 N2為了是計算方便是所得的問題是一個線性規(guī)劃，采用一個分段線性的方差測度f(t)=》P(R—t)n*n+neN2它仍然滿足非減的條件。則我們的問題變?yōu)閙ax{工p(r2)tx1一九工p(R一(r2)tx1)(xo,x1,VngN)gN}nn 兀(n) n' '' “xo{x1n,ngN1}ngN2 ngN222N={(xo,x1,VngN):eTxo=1,(e)Tx1=(r1)txo,VngN,xo>0,x1>0}n 1 n n 1 n可以將上面的模型推廣到三階段的情況。在這篇文章中作者還給出了包含線性交易費用的模型。y1表示一階段買入資產(chǎn)的數(shù)量n卩1表示一階段買入一美元的資產(chǎn)的交易費iz1表示一階段賣出資產(chǎn)的數(shù)量nV1表示一階段賣出一美元的資產(chǎn)的交易費ix1[i]表示x1的第i個分量nn則對于風險資產(chǎn)xi[i]=n[i]x0[i]+y1[i]—z1[i]，i=1,...,mnnn nn藝(1—v1)z1[i]ini=1對于無風險資產(chǎn)x1[m+1]=rl[m+1]x0i[m+1]—近藝(1—v1)z1[i]ini=1i=1初始的資金要求為區(qū)(1+卩o)xo[i]=1—xo[m+1]ii=1則可行集為T={(x0,xi,yi,zi,VneN):滿足上面的三個方程}nnn 1帶有交易成本的魯棒兩階段的投資組合選擇的模型為max{工p(r2)Txi —九工p(R-(r2)txi)(xo,xi,yi,zi,VneN)eT}?,,, nn 兀(n) n亠 ’' "x0{xin,yin,zin,neNi}neN2 neN2224.AharonBen-Tal,TamarMargalitArkadiNemirovski給出了一^多階段的組合選擇問題的魯棒建模方法。假設(shè)有n種類型的資產(chǎn)i=1,…,n和現(xiàn)金（n+1）。L個投資階段。目標是控制這些資產(chǎn)的一個投資組合。x1表示投資組合中資產(chǎn)i在階段l開始時的數(shù)量。ix1可以有下列的方程給出：ii<n時，xi=ri-ixi-i-yi+ziiii iiri-ixi-i是來自前一個階段的數(shù)量，ri-i>0表示資產(chǎn)收益。ii izi表示在階段i初買入的資產(chǎn)數(shù)量。iyi表示在階段i初賣出的資產(chǎn)數(shù)量。ii=n+i時， i+工（I一卩i）yi一工（i+vi）ziTOC\o"1-5"\h\zn+i n+in+i ii iii=i i=i匕1=ri=ri-ixi-i-yi+zi,i=i,...,n,l=i,...,Liii iin+in+i（i-卩i）yi是在階段i賣出資產(chǎn)i得到的資產(chǎn)數(shù)量，卩i表示交易成本ii i（i+v1）z表示在階段i買入資產(chǎn)i得到的資產(chǎn)數(shù)量，v1表示交易成本ii i應(yīng)該滿足約束y1<y1<y1,i=i,...,n,iiiz<z1<z1,i=i,...,n,~iiixi<yi<xi,i=i,...,n~iii假設(shè)約束為簡單的約束，即下界為0，上界為無窮大目標是極大化期末財富的總價值V=乙IXL?？傻玫骄€性規(guī)劃模型為ZIi=imaxv= rLxLiii=i

xl=rl-1xl-1+工(1-yl)yl一工(1+vl)zln+1 n+1n+1 ii iii=1 i=1yi>0,i=1,...,n,l=1,...,Lizin0,i=1,...,n,l=1,...,Lixi>0,i=1,...,n,n+1,l=1,...,L令g令gl=(Rl)-1xl,i iinl=(Rl)-1yl,ql=(Rl)-1z，其中Rl=rOr1...rl-1，則新的規(guī)劃為i iii ii iiiin+1maxv= RL+1gLii

i=1TOC\o"1-5"\h\zgl=gl-1―叩+ql,i=1,...,n,l=1,...,Lii iigl=gl-1+工Aql-工Blql,l=1,...,Ln+1 n+1 ii iii=1 i=1耳i>0,i=1,...,n,l=1,...,Liql>0,i=1,...,n,l=1,...,Ligl>0,i=1,...,n,n+1,l=1,...,Li其中其中數(shù)據(jù)的不確定性Al=(1-卩數(shù)據(jù)的不確定性Al=(1-卩l(xiāng))Rl/Rl,i i in+1Bl=(1+vl)Rl/Rl,i i in+1maxww<遲Rl+1gliii=1gl=gl-1-nl+ql,i=1,...,n,l=1,...,Lii iigl =gl-1+乙Alnl一乙Blql,l=1,...,Ln+1 n+1 ii iii=1 i=1nl>0,i=1,...,n,l=1,...,Liql>0,i=1,...,n,l=1,...,Ligl>0,i=1,...,n,n+1,l=1,...,Li決策向量gl,nl，…,ql不是實的，是?l的可測函數(shù)，當決策向量實施的時候，數(shù)據(jù)就是立ii i即可知。不確定線性規(guī)劃的魯棒規(guī)劃max{cTx|AX+b>0}XarbX為NX為N維的決策向量，c為精確可知的目標，［A,b］二為不確定的約束矩陣。Larbmmmax{cTx|AX+b>0,V[A,b]eU}XU={(aT,bo)=([ao]t,bo)+ilu([aj]t,bj)utu<1}i II II jllj=1錐二次規(guī)劃錐二次規(guī)劃max{cTx|([ao]t,bo)-||P+aX|>0,l=1,...,m}X l l l l 2'qi'兀 'qi'兀 =gL P='Ai]兀=l$l丿L+1 l<-Bl丿<pT兀-0J兀TVl兀lllVi lmax,l=2,...,L, P=Rl+iL+1aTX+bllL+1L+1<[gL]TVL+1[gL]<^pL+1gLlli=1gi=gi-i—qi+qi,i=1,...,n,/=1,...,Lii iigl+1n+1+gl+1n+1+0l