鲁棒优化的方法及应用

1、URn Rm n Rm所对应的鲁假设不确定的集合由一个有界的集合Z RN的仿射像给出，如果 Z是1线性不等式约束系统构成P,则不确定线性规划的鲁棒规划等价于一个线性规划问题。2由锥二次不等式系统给出Pil2qTPi ,i 1,., M，则不确定线性规划的鲁棒规3由线性矩阵不等式系统给出P。iP 0,则所导致的问题为一个半定规划问题。鲁棒优化的方法及应用杨威在实际的优化中决策过程中，我们经常遇到这样的情形，数据是不确定的或者是非精确 的；最优解不易计算，即使计算的非常精确，但是很难准确的实施；对于数据的一个小的扰动可能导致解是不可行。鲁棒优化是一个建模技术，可以处理数据不确定但属于一个不确定 集

2、合的优化问题。早在19世纪70年代，Soyster就是最早开始研究鲁棒优化问题的学者之一,他的文章给出了当约束矩阵的列向量属于一个椭球形不确定的集合时的鲁棒线性优化问 题。几年以后 Falk沿着这条思路做了非精确的线性规划。在以后的很长的一段时间里，鲁 棒优化方面都没有新的成果出现。直到19世纪末，Ben-Tal,Nemirovski的工作以及这时计算技术的发展，尤其是对于半定优化和凸优化内点算法的发展，使得鲁棒优化又成为一个研究的热点。一个一般的数学规划的形式为min nx0 : f0(x,)人 0, fi(x, )0,i1,.,mx0 R,x Rn其中x为设计向量，f0为目标函数，f1,

3、f2,., fm是问题的结构元素。表示属于特定问题的数据。U是数据空间中的某个不确定的集合。对于一个不确定问题的相应的鲁棒问题为min nxo：fo(x, ) x。 0, fi(x, ) 0,i 1,.,m,X R,x R这个问题的可行解和最优解分别称为不确定问题的鲁棒可行和鲁棒最优解。这篇文章主要回顾了鲁棒优化的基本算法，目前的最新的研究结果及在经济上的应用。1鲁棒优化的基本方法1.1鲁棒线性规划一个不确定线性规划mincTx:Ax b (c,A,b) U棒优化问题为 mint:t cx,Ax b,(c,A,b) U，如果不确定的集合是一个计算上易处X理的问题，则这个线性规划也是一个计算上易

4、处理的问题。并且有下列的结论:划等价于一个锥二次的问题。dim1.2鲁棒二次规划精选文库3考虑一个不确定的凸二次约束问题min cTx: xT Aix 2$x c ,i 1,.,m (Ai, bi,ci )mU对于这样的一个问题，即使不确定集合的结够很简单，也会导致 于这种问题的处理通常是采用它的近似的鲁棒规划问题。考虑一个不确定的优化问题P mincTx:F(x, ) 0XNP难的问题，所以对U，假设不确定集合为U n V，而n表示名义的数据，而 V表示一个扰动的集合，假设 V是一个包含原点的凸紧集。不确定问题P可以看成是一个不确定问题的参数族P mincTx:F(x, )0XV，0表示不确

5、定的水平。U (Ci,A,bi) (Cin,An,bn),l - l . I、ml ( ci , Ai , bi ) i 1 1TQj1,j1,，ks.tC T, n2x biijLT 1 cX b .2T. LXr A n -TA X1CL2MLCL2xTbi1T. LX bikijQij 1-.1-TAxM_ . L .TA X0,i1,., mAinxmin cTx:XAx bi|2Ti Xi,i1,.,m(Ai , bi , i ,i)im1UU(A,bi, i, i)m1 Ai, bi i 1 i,昇1广U rightUleft (A,b) (Ain,bin)Li(l,bl)mil

