鲁棒优化的方法及应用

鲁棒优化的方法及应用杨威在实际的优化中决策过程中，我们经常遇到这样的情形，数据是不确定的或者是非精确的；最优解不易计算，即使计算的非常精确，但是很难准确的实施；对于数据的一个小的扰动可能导致解是不可行。鲁棒优化是一个建模技术，可以处理数据不确定但属于一个不确定集合的优化问题。早在19世纪70年代，Soyster就是最早开始研究鲁棒优化问题的学者之一，他的文章给出了当约束矩阵的列向量属于一个椭球形不确定的集合时的鲁棒线性优化问题。几年以后Falk沿着这条思路做了非精确的线性规划。在以后的很长的一段时间里，鲁棒优化方面都没有新的成果出现。直到19世纪末，Ben-Tal,Nemirovski的工作以及这时计算技术的发展，尤其是对于半定优化和凸优化内点算法的发展，使得鲁棒优化又成为一个研究的热点。一个一般的数学规划的形式为0000,min{:(,)0,(,)0,1,...,}nixRxRxfxxfxim其中x为设计向量，0f为目标函数，12,,...,mfff是问题的结构元素。表示属于特定问题的数据。U是数据空间中的某个不确定的集合。对于一个不确定问题的相应的鲁棒问题为0000,min{:(,)0,(,)0,1,...,,}nixRxRxfxxfximU这个问题的可行解和最优解分别称为不确定问题的鲁棒可行和鲁棒最优解。这篇文章主要回顾了鲁棒优化的基本算法，目前的最新的研究结果及在经济上的应用。1鲁棒优化的基本方法1.1鲁棒线性规划一个不确定线性规划{min{:}(,,)}TnmnmxcxAxbcAbURRR所对应的鲁棒优化问题为min{:,,(,,)}TxttcxAxbcAbU，如果不确定的集合是一个计算上易处理的问题，则这个线性规划也是一个计算上易处理的问题。并且有下列的结论：假设不确定的集合由一个有界的集合{}NZR的仿射像给出，如果Z是1线性不等式约束系统构成Pp，则不确定线性规划的鲁棒规划等价于一个线性规划问题。2由锥二次不等式系统给出2,1,...,TiiiiPpqriM，则不确定线性规划的鲁棒规划等价于一个锥二次的问题。3由线性矩阵不等式系统给出dim010iiiPP，则所导致的问题为一个半定规划问题。1.2鲁棒二次规划考虑一个不确定的凸二次约束问题1{min{:2,1,...,}(,,)}TTTmiiiiiiixcxxAxbxcimAbcU对于这样的一个问题，即使不确定集合的结够很简单，也会导致NP难的问题，所以对于这种问题的处理通常是采用它的近似的鲁棒规划问题。考虑一个不确定的优化问题{min{:(,)0}}TxPcxFxU，假设不确定集合为nUV，而n表示名义的数据，而V表示一个扰动的集合，假设V是一个包含原点的凸紧集。不确定问题P可以看成是一个不确定问题的参数族{min{:(,)0}}TnxPcxFxUV，0表示不确定的水平。具有椭圆不确定性的不确定的凸二次规划问题的近似鲁棒问题11{{(,,)(,,)(,,)}1,1,...,}LnnnlllmTiiiiiiliiiijlUcAbcAbcAbQjk其中10,0kjjjQQ则问题可一转化为一个半定规划问题11111111min2...[]22[]2..0,1,...,[]2TLkTnnTTLnTiiiiijiiijTiTiikijijLLTTLiiinLiiicxccxbcxbxbAxcxbAxstQimcAxxbAxAxAxI具有椭圆不确定集合的不确定锥二次问题的近似鲁棒规划考虑不确定锥二次规划12{min{:,1,...,}{(,,,)}}TTmiiiiiiiiixcxAxbximAbU它的约束为逐侧的不确定111{,}(,,,)}{,}mleftmiiiiiiiimrightiiiAbUUAbU它的左侧的不确定的集合是一个椭圆11{{(,)(,)(,)}1,1,...,}LleftnnllmTiiiiliiijlUAbAbAbQjk其中10,0kjjjQQ右侧的不确定集合是有界的，它的半定表示为11{{(,)(,)(,)}}RrightnnrrmiiiiriiirUV{:()()0}VuPQuR，(),()PQu为线性映射。则半定规划为11111min[][]..0,1,...,[]TknnTijiijTiikijijLLTiinnLiiiiicxAxbAxbstQimAxbAxbAxAxI其中11**0,1,...,,1,...,(),1,...,(),1,...,()0,1,...,0,1,...,ijTnniiiiTiiiTRRiiiiimjkxTrRVimxPVimxQVimVim1.3鲁棒半定规划一个不确定的半定规划的鲁棒规划为0011{min{:0}{(,...,)}}nTmiinixicxAxAAAU由一个箱式不确定集合影响的不确定半定规划的近似鲁棒问题0001{(,...,)(,...,)(,...,)1}LnnllnnlnlUAAAAAA。则半定规划的近似的鲁棒优化为01,011[],1,...,min:[],1,...,,1,...,lnlllljjjTllxXLnllljjljXAxAxAlLcxXAxlLXAxAlL由一个球不确定集合影响的不确定半定规划的近似鲁棒问题00021{(,...,)(,...,)(,...,)1}LnnllnnlnlUAAAAAA。则半定规划问题为12120,,1[][][][]min:[]0,2()[]LnTnnjjxFGjLGAxAxAxAxcxAxFFGAxAAxF具有易处理的鲁棒counterparts的不确定线性规划。如果多胞形是由有限集合的凸包给出的，则鲁棒规划为01min{:0,1,...,}nTlljjxjcxAxAlL2鲁棒优化的几种新的方法鲁棒规划的最近的研究包括了对于可调节的鲁棒优化的研究以及对于鲁棒凸优化的研究。2.1不确定的线性规划的可调节的鲁棒解不确定线性规划为[,,],{min:}TZUVbZuvLPcuUuVvb，其中不确定集合nmnmZRRR是一个非空的紧的凸集，V称为recourse矩阵。当V是确定的情况下，则称相应的不确定线性规划为固定recourse的。定义：线性规划ZLP的鲁棒counterpart为():min{:([,,]):}TuRCcuvUVbZUuVvb，则它的可调节的鲁棒counterpart为():min{:([,,]),:}TuARCcuUVbZvUuVvb。可调节的鲁棒规划比一般的鲁棒规划灵活，但是同时它也比一般的鲁棒规划难解。对于一个不确定线性规划的鲁棒规划是一个计算上易处理的问题，然而它相应的可调节的鲁棒规划却是不易处理的问题。但是如果不确定集合是有限集合的凸包，则固定recourse的ARC是通常的线性规划。从实际的应用来看，只有当原不确定问题的鲁棒counterpart在计算上容易处理的时候，鲁棒优化方法才有意义。当可调节的变量是数据的仿射函数时，可以得到一个计算上易处理的鲁棒counterpart.对于ZLP的仿射可调节的鲁棒counterpart(AARC)可以表示为,,():min{:(),([,,])}TuwWAARCcuUuVwWbUVbZ。如果Z是一个计算上易处理的集合，则在固定recourse的情况下，ZLP的仿射可调节的鲁棒counterpart(AARC)是一个计算上易处理的问题。如果Z是这样的一个集合，0001{[,,][,,][,,]:}LlllllZUVbUVbUVb，是一个非空的凸紧集。在固定的recourse的情况下，AARC具有这样的形式01000,,,...,min{:[][][],}LTlllllluvvvcuUUuVvvbb如果不确定的集合是一个锥表示的，则ZLP的仿射可调节的鲁棒counterpart(AARC)是一个锥二次或半定规划。如果recourse也是可变的，则AARC是不易处理的问题，这时采用它的近似形式。在简单椭圆不确定集合的情况下，AARC等价于一个半定规划。当扰动的集合是一个中心在原点的箱式集合或者是一个关于原点对称的多胞形集合，则AARC可以有一个半定规划来近似。对于多期的决策问题也是一个可调节的鲁棒优化问题。考虑一个两期的决策问题infinf(,,)uUvVfuvp其中p是不确定的，但属于一个闭的有界的不确定集合。可行集V依赖于u和参数p。则可以表示为(,)Vup，或()uVp。可调节的鲁棒counterpart问题可以表示为,inf{:,(,):(,,)}uUttpPvVupfuvpt，可以等价的表示为(,)infsupinf(,,)uUvVuppPfuvp。如果P包含有限数量的元素，12{,,...,}kPppp，则对于每个ipP，都存在着相应的iv满足上面的问题。则问题可以转化为一个等价的单层优化问题1,,...,,inf..(,,),1,...,,(,),1,...,kuvvtiiiitstfuvptikuUvVupik这样的一个单层的优化问题对于许多类的函数f和集合(,)Vup，这是一个易处理的问题。比如0(,,)(,,)iiiifuvpfuvp，{:()0,1,...,},lUugulm2(,){:(,,)0,1,...,}iiliiVupvfuvplm其中2(,,)(,)()()(),0,...,TTliiliiiliiliilifuvpfwpwQpwqpwbplm1(),1,...,TTllllguuRurudlm，(,),1,...,Tiiwuvik在这种情况下，问题等价于一个二次约束的优化问题1,,...,,00012inf..,1,...,0,1,...,,0,1,...,,1,...,kuvvtTTiiiiiiTTlllTTTiiliiliiltstwQwqwbtikuRurudlmwQwqwbiklm如果不确定集合是有限集合12{,,...,}kPppp的凸包()convP，则考虑下面的问题(,)()infsupinf(,,)uUvVuppconvPfuvp如果()()inf(,,)uuvVpgpfuvp是拟凸的，则()max()max()uupconvPpPgpgp。则问题转化为一个单层的优化问题。2.2一个锥二次问题的鲁棒解一个锥二次约束的形式为2TAxbcxd，[,,,]mnmnARbRcRdR，或者是等价的形式1mTAxbLcxd，L是Lorentz锥。假设不确定参数属于一个有界的集合。两种类型的不确定集合常常用到，一个是范数有界的不确定集合，一个是扰动的向量属于一个有界的扰动集合时的结构不确定集合。对于参数的结构不确定为00001{(,,,)(,,,)(,,,),}LllllllSAbcdAbcdAbcdV，其中是描述扰动的向量，0是表示扰动幅度的向量，V是扰动集合，0000,,,Abcd是名义数值，,,,llllAbcd为