鲁棒优化的方法及应用

鲁棒优化的方法及应用杨威在实际的优化中决策过程中，我们经常遇到这样的情形，数据是不确定的或者是非精确的；最优解不易计算，即使计算的非常精确，但是很难准确的实施；对于数据的一个小的扰动可能导致解是不可行。鲁棒优化是一个建模技术，可以处理数据不确定但属于一个不确定集合的优化问题。早在19世纪70年代，Soyster就是最早开始研究鲁棒优化问题的学者之一，他的文章给出了当约束矩阵的列向量属于一个椭球形不确定的集合时的鲁棒线性优化问题。几年以后Falk沿着这条思路做了非精确的线性规划。在以后的很长的一段时间里，鲁棒优化方面都没有新的成果出现。直到19世纪末，Ben-Tal,Nemirovski的工作以及这时计算技术的发展，尤其是对于半定优化和凸优化内点算法的发展，使得鲁棒优化又成为一个研究的热点。一个一般的数学规划的形式为minxoeR，xeRnminxoeR，xeRn{Xo：fo(匕)-i其中x为设计向量，f为目标函数，f，f，•••，f是问题的结构元素。g表示属于0 1 2m特定问题的数据。U是数据空间中的某个不确定的集合。对于一个不确定问题的相应的鲁棒问题为min{x:f(x,g)-x<0,f(x,g)<0,i=1,...,m,VgwU}xeR,xeRn0 0 0 ，0这个问题的可行解和最优解分别称为不确定问题的鲁棒可行和鲁棒最优解。这篇文章主要回顾了鲁棒优化的基本算法，目前的最新的研究结果及在经济上的应用。鲁棒优化的基本方法1.1鲁棒线性规划—个不确定线性规划{min{CTx:Ax>b}|(C,A,b)eUuRnXRmxnxRm}所对应的鲁x棒优化问题为min{t:t>cTx,Ax>b,(c,A,b)eU}，如果不确定的集合是一个计算上易处x理的问题，则这个线性规划也是—个计算上易处理的问题。并且有下列的结论：假设不确定的集合由一个有界的集合Z={g}uRn的仿射像给出，如果Z是1线性不等式约束系统构成Pg<P，则不确定线性规划的鲁棒规划等价于一个线性规划问题。2由锥二次不等式系统给出||pg-P<q疋-r,i=h…,M，则不确定线性规划的鲁棒规i i2i i划等价于—个锥二次的问题。3由线性矩阵不等式系统给出P0+^gP>0，则所导致的问题为一个半定规划问题。0 iii=1鲁棒二次规划

考虑一个不确定的凸二次约束问题{min{cTx:xtAx<2bTx+c,i=1,...,m}(A,b,c)meU}i i i iiii=1x对于这样的一个问题，即使不确定集合的结够很简单，也会导致NP难的问题，所以对于这种问题的处理通常是采用它的近似的鲁棒规划问题。考虑一个不确定的优化问题P={min{cTx:F(xg)<0}|geU}，假设不确定集合为xU=gn+V，而gn表示名义的数据，而V表示一个扰动的集合，假设V是一个包含原点的凸紧集。不确定问题P可以看成是一个不确定问题的参数族P={min{cTx:F(x,g)<0}geU=gn+pV}，p>0表示不确定的水平p 一具有椭圆不确定性的不确定的凸二次规划问题的近似鲁棒问题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则问题可一转化为一个半定规划问题mincTx2XTbn+cnmincTx2XTbn+cn一艺九ii ijj=1C+xTbi...二+XTbL2i2[AnX]TiC+xTbi2iM二+XTbL2 iAnxi艺九Qijij=1[A1x]T

iM[ALx]T

iA1xLALx

ii具有椭圆不确定集合的不确定锥二次问题的近似鲁棒规划考虑不确定锥二次规划{min{cTx:||Ax+b||<atx+P,i=1,...,m}{(A,b,a,P)}meU}X i i2 i i iiiii=1它的约束为逐侧的不确定U=<(A,b,a,卩)}miiiii=1TOC\o"1-5"\h\z、U=<(A,b,a,卩)}miiiii=1{a,卩}mii i=1 丿它的左侧的不确定的集合是一个椭圆Uleft={{(A,b)=(An,bn)+ii ii liii=1 jl=1

其中Q>0,丈Qf0jjj=1右侧的不确定集合是有界的，它的半定表示为(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）为线性映射。则半定规划为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鲁棒半定规划一个不确定的半定规划的鲁棒规划为{min{cTx{min{cTx:A+LxA>0}{(A A)}0 ii ~x i=1半定规划的近似鲁棒问题m0n i=1GU｝由一个箱式不确定集合影响的不确定U={(AA)=(AnU={(AA)=(AnAn)+Lg0 n 0 nl=1则半定规划的近似的鲁棒优化为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}由一个球不确定集合影响的不确定半定规划的近似鲁棒问题U={（A，…，A）=（An，…，An）+tg（A1，…，A1）|引<1}n 1 0 n n

l=1则半定规划问题为cTx:（GcTx:（GA[x]1A[x]2MA[x]A[x]L12>0,F+G<2（An+FxAn）>0jj

j=1IAL[x]具有易处理的鲁棒counterparts的不确定线性规划。如果多胞形是由有限集合的凸包给出的，则鲁棒规划为min0x:Ai+才xAi>0,1=1，...，L}x 0 j=1jj鲁棒优化的几种新的方法鲁棒规划的最近的研究包括了对于可调节的鲁棒优化的研究以及对于鲁棒凸优化的研究。2.1不确定的线性规划的可调节的鲁棒解不确定线性规划为LP{mincTu:Uu+Vv<b}匚=UVbeZ，其中不确定集合Zu，v [U，V，b]ZZuRnXRm“XRm是一>非空的紧的凸集，V称为recourse矩阵。当V是确定的情况下，则称相应的不确定线性规划为固定recourse的。定义：线性规划LP的鲁棒counterpart为(RC):min{cTu:3vV(©=[U，V，b]eZ):Uu+Vv<b}，u则它的可调节的鲁棒counterpart为(ARC):min{cTu:V(©=[U，V，b]eZ)，3v:Uu+Vv<b}。u可调节的鲁棒规划比一般的鲁棒规划灵活，但是同时它也比一般的鲁棒规划难解。对于一个不确定线性规划的鲁棒规划是一个计算上易处理的问题，然而它相应的可调节的鲁棒规划却是不易处理的问题。但是如果不确定集合是有限集合的凸包，则固定recourse的ARC是通常的线性规划。从实际的应用来看，只有当原不确定问题的鲁棒counterpart在计算上容易处理的时候，鲁棒优化方法才有意义。当可调节的变量是数据的仿射函数时，可以得到一^计算上易处理的鲁棒counterpart.对于LP的仿射可调节的鲁棒counterpart(AARC)可以表示为(AARC):min{cTu:Uu+V(w+W匚)<b，V(匚=[U，V，b]eZ)}。u，w，W如果Z是一个计算上易处理的集合，则在固定recourse的情况下，LPZ的仿射可调节

的鲁棒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的仿射可调节的鲁棒counterpart(AARC)是-个锥二次或半定规划。如果recourse也是可变的，则AARC是不易处理的问题，这时采用它的近似形式。在简单椭圆不确定集合的情况下，AARC等价于一个半定规划。当扰动的集合是一个中心在原点的箱式集合或者是一个关于原点对称的多胞形集合，则AARC可以有一个半定规划来近似。对于多期的决策问题也是一个可调节的鲁棒优化问题。考虑一个两期的决策问题infinff(u,v,p)mgUvgV其中P是不确定的，但属于一个闭的有界的不确定集合。可行集V依赖于u和参数p。则可以表示为V(u,p)，或V(p)。可调节的鲁棒counterpart问题可以表示为uinf{t:VpeP,3veV(u,p):f(u,v,p)<t}，ueU,t可以等价的表示为infsupinff(u,v,p)。ueUpePveV(u,p)如果P包含有限数量的元素，P={匕,p2，…,p,}，则对于每个p.eP，都存在着相应的12kiv满足上面的问题。则问题可以转化为一个等价的单层优化问题iinftu,v1,...,vk,ts.t.f(u,v,p)<t,i=1,...,kii

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

ii这样的一个单层的优化问题对于许多类的函数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在这种情况下，问题等价于一个二次约束的优化问题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)。则问题转化为一U vwV/p) peconv(P)U pePU个单层的优化问题。2.2一个锥二次问题的鲁棒解一个锥二次约束的形式为11Ax+b||<ctx+d,[AeRmxn,beRm,ceRn,deR],2或者是等价的形式'Ax+b)e厶+1,L是Lorentz锥。(ctx+d丿假设不确定参数属于一个有界的集合。两种类型的不确定集合常常用到，一个是范数有界的不确定集合，一个是扰动的向量属于一个有界的扰动集合时的结构不确定集合。对于参数的结构不确定为S={(A,b,c,d)=(Ao,bo,co,do)+pf (Az,bi,c,d/),eV}，其中:是描述l=1扰动的向量，P>0是表示扰动幅度的向量，V是扰动集合，Ao,bo,co,d0是名义数值，A1,b,c,di为扰动方向。V是椭圆的交集V=｛匚eRl:匸TQ匸<1,k=1,...,K｝，kQk=1,...,K为对称的正半定矩阵，且工kq是正定的。k k=1k对于一个单侧不确定的锥二次约束，ElGhaoui和Lebret证明了在不确定集合是范数有界的情况下，问题等价于一个锥二次约束。Ben-Tal,Nemirovski给出了在扰动集合是椭圆集合的交集的结构不确定的情况下，如果是简单的椭圆不确定集合,则相应的鲁棒counterpart为一个线性矩阵不等式，在一般的情况下，问题是NP难的，但是可以用线性矩阵不等式来近似。Ben-Tal等研究了逐侧不确定的锥二次约束，即对于影响左侧的不确定独立于影响右侧的不确定。(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"成立。在具有椭球交集的结构不确定的集合的情况下，这两个问题是易处理的。在很多的情况下，影响两侧的不确定集合是相互依存的。比如考虑一个不确定的锥二次约束 ||A[PGx+b[pG||<ct[pGx+d[pG,VQeV, (*)2其中A[z],b[z],c[z],d[z]关于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表示不可调节的变量，v表示可调节的变量。假设目标函数是确定的，独立于可调节的变量v,则相应的锥优化问题为min{cTu|Uu+Zv—beK}，uK是一^锥。则相应于不确定集合S的鲁棒counterpart为min{cTu日v:Uu+Zv—beK,V(U,乙b)eS}u则可调节的鲁棒规划为min{cTu|V(U,Z,b)eS,3v=v(U,Z,b):Uu+Zv—beK,}。u可调节的鲁棒规划比一般的鲁棒灵活一些。但是这样会导致所得到的问题是不易处理的。克服计算上缺点的一个方法是限制可调节的变量为一个仿射函数。v=w+W:，这样得到了仿射可调节的鲁棒规划为min{cTu|Uu+Z(w+WQ)—beK,VQ=(U，乙b)eS}u,w,W对于结构不确定的锥二次约束可表示为IIA[pQ]x+b[PQ]||<CT[pQ]x+d[pQ]，如果2分别用u,v表示x的子向量，并且分别对应于不可调节的部分和可调节的部分，则上面的约束可以表示为束可以表示为IU[pGu+Z[pGv+b[pG||<eT[pGu+fT[pGv+d[PG(**),2若v=w+W:，则上面的约束即为仿射可调节的约束。下面分成两种情况来讨论，一种是固定的 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在第二种情况下，如果扰动很小，使得二次项可以被忽略，则可以用上面的半定规划来近似如果二次项不能够被忽略，则需要增加一些变量后能够用一个半定规划来近似。鲁棒凸优化2.3.1鲁棒凸二次约束的规划问题一个凸二次约束的规划问题为TOC\o"1-5"\h\zmin cTxst xtQx+2qTx+y<0,i=1,...,pi i i其中x为决策向量，ceRn,yeR,qeRn,QeRnxn,Q>0为参数。i i i i上面的这个问题可以转化为一个二阶的锥规划问题mincTxs.t.<1s.t.<1-y-2qTx, i=1,...,pi(1+y+2qTx)ii由于上述的模型对于参数很敏感，所以有必要研究其对应的鲁棒问题一个一般的鲁棒凸二次规划问题为min cTxs.t xtQx+2qTx+y<0,(Q,q,y)eS,i=1,...,pi i i iii i当不确定的集合S,i=1,...,p是椭球时，上面的问题可以转化为一个半定规划问题，这i里我们来确定S的结构，使它能够转化为一个二阶锥规划。分成以下的三种情况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范数约束的不确定的集合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二次约束的二次规划的鲁棒解对于一个非凸的二次约束的二次优化问题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任何一个二次多项式可以写成两个正系数的二次多项式的差，一个一般的(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]，则问题可以转化为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，所有的系数为正的。i<jijij iii iiig(x)=min(u(x)-v(x))，并且u(x),v(x)为单调递增的二次函数使得k k k kk=1,...,mg(x)=工Ckxx+工Ckx2+工dkx+bk i<jijij iii iiik由于孤立的最优解即使是可计算的，但是它是难于实施，因为它对一个小的扰动非常的不稳定，因而，从实际的观点来看，只有非孤立的可行解有意义。Essential最优解f(x*)=min{f(x)xeS*}，S*表示所以非孤立的可行解的集合。£EssentiaI可行解：e»0,xe[a,b]满足g(x)>£。—个非孤立的可行解X称为是Essential£最优解，如果它满足f(X)-£<inf(f(x)|g(x)>£,xe[a,b])寻找EssentiaI£最优解的方法是：从—个初始的EssentiaI可行解，寻找—个更好的Essential可行解，直到不能获得比当前的可行解更好的可行解为止。假设丫为一个Essential可行解的目标函数值，给定£>0:如果f(a)>Y-£，由于f(x)单调递增，则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)算法。鲁棒优化的应用鲁棒优化现在已经应用到了各个研究领域，这里我们主要给出了在金融上的应用。1.RuijunShen和ShuzhongZhang将鲁棒的观点应用于基于scenario树的投资组合的选择问题中，给出了一阶段和两阶段的组合选择模型相应的鲁棒规划问题。这里允许概率分布存在ambiguity•这样的一个问题能够转化为一个有限的锥形式凸规划问题。并且在不允许卖空的情况下，效用函数采用下半方差的负值，参数的不确定集合是椭球形的，则相应的问题可以转化成一个二阶锥规划问题。假设想从n种资产中选择一个投资组合并且持有一段时间，假设初始的财富为1,持有期末有m种可能的结果。即所有的可能的scenario可以通过一个具有m个叶子的—阶段树来表示。假设收益向量的第i个元素表示表示第i种资产的收益。则基于scenario的单阶段的组合选择模型为max£兀u(©Tri)ii=1s.. ©Te=1©eAn是股票的数量,m是每个节点scenario的数量©eRn是持有的股票,是模型中的决策向量rieRn是如果scenarioi出现的话n个股票的收益兀是scenarioi出现的概率

eeRn是分量全为1的向量A是允许的投资组合集合则两阶段的效用极大化投资模型为max区兀忆兀I*TRJ)iji=1 j=ls.t©re=1eARjeRn表示如果seenario1出现在第一阶段，seenarioj出现在第二阶段兀1表示条件概率seenarioj出现在第二阶段在seenario1出现在第一阶段的条件下的概j率。Ai第二阶段允许的投资组合©*是第二阶段的recourse问题的最优解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假设可行集为凸集令兀=(兀，…,兀)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是凹的，则上面的问题为凸规划单阶段模型的鲁棒规划模型确定的情景树有两个缺点：一个是每个情境中收益的模糊性，一个是每个情景发生的条件概率的模糊性。实际上在我们的模型中用到的收益向量为估计值。并且我们并不知道确切的收益为多少，但是根据统计分析，我们知道实际的值离我们估计的值不远，我们可以得到某些置信区间。rwVi（收益的模糊性）兀w口（概率分布的模糊性）假设所有的集合为凸的，紧的，非空的。令y=兀—必,U=n-T%,xwHoywU则鲁棒模型为maxmin (7%+y)u(©Tri)0riwVi,ywU円1 1s.t0Te=10wA两阶段的鲁棒规划模型两阶段的模型中的估计量为魅加，7,%j，令y=兀-7%，U=n-T%，7w^oywU,令yi=7i-7%'，Ui=口—7%i，7wHOyiwUi.maxmin艺(7%+y)maxmin区(%+yi)u(0订讪0riwVi,ywUi=1 0irijwVij,yiwUij=1s.t0iTe=0Tri,Vi=1,2,...,m0iwAi,0Te=10wA单阶段鲁棒模型的有限表示假设条件：1没有卖空A=Rn+2—个半方差的非效用函数d(w)=(R-w)2相当于一个给定的基准组合的下方风险，相应+的效用函数为u(w)=-(R-w)2。+模糊集合是椭球形的：n={7wRm兀Te=1,7-T%|<0},Vi={riwRn(ri-%)TQi(ri-%)<p2},i=1,...,mi为了简便，假设Qi是单位矩阵U={yeRmyTe=0,||y||<9},Vi={rieR^||ri—%』<p},i则原模型可变形为=1,...,mmax0s.t.0Te=10>0艺7%[-(R-0T%)2]ii=1则相应的鲁棒规划模型为maxminrieVi,yeU0Te=10>00s.t.区(%+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、利用结论t0—7%ra、利用结论t0江mi=1(7%+y)a,VyeUoiiit09(a—竺)m丿esoc(m+1)将上面的规划变为mint,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.通过增加变量变为t<£(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映射到区间他T%'-P.||e||,e朋+P.||叫|］，则上述模型等价于区(7%i+yi)(R区(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的方法。在一^简单的情况下，相应鲁棒优化问题是一个标准的二次规划问题，在大多数情况下，这个问题可以转化为一个鞍点问题。利用2003年Handorsson和Tutuncu给出的方法求解。作者给出了在不确定集合为区间时的鲁棒MVO模型，和鲁棒最大夏普比率问题。一个资产分配问题可以表示为在期望收益的下限上极小化方差或最大化一个风险调节的期望收益max卩txmax卩tx一九xtQxxeRn (2s.t.xeZxeRns.t卩TXnR,(1)xeZ其中Z={xeRn£x=1,x>0}ii=1对于期望收益的向量卩和协方差矩阵Q分别取成区间的形式U={卩：卩L<R<pU}U={Q:QL<Q<QU,Q>0}QU={（卩,Q）：peU,QeU」卩Q采用区间型数据的原因：（1）区间的端点对应于历史数据中相应的统计的极值，在分析估计和Scenarios中。（2）建模者可以选择置信水平，以预测区间的形式产生收益和协方差的估计。给定不确定集合U，优化问题（1）（2）对应的鲁棒优化为min{maxxTQx}xeRnQeUQs.tmin卩tx>R, （7） max{min卩tx一九xtQx}（8）MeUy xeZpeU^QeUQxeZ若x*（九）是（8）—个给定正值九的最优解，则x*（九）也是（7）的最优解对于R=min卩tx*（九）。US财政证券可以认为是无风险投资。如果这样的资产包含于资产类中，则有效的投资组合是这个无风险资产和一个风险组合的线性组合。这个最优的组合是具有最高夏普比率的卩tx-r组合。h(x)= f,rf为无风险的已知收益。假设Q是正定的。因为Q是正半定的，xTQx f若它是正定的，则意味着没有冗余的资产。具有最高夏普比率的组合可以通过解决下面的优化问题给出：maxh(x)s.txwZ (11)这个目标函数是一个非线性，非凹的目标函数，难以解决。利用lifting技术对Z进行齐次化：x{xeRn,KeRk>0,-旳U(0,0)，增加(O’。)是为了或得一个凸集。心是一"锥，当Z是一"环的时候，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)是齐次的，则增加规范化的约束不会影响最优解(卩-re)T=1，则问题等价于max^z^ st(x,K)eZ+,(卩一re)=1xTQx f结论：给定一个可行的具有eTx=1性质的组合集Z，VxeZ，这个集合中具有最大夏普比率的解可以通过下面的规划来解：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表示他的最优解，令minmin{maxxTQx}1利用SP算法解决没有期望收益约束的问题xeRn令x表示他的最优解，令mins.txeNR=(pL)TXminmin2，解决问题max{min pTx}，令x表示他的最优解，R =(pL)TxxeNpeUp,QeUQ max max maxA=R-Rmaxmin3选择K，有效前沿上点的数量，Re{R +A/(K—1),R +2A/(K—1),...,R +(n—1)A/(K—1)}，解决问题minminminmin{maxxTQx}xeRnQeUQs..minptx>R,peUpxeN3．MustafaC.Pinar给出了多阶段的组合选择模型。目标是最大化最终期望收益和最小化与一个给定的财富水平的偏差。他们之间是通过一个非负参数来平衡的。利用一个分段的线性罚函数，能够得到线性规划模型，并且能够确保如下阶段的最优性。假设有m+1种资产，前m种为风险的股票，第m+1种为无风险资产，比如现金。x0表示1阶段初的决策向量，xo[i]表示相应的组合种第i种资产的市值。x1表示2阶段初的决策向量,r1,r2表示一阶段和二阶段结束后的净资产收益。是有限概率空间上(°,F,P)的离散的随机变量。假设市场的发展是离散的seenario树。r1表示随机变量r1相应于第一层seenario树的第n个节点的实现。由于recourse由于recourse问题Q(x0),neN的可分性，上面的优化问题等价于n2工p(r2)tx1 eTx0=1,(e)Tx1基于最大的期望end-of-horizon组合值的没有交易费用的两阶段组合选择模型的随机规划为：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以上的模型假设决策者是风险中立的，Mulvey,VanderbeiandZenios建议通过由一^参数控制给目标函数增加一个风险项得到两阶段的鲁棒随机规划。他们的模型为4)max{工pQ(xo)一九f((r2)tx1,...,(r2)tx1 )lerxo=1,xo>o}4)n nn 1 兀(1) N 兀(N)1ox ngN2则可分离的鲁棒优化模型为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问题不是最优时的最优解。如果f是一个非减的函数，九>0，则上面的两个问题时等价的。TakritiandAhmed利用了一^分段二次的方差度量f(t)=工P(R—t)2，其中R*是目标函数值。t是一组离散的随机变量，具有实n*n+ *"叫现1,‘2’…''N，而P1，P2,…'PnI是相应的概率。。N2 N2为了是计算方便是所得的问题是一个线性规划，采用一个分段线性的方差测度f(t)=》P(R—t)n*n+neN2它仍然满足非减的条件。则我们的问题变为max{工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表示一阶段买入资产的数量n卩1表示一阶段买入一美元的资产的交易费iz1表示一阶段卖出资产的数量nV1表示一阶段卖出一美元的资产的交易费ix1[i]表示x1的第i个分量nn则对于风险资产xi[i]=n[i]x0[i]+y1[i]—z1[i]，i=1,...,mnnn nn艺(1—v1)z1[i]ini=1对于无风险资产x1[m+1]=rl[m+1]x0i[m+1]—近艺(1—v1)z1[i]ini=1i=1初始的资金要求为区(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给出了一^多阶段的组合选择问题的鲁棒建模方法。假设有n种类型的资产i=1,…,n和现金（n+1）。L个投资阶段。目标是控制这些资产的一个投资组合。x1表示投资组合中资产i在阶段l开始时的数量。ix1可以有下列的方程给出：ii<n时，xi=ri-ixi-i-yi+ziiii iiri-ixi-i是来自前一个阶段的数量，ri-i>0表示资产收益。ii izi表示在阶段i初买入的资产数量。iyi表示在阶段i初卖出的资产数量。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卖出资产i得到的资产数量，卩i表示交易成本ii i（i+v1）z表示在阶段i买入资产i得到的资产数量，v1表示交易成本ii i应该满足约束y1<y1<y1,i=i,...,n,iiiz<z1<z1,i=i,...,n,~iiixi<yi<xi,i=i,...,n~iii假设约束为简单的约束，即下界为0，上界为无穷大目标是极大化期末财富的总价值V=乙IXL。可得到线性规划模型为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，则新的规划为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其中其中数据的不确定性Al=(1-卩数据的不确定性Al=(1-卩l)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的可测函数，当决策向量实施的时候，数据就是立ii i即可知。不确定线性规划的鲁棒规划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锥二次规划锥二次规划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