6、1TQj1,j1,.,k具有椭圆不确定性的不确定的凸二次规划问题的近似鲁棒问题k其中 Qj 0, Qj f 0j 1则问题可一转化为一个半定规划问题Tmin c XAL AiLx具有椭圆不确定集合的不确定锥二次问题的近似鲁棒规划 考虑不确定锥二次规划它的约束为逐侧的不确定它的左侧的不确定的集合是一个椭圆精选文库4右侧的不确定集合是有界的,它的半定表示为uright ( i,i)(in,in)Rr( ir,：)1r 1Vu:P(Q(u)0, P( ),Q(u)为线性映射。则半定规划为mincT Xkijs.t.AinxbinTA/xbi1TM0, i 1,., mAiLxbiLTij其中bin0

7、,ixTP*(Vi)AIXLAiLx1,.,m, jniXT1,.,k1iMRiTr(RV),i 1,.,m1i,i 1,.,mRiQ*(Vi)Vi0,i1.3鲁棒半定规划一个不确定的半定规划的鲁棒规划为0,i1,.,m1,.,mmin cTx: AQXi A 0 ( A0,., An)m1U由一个箱式不确定集合影响的不确定i 1半定规划的近似鲁棒问题U ( A0,.,An) (An,., A?)l(Ai,., An)i则半定规划的近似的鲁棒优化为X1Ax. Tmin c X:XX1X1A0j 1Ax,lnXjAj,l1,., LX1A0XjA,l 1,.,Lj 1k其中 Qj 0, Qj f

8、 0j 1ij QiiI精选文库5U(Ao,An)(An,., A?)i(A0,An)|i2 1。Ax A2XLALXA1xmin cT x: A2xMM 0,F G.-n* n、2( A0XjAj )j 1ALX具有易处理的鲁棒 counterparts的不确定线性规划。 如果多胞形是由有限集合的凸包给出的，则鲁棒规划为nmin CTX:A0 xj Aj 0, l 1,., Lxj 12鲁棒优化的几种新的方法鲁棒规划的最近的研究包括了对于可调节的鲁棒优化的研究以及对于鲁棒凸优化的研究。 2.1不确定的线性规划的可调节的鲁棒解不确定线性规划为 LPZmi ncTu:Uu Vvu,vb U,V,

9、bZ，其中不确定集合Z Rn Rmn Rm是一个非空的紧的凸集,V称为recourse矩阵。当V是确定的情况下,则称相应的不确定线性规划为固定recourse的。Z):Uu Vv b，Z), v:Uu Vv b。由一个球不确定集合影响的不确定半定规划的近似鲁棒问题则半定规划问题为定义：线性规划 LPz的鲁棒COUnterpart(RC):mincTu: v (U,V,b则它的可调节的鲁棒 counterpart为(ARC): mincu: (U,V,b可调节的鲁棒规划比一般的鲁棒规划灵活，但是同时它也比一般的鲁棒规划难解。对于一个不确定线性规划的鲁棒规划是一个计算上易处理的问题，然而它相应的可

10、调节的鲁棒规划却是不易处理的问题。但是如果不确定集合是有限集合的凸包，则固定recourse的ARC是通常的线性规划。从实际的应用来看，只有当原不确定问题的鲁棒counterpart在计算上容易处理的时候，鲁棒优化方法才有意义。当可调节的变量是数据的仿射函数时，可以得到一个计算上易处理的鲁棒coun terpart.对于LPZ的仿射可调节的鲁棒 counterpart (AARC)可以表示为(AARC): min cTu :Uu V(w W ) b, (U,V,bZ)。如果Z是一个计算上易处理的集合，则在固定recourse的情况下，LPZ的仿射可调节精选文库6的鲁棒counterpart (

11、AARC)是一个计算上易处理的问题。如果Z是这样的一个集合,LZ U,V,b U0,V0,b0|U|,V|,b| :| 1是一个非空的凸紧集。在固定的recourse的情况下，AARC具有这样的形式T0|0|0min Lc u :U|U u VV|V bu ,v ,VVlb,如果不确定的集合是一个锥表示的，则LPZ的仿射可调节的鲁棒 counterpart (AARC)是一个锥二次或半定规划。如果recourse也是可变的，则 AARC是不易处理的问题，这时采用它的近似形式。在 简单椭圆不确定集合的情况下，AARC等价于一个半定规划。当扰动的集合是一个中心在原点的箱式集合或者是一个关于原点对称

12、的多胞形集合，则AARC可以有一个半定规划来近似。对于多期的决策问题也是一个可调节的鲁棒优化问题。考虑一个两期的决策问题iunu n fgv,p)其中p是不确定的，但属于一个闭的有界的不确定集合。可行集V依赖于u和参数P。则可以表示为V (u, P)，或Vu(p)。可调节的鲁棒counterpart问题可以表示为uiriftt: p P, V V(u, p): f(u,v, p) t，可以等价的表示为PUvV%P) f(u,v, p)。如果P包含有限数量的元素，P P1, P2,., Pk，则对于每个PiP ,都存在着相应的Vi满足上面的问题。则问题可以转化为一个等价的单层优化问题inf tu

13、,V1,.,Vk ,ts.t f(u,Vi, Pi) t,i 1,.,k u U,v V(u,Pi),i1,k这样的一个单层的优化问题对于许多类的函数f和集合V(u, P)，这是一个易处理的问题。精选文库7gi(u) uTRu r|Tu di,l1,., mh， WiT(u,Vi) ,11,.,k0,l1,.,m2其中 fl(u,Vi, Pi) fl(Wi, Pi)wTQl (pi)Wiql( Pi)TWibl(Pi), l0,.,m2比如 f (u,Vi, p)fo(u,Vi, Pi)，U u : gl(u)0,l1,.,m,V(u, Pi) Vi : fl(u,Vi, p)精选文库8inf

14、 tu,v1,.,vk ,t, T .Ts.t Wi Qi0Wiqi0 WiuT RuwiTQilwibi0t, i 1,.,kT.n u dlT T.q il W bl0,i1,.,k,l 1,.,m2如果不确定集合是有限集合PAx bcT x dLm 1， L 是 Lorentz 锥。Ax b|2( A, b,c,d) (A0,b0,c0,d0)扰动的向量,0是表示扰动幅度的向量,V是扰动集合，A0,b0,c0,d0是名义数值,.l . l l .lA ,b ,c ,d为扰动方向。V是椭圆的交集V RL : TQk1,k 1,., K，Qk k 1,., K为对称的正半定矩阵，且Kk 1Q

15、k是正定的。El Ghaoui和Lebret证明了在不确定集合是范数有Ben -Tal,Nemirovski给出了在扰动集合是椭圆集 则相应的鲁棒 cou nterpartNP难的，但是可以用线性矩阵不等式来则x是问题II Ax b2cTx d的可行解，但且仅当存在，使得在这种情况下，问题等价于一个二次约束的优化问题 Pi, P2,., Pk的凸包conv(P)，则考虑下面的问题unUpSoUPp) vvnu, p)f(u，v，p)如果gu(p) vp)f(u,v,p)是拟凸的，则pmaxP)gu(p) maxguCP)。则问题转化为个单层的优化问题。2.2 一个锥二次问题的鲁棒解 一个锥二次

16、约束的形式为cTx d，A Rmn,b Rm,c Rn,d R，或者是等价的形式假设不确定参数属于一个有界的集合。两种类型的不确定集合常常用到，一个是范数有界的不确定集合，一个是扰动的向量属于一个有界的扰动集合时的结构不确定集合。对于参数的结构不确定为L l(Al,bl,cl,dl),V，其中是描述l 1对于一个单侧不确定的锥二次约束， 界的情况下，问题等价于一个锥二次约束。 合的交集的结构不确定的情况下，如果是简单的椭圆不确定集合， 为一个线性矩阵不等式，在一般的情况下，问题是 近似。Ben-Tal等研究了逐侧不确定的锥二次约束，即对于影响左侧的不确定独立于影响右侧的不确定。(A,b,c,d

17、)(A,b,c,d) (A,b) U ,(c,d) U ，U ,U 是相互独立的集合。精选文库9II Ax b约束A x b|2 cTx d，(*)V RL: TQk1,k1,，K，Qk k 1,，K为对称的正半定矩阵,K且kQk是wx 2(c1)Tx.1/ L、Td ,.,(c )dLT,uxUxI r A 0 I 0-12Ax b ,A1X b1,.,ALx bL.如果向量x被分成两部分，x (uT,vT)T，其中U表示不可调节的变量,v表示可调节的变量。假设目标函数是确定的，独立于可调节的变量V,则相应的锥优化问题为Zv b K, (U,Z,b) SV v(U,Z,b):Uu Zv b

18、K,。可调节的鲁棒规划比一般的鲁棒灵活一些。但是这样会导致所得到的问题是不易处理的。克A,b U和cTx d, c,d U成立。在具有椭球交集的结构不确定的集合的情况下，这两个问题是易处理的。在很多的情况下，影响两侧的不确定集合是相互依存的。比如考虑一个不确定的锥二次其中Az,bz,cz,dz关于z是仿射的。V是中心在原点的椭圆的交集。mjncTu|Uu Zv b K，K是一个锥。则相应于不确定集合S的鲁棒counterpart为mincTu v:Uuu则可调节的鲁棒规划为mincTu (U ,Z,b) S,u正定的。如果存在着k 0,0 ,且满足下式,则x满足(*)式。v(x)k kwTxu

19、Txwxk kQkUTxuxUxI其中 vx (C0)Txd0,精选文库10分别用u,v表示x的子向量，并且分别对应于不可调节的部分和可调节的部分,则上面的约服计算上缺点的一个方法是限制可调节的变量为一个仿射函数。，这样得到了仿射可调节的鲁棒规划为mincTu|Uu Z(w W ) b K,(U,z,b) S对于结构不确定的锥二次约束可表示为II A x b2 cTxd，如果精选文库(111束可以表示为点的椭圆的交集，如果存在u, v w W 满足(*)，对于所有的扰动V成立,u,w,W2 Tu,w,W1-%u,w,Wu,w,Wk kQku,w,W0则可以用上面的半定规划来近似。mins.tT

20、c xxTQix 2qiTx i0,i 1,，PRnn,Qi 0为参数。min cs.t2Vixi 2qTx)i2qiTx,i 1,., pU u Z v b |2 eTu fT v d (*)，若v w W ，则上面的约束即为仿射可调节的约束。下面分成两种情况来讨论，一种是固定的recourse,即Z是确定的，一种是可变的recourse，即Z是不确定的。在第一种情况下，如果约束由(*)表达，扰动集合为中心在原k 0,k 1,.,K和0使得下式成立，则会存在一个解%u,w,W其中% U0uZw b0，%UluZWbl,l1,.,L0T e uf Twd0,lIT e ufTWldl,l1,.

21、, L在第二种情况下，如果扰动很小，使得二次项可以被忽略，如果二次项不能够被忽略，则需要增加一些变量后能够用一个半定规划来近似。 2.3鲁棒凸优化2.3.1鲁棒凸二次约束的规划问题一个凸二次约束的规划问题为其中x为决策向量，c Rn, i R, q Rn,Qi上面的这个问题可以转化为一个二阶的锥规划问题Tx由于上述的模型对于参数很敏感，所以有必要研究其对应的鲁棒问题 一个一般的鲁棒凸二次规划问题为精选文库12Sa (Q,q, ):(Q,q,)鲁棒约束x：Qx 2qTx0, (Q,q,)Sa等价于K个凸二次约束xTQix 2qTxi 0, j1,.,k。Sa (Q,q, )：(Q,q,kj(Qj

22、,qj,j 1j)，Qj0,j 0, jj 1，则鲁棒约束XTQX 2qTx0,(Q,q, ) Sa等价于jXTQiX 2qiT Xi 0,j 1k0, j,j 1Sb (Q,q,k)：(Q,q, ) j(Qj,qj,j 1j)，Qj0,j1,., k, Ab, 0。如果决策向量x Rn满足鲁棒约束XTQX2qTx0 ,对于所有的(Q,q,)Sb，当且仅当存在着Rk，使得2Vx(1i 2q：x A：)2qTx A： , i1,.,P其中Aj是A的第j列，Qj VjTVj,j1,., k 。. :min c Xs.tx：QiX 2qi：xi 0,(Qi,qi, i) S,i 1,.,P当不确定的

23、集合 Si,i 1,., p是椭球时，上面的问题可以转化为一个半定规划问题，这 里我们来确定Si的结构，使它能够转化为一个二阶锥规划。分成以下的三种情况1离散集合和多边形不确定集合 对于离散形式的集合定义为(Qj,qj, j),Qj0, j 1,., k，或者等价的k个二阶锥约束。 对于离散集合的凸包为将上面的两种情况下的集合推广到多边形的不确定集合b：02范数约束的不确定的集合足(Q,q, ):(Q,q, ) (Q0,q0, 0)kUj(Qj,qj, j),Qj 0,u j 10,|u|p1一个决策向量X Rn满足鲁棒约束XTQX 2qTx0 ,对于所有的(Q,q,)Sc，当且s.t1 i精

24、选文库13仅当存在f满足(1 i2Vix2qTx fj)i 1,., p2V0X11 V,f|q2qTx1 10，其中一 1，p qQjVjTVj，j0,., k二次项和锥项的不确定性是独立的，即Sd (Q,q, )：(Q,q, )(Qq,0)kUj(Qj,qj, j),Qj j 10, j(q, ) (q0, 0 )1一个决策向量x Rn满足鲁棒约束XTQX2qTx0，对于所有的(Q,q,Sd，当且仅当存在f ,gkR和 0，满足gj 2qTxj, j 1,.,k，2Vix(1 fj)1 fj,i 1,., k2V0X1V,flqg|s0,其中丄P丄1，丄q r-1 ,QjVjTVj，sj

25、0,.,k3因子化的不确定的集合 如果不确定的集合定义为VTFV , FRmFSe(Q,q, 0):F。T, Nm,V12Rmn,F00,N0q q0,|Wi|g施丽厂 S,S 0i, i,G 0一个决策向量X Rn满足鲁棒约束仅当存在,v, , r R, u R ,w0,v1Tt,1_ rmax (H)Rn,| iXTQXRm,t2qTx0 ,对于所有的Rm，使得下式成立(Q,q, ) Se，当且iUi,UjXj,UjXj, j 1,.,n12 S 2xV 2qTx0精选文库14精选文库15其中C Rn是一个多面体，并且a,ba x b Rn中，每个k 2 c Xidikifk(x)CjkX

26、Xji j任何一个二次多项式可以写成两个正系数的二次多项式的差，一个一般的 写成(QQ P)可以由于 fo (a)fo (x)fo (b), xa,b，则问题可以转化为mins.t tfk (x)f0 (b)f。(x) tf0 (x)fk (x)fo (a)2 其中 f(x)ijCijxXjiCixiidixi，所有的系数为正的。min f0(x)s.t fk(x) 0,k 1,.,m,x Cfk(x),k0,1,.,m Rn 的形式为minf。(x) f。(x)s.tfk (x) fk (x) 0,k 1,.,m,x C通过变换记号，可以得到这样的形式minf (x) g(x) 0,x a,

27、bg(x) min (Uk (x) Vk(x)，并且Uk(x), Vk(x)为单调递增的二次函数使得k 1,.,m2r2wi(ii)(i),i1,.,m其中H1G *0N)G12,HQTmax1 iQ是H的谱分解,1diag(),1wQTFG2V0X。max (H)2.3.2二次约束的二次规划的鲁棒解对于一个非凸的二次约束的二次优化问题m i,精选文库16gk(x)kk 2ik.j jCijXiXj iCix jdiXi bk由于孤立的最优解即使是可计算的，但是它是难于实施，因为它对一个小的扰动非常的不稳定，因而，从实际的观点来看，只有非孤立的可行解有意义。Esse ntia I最优解f(x*

28、) min f (x) x S*，S*表示所以非孤立的可行解的集合。精选文库17假设为一个Essential可行解的目标函数值，给定如果f(a)，由于f（X）单调递增，则f（X）,X a, b如果f(a)，g(a)则a即为一个Essential可行解如果f(a)，g(a)则需要考虑一个辅助的问题(Q/)maxg(x) f (x),x a, b(Q/）求解采用分支定界的方法。这篇文章中给出了一个successive in cumbe nt tran sce ndin g(SIT)算法。3鲁棒优化的应用鲁棒优化现在已经应用到了各个研究领域，这里我们主要给出了在金融上的应用。1. Rujun She

29、n和Shuzhong Zhang 将鲁棒的观点应用于基于选择问题中，给出了一阶段和两阶段的组合选择模型相应的鲁棒规划问题。：布存在ambiguity.这样的一个问题能够转化为一个有限的锥形式凸规划问题。 卖空的情况下，效用函数采用下半方差的负值，参数的不确定集合是椭球形的，题可以转化成一个二阶锥规划问题。假设想从n种资产中选择一个投资组合并且持有一段时间，假设初始的财富为期末有m种可能的结果。即所有的可能的 scenario可以通过一个具有 m个叶子的一阶段树 来表示。假设收益向量的第 i个元素表示表示第i种资产的收益。则基于 seenario的单阶段 的组合选择模型为seenario树的投资

30、组合的这里允许概率分 并且在不允许,则相应的问1,持有maxs.tmiU( Tri)i 1Te 1n是股票的数量，m是每个节点scenario的数量Rn是持有的股票，是模型中的决策向量riRn是如果seenario i出现的话n个股票的收益i是scenario i出现的概率Essential 可行解:0, x a,b满足 g(x) 。一个非孤立的可行解X称为是Essential最优解，如果它满足f(X)最优解的方法是：从一个初始的Essential可行解，寻找一个更好的inf( f (x) g(x) ,x a,b)寻找 EssentialEssential可行解，直到不能获得比当前的可行解更好

31、的可行解为止。精选文库18maxii z 产 T ij X jU( rj) j 1s.trijRn 表示如果 seenarioi出现在第一阶段，seenario j出现在第二阶段j表示条件概率seenarioj出现在第二阶段在scenario i出现在第一阶段的条件下的概率。i第二阶段允许的投资组合i是第二阶段的 recourse问题的最优解maxju(iTrij)则上面的问题可以写成(P2)s.ti 1iTei1,2,., mmaxmaxistiTeis.ti . iT ij , jU( r )Tri, i 1,2,., m假设可行集为凸集令 (1,., m)，i1 ,.,且由定义可知i为非

32、负的向量 Te 1, iTe 1问题(P2)是可分的，则可得mmaxi 1i maxju(iTrij)s.tiTeiT ir ,Tei 1,2,., m1,e R是分量全为1的向量是允许的投资组合集合则两阶段的效用极大化投资模型为精选文库19由于u(g)是凹的，则上面的问题为凸规划。精选文库20并且我们并不知道确切我们可以得到max iris.tmmin (%Vi,y Ui 1Te 1yi)u(Tri)两阶段的模型中的估计量为%, %,%,令%, U令yii %，Uimax m.inri Vi,y U(%yi)maXrij minuim(%j 1yj)u( iTrj)s.tiTeii 1,2,

33、., m1没有卖空Rn2 一个半方差的非效用函数d(w) (Rw)2相当于一个给定的基准组合的下方风险，相应的效用函数为u(w) (Rw)2。单阶段模型的鲁棒规划模型确定的情景树有两个缺点：一个是每个情境中收益的模糊性，一个是每个情景发生的条 件概率的模糊性。实际上在我们的模型中用到的收益向量为估计值。的收益为多少，但是根据统计分析，我们知道实际的值离我们估计的值不远， 某些置信区间。ri Vi (收益的模糊性)(概率分布的模糊性)假设所有的集合为凸的，紧的，非空的。令则鲁棒模型为两阶段的鲁棒规划模型Te1单阶段鲁棒模型的有限表示 假设条件：模糊集合是椭球形的:RmTe 1,Vi riRn (

34、ri%i)TQi(ri %)i2, i 1,.,m为了简便,假设 Qi是单位矩阵精选文库21精选文库22U y Rm yTey|Vi ri Rni, i1,.,m则原模型可变形为max(R T%)2s.t则相应的鲁棒规划模型为maxs.t进一步变形为利用结论t。将上面的规划变为i minri Vi,y UTe 1m(% yi)i 1(R T%)2min,t1 ,t0s.tmin,t1 ,t0s.tyJSi, yt0t0tiTet0t0timax(%max(R1,max( %y U 2i 1max(R01,t0(ay)TtT%)2y)TtT%)2%aaTesoc(m 1)e)m精选文库23精选文

35、库24对于一个一般的模型通过增加变量变为min t0,t1 ,t0t。aT( a e、(a e)m0,maxris.tmax t0St t。UiwiTesoc(m1),titi21 soc(3)T%0,soc( n1)minVi,y UTe 1m(%i 1U(Wi),Tri,1,如果D是一个凸集，则它的齐次锥是则可以得到如下的凸表示mint0对于多阶段的鲁棒模型%twi0,max minri Vi,y UTe1(%i 1yJUi,ri ViH(D)t0H(U )*,UiH(Vi)*Te 1m(%i 1yi)u(clTri0, Du(wi),yi) max mini rj Vj ,yi Uis.

36、tiTei0,(% yj)(R11,2,., miTrij)2精选文库25精选文库xx ()。26因此iWi : rTri把球Vi映射到区间Tr% i|,T%II ，则上述模型等价于maxi i minri i Vi i,y Um(%i 1yi) max min max丄iTs.t. eiT%Wi,0, i| IIWim(% yi)( Rjj 11,2,., mT% ill IIiT% II i)22. R.h.tutuncu, M.Koenig 给出一个基于应鲁棒优化问题是一个标准的二次规划问题，点问题。利用2003年Handorsson和Tutuncu给出的方法求解。作者给出了在不确定集合

37、 为区间时的鲁棒MVO模型，和鲁棒最大夏普比率问题。一个资产分配问题可以表示为在期望收益的下限上极小化方差或最大化一个风险调节 的期望收益worse-case的方法。在一个简单的情况下，相 在大多数情况下，这个问题可以转化为一个鞍其中mRqxTQxs.tTxR, (1)xRn0对于期望收益的向量和协方差矩阵UUQQ:QLQU,Q 0( ,Q)：,Q UQTmax xx s.t xxTQx(2)Q分别取成区间的形式采用区间型数据的原因：（1）区间的端点对应于历史数据中相应的统计的极值，在分 析估计和Scenarios中。（2）建模者可以选择置信水平，以预测区间的形式产生收益和协方 差的估计。给定

38、不确定集合U，优化问题（1） （2）对应的鲁棒优化为minmax xTQxx RN Q UQJTx R, （7）s.tminUmax minx * U ,Q UQTxXTQX (8)）是（8）一个给定正值的最优解，则x （）也是（7 ）的最优解对于精选文库xx ()。27精选文库28Txrfmax h(x) s.t x(11)x Rn,R一个锥，当是一个环的时候,是一个 ice-cream锥，若是一个多面体,x Axb,cx d，则x Ax b 0,cxd 0,0。Txh(x)传rfe)Tx1xJxT Qx:g(x)g(-),0,由于g(x)是齐次的，则问题等价于 max g(x) s.t (

39、x,)，由于g(x)是齐次的，则增加规范化的约束不会影响最优解(rfe)T 1，则问题等价于1 max-5= 5/XTQXst(X,),(rfe)T1结论：给定一个可行的具有 eT x1性质的组合集x，这个集合中具有最大夏普maxxTQx s.t (x,),(15)minmax xTQxrfe)T 1s.tmin(US财政证券可以认为是无风险投资。如果这样的资产包含于资产类中，则有效的投资组合是这个无风险资产和一个风险组合的线性组合。这个最优的组合是具有最高夏普比率的组合。h(x), rf为无风险的已知收益。假设 Q是正定的。因为 Q是正半定的,JXTQX若它是正定的，则意味着没有冗余的资产。

40、具有最高夏普比率的组合可以通过解决下面的优化问题给出：这个目标函数是一个非线性，非凹的目标函数，难以解决。 利用lifting技术对 进行齐次化：x0, U (0,0)，增加(0,0)是为了或得一个凸集。比率的解可以通过下面的规划来解:若 x* (x,k)是(15)的解，贝U x*5?/1?。松弛问题如下:(x,)鲁棒有效前沿的算法:精选文库29minmax xTQX1利用SP算法解决没有期望收益约束的问题XRn QUQ，令Xmin表示他的最优解，令s.t XRmin() xmin2，解决问题mxax umnuQx，令Xmax表示他的最优解，Rmax() XmaxRmaxRmin3选择K，有效

41、前沿上点的数量,RRmin/(K1),Rmin 2/(K 1),，Rmin(n 1) /(K 1)，解决问题minmax xTQxX R Q UQJs.tmin Tx R,U3. Mustafa C.Pinar给出了多阶段的组合选择模型。目标是最大化最终期望收益和最小 化与一个给定的财富水平的偏差。他们之间是通过一个非负参数来平衡的。利用一个分段的线性罚函数，能够得到线性规划模型，并且能够确保如下阶段的最优性。假设有m+1种资产，前m种为风险的股票，第 m 1种为无风险资产，比如现金。X0表示1阶段初的决策向量，x0i表示相应的组合种第i种资产的市值。X1表示2阶段初的决策向量,r1, r2表

42、示一阶段和二阶段结束后的净资产收益。是有限概率空间上(，F , P)的离散的随机变量。假设市场的发展是离散的seenario树。r,表示随机变量r1相应于第一层seenario树的第n个节点的实现。基于最大的期望 en d-of-horizon组合值的没有交易费用的两阶段组合选择模型的随机规划为：maxPnQn(x0) eTx0 1,x0 0X n N2其中Qn(X0)max(rn2)Tx1(n)X/T 1Z 1T 01Cl(e) X (n) (r (n) X ,X (n)0由于 recourse问题Qn(x0), n N2的可分性，上面的优化问题等价于/ 2T 1Pn(rn) X (n)T0

43、 T1/1T0K|0c1c、e X1,(e) X(n) (r )x ,n N1,xOx00maxNxXn,n N1 n N2以上的模型假设决策者是风险中立的，Mulvey,Va nderbei and Zen ios建议通过由一个参数控制给目标函数增加一个风险项得到两阶段的鲁棒随机规划。他们的模型为精选文库30精选文库31z2xT1 X T 0. 0Cl.,(rN) x (N) e x1,x0r/2T 1,2T 1,2、T 10max p n(rn ) X (n) f (h ) X ,.,.X Xn, n N1 n N 2r, 01Hl T 0. / T 1/ 1T 0HI 0(X , Xn,

44、 n N1):ex1,(e) Xn(rn) x , n NM ,( R) x(N)(X , Xn, nN1)(5)0,x10Takriti and Ahmed证明了对于任意的方差测度 f，上式对能够给出当两阶段的组合决策问题对于recourse问题不是最优时的最优解。如果f是一个非减的函数,0，则上面的两个问题时等价的。f(t)Takriti and Ahmed利用了一个分段二次的方差度量n(R tn)2，其中R*是目标函数值。t是一组离散的随机变量，具有实n N2现 t1 , t2).)t N 2，而1, 2 ,., N|是相应的概率。r/2 T 10maX Pn(rn ) x (n)xXn

45、,n N1 n N2fz01Ki T 0( X ,Xn, n N1) :e X2 T 10Pn(R* (rn ) X (n) (X ,Xn N1)n N2” /T 1 Z 1T 01,(e) Xn(rn) x , nM 0N1,x0,x101,.,mmax PnQ(x0)f (r12)Tx1(1),.X n N2则可分离的鲁棒优化模型为为了是计算方便是所得的问题是一个线性规划，采用一个分段线性的方差测度f(t)n(R tn)n N2它仍然满足非减的条件。则我们的问题变为可以将上面的模型推广到三阶段的情况。在这篇文章中作者还给出了包含线性交易费用的模型。y1表示一阶段买入资产的数量,i1表示一阶

46、段买入一美元的资产的交易费Zn表示一阶段卖出资产的数量,1Vi表示一阶段卖出一美元的资产的交易费如订表示x：的第i个分量则对于风险资产 xnirnix0i yzlli，i对于无风险资产xnm 1亦 1x01m 1i 1(11)y1im(1 v1)znii 1精选文库32m初始的资金要求为(1i 1i0)x0i1 x0m 1精选文库I133n Ni) T的一个投资组合。Xi表示投资组合中资产i在阶段I开始时的数量。1是来自前一个阶段的数量,I ri0表示资产收益。Z1表示在阶段I初买入的资产数量。yi表示在阶段I初卖出的资产数量。n 1时,nII 1 I 1Xn 1rn 1Xn 1(1i 1iI

47、)yIn(1i 1vI)ZIIrn1xn1是从前一个阶段得到的现金流;(1：）y：是在阶段I卖出资产i得到的资产数量,i表示交易成本(1v：） Zil表示在阶段I买入资产i得到的资产数量,Vi表示交易成本则可行集为T （xlx：, yn,zn, n NJ:满足上面的三个方程带有交易成本的鲁棒两阶段的投资组合选择的模型为0 max Pn（r）TX1 （n）P n（R* （丁）（X。, X；,紀,Z：,X Xn nH 叫 n N2n N24. Aharo n Ben-Tai, Tamar MargaIit Arkadi Nemirovski给出了一个多阶段的组合选择问题的鲁棒建模方法。假设有n种类

48、型的资产i 1,n和现金（n 1）。L个投资阶段。目标是控制这些资产x可以有下列的方程给出:I I 1 I 1 I I n 时，Xi r Xiyi Zi应该满足约束YiYiV： ,i1,., n.II呂 Z-I .Zi ,i1,., n,II为ViI -Xi ,i1,., n上界为无穷大0,假设约束为简单的约束，即下界为精选文库I134max目标是极大化期末财富的总价值 riLXiL。可得到线性规划模型为L L ri XiI 1 I riXiI IyiZ,i 1,., n,l 1,., L精选文库35令 i1 (R1),1，lVi0,ii 11,.,n, li1,.,Ll乙0,i1,., n,

49、l1 LlXi0,i1,., n, n1,l1,.,L(R1)1 lVi，：(Ri1)11卄亠1Zi，其中R11ilrn1 LilXnri0ri1.ril 1，则新的规划为n1 l 1“ l、 I1Xn 1(1 i )yin 1RLn(1 VZ11其中数据的不确定性决策向量i:, i:,.maxi 1,., n,l 1,., LlililiAB：lilili1 1 n 1nA1 i1i 1nB1 ,1i 10,i1,., n,l1,.,L0,i1,., n,l1,.,L0,i1,., n,n1,l1,.丄(1亦/尺1,(1 vbR1/1,max wwn 1RiL1 iLi 11ii1 1 1i

50、i1 .,i 1,.,1n11An 1Ai 1ni1Bi 11 1i i0,i1,., n,l1,.,L0,i1,., n,l1,.,L11 L I,i0,i1,., n,nlili ,l1 L,I,II I 7 77 7 J Jn, l 1,., Lli1,l1,.,Lil不是实的,l的可测函数，当决策向量实施的时候，数据就是立即可知。不确定线性规划的鲁棒规划maxcT X AXXb 0精选文库36精选文库37maxX为N维的决策向量，c为精确可知的目标,A, baTb1Lambm为不确定的约束矩阵。锥二次规划aTxbimaxcT x AX b 0,Ui (aT，b0) (a0T，b0)ma

51、xcTx|(ai0T,bi0)|FA1，l B1A,bUkiUj(aijT,bj)j 11iX2 0，i1,m2,., L,FL 1RL1 ,精选文库38iL 1 是 RL1的期望,i 1ll 1liii1li, i1,., n, l1,l (l Tll 1 n 1nn1 Jl V li 1l 0,i1,., n,l1,.,Li 0,i1,., n, 11 Lil 0,i1,.,n, n1,l 1,.,L是随机变量RL 1的协方差矩阵。1iil2, l 1,.,L .il ：,11,.,L1是随机变量的协方差。锥规划模型可以用已有的算法求解。4结论：这里给出了鲁棒优化的基本算法，最新的发展和在

52、金融上的应用。今后的研究 方向是对鲁棒优化算法本身的研究，另一个是将其用到金融上。参考文献1 A.L.Soyster. Convex p rogram ming and set-i nclusive con stra ints and app licati on to in exact lin ear p rogrammi ng. Op erati on Research,21:1154-1157,19732 J.E.Falk. Exact soluti on of in exact li near p rograms. Op erati on Research,24,1796wLiiliL 1ililin 1VL1(R pl)T(Vl) 1(FiPl)n/ LTVL1 L精选文库39op timizati on.convexRobustapp licati ons.a muli-stagemeasure