鲁棒优化的方法及应用.doc

..... 页眉..... 页脚鲁棒优化的方法及应用杨威在实际的优化中决策过程中, 我们经常遇到这样的情形, 数据是不确定的或者是非精确的; 最优解不易计算, 即使计算的非常精确, 但是很难准确的实施; 对于数据的一个小的扰动可能导致解是不可行。鲁棒优化是一个建模技术, 可以处理数据不确定但属于一个不确定集合的优化问题。早在 19 世纪 70 年代, Soyster 就是最早开始研究鲁棒优化问题的学者之一, 他的文章给出了当约束矩阵的列向量属于一个椭球形不确定的集合时的鲁棒线性优化问题。几年以后 Falk 沿着这条思路做了非精确的线性规划。在以后的很长的一段时间里,鲁棒优化方面都没有新的成果出现。直到 19 世纪末, Ben-Tal,Nemirovski 的工作以及这时计算技术的发展, 尤其是对于半定优化和凸优化内点算法的发展, 使得鲁棒优化又成为一个研究的热点。一个一般的数学规划的形式为 0 0 0 0 , min { : ( , ) 0, ( , ) 0, 1,..., } ni x R x R x f x x f x i m ? ?? ?? ? ??其中 x 为设计向量, 0f 为目标函数, 1 2 , ,..., m f f f 是问题的结构元素。?表示属于特定问题的数据。U 是数据空间中的某个不确定的集合。对于一个不确定问题的相应的鲁棒问题为 0 0 0 0 , min { : ( , ) 0, ( , ) 0, 1,..., , } ni x R x R x f x x f x i m U ? ? ?? ?? ? ????这个问题的可行解和最优解分别称为不确定问题的鲁棒可行和鲁棒最优解。这篇文章主要回顾了鲁棒优化的基本算法,目前的最新的研究结果及在经济上的应用。 1 鲁棒优化的基本方法 鲁棒线性规划一个不确定线性规划{min{ : } ( , , ) } T n m n m x c x Ax b c A b U R R R ?? ????所对应的鲁棒优化问题为 min{ : , , ( , , ) } Tx t t c x Ax b c A b U ? ??,如果不确定的集合是一个计算上易处理的问题,则这个线性规划也是一个计算上易处理的问题。并且有下列的结论: 假设不确定的集合由一个有界的集合{ } N Z R ?? ?的仿射像给出,如果 Z 是 1 线性不等式约束系统构成 P p ??,则不确定线性规划的鲁棒规划等价于一个线性规划问题。 2 由锥二次不等式系统给出 2 , 1,..., T i i i i P p q r i M ? ?? ???,则不确定线性规划的鲁棒规划等价于一个锥二次的问题。 3 由线性矩阵不等式系统给出 dim 010 i i i P P ???? ??,则所导致的问题为一个半定规划问题。 鲁棒二次规划考虑一个不确定的凸二次约束问题..... 页眉..... 页脚 1 {min{ : 2 , 1,..., } ( , , ) } T T T m i i i i i i i x c x x Ax b x c i m A b c U ?? ?? ?对于这样的一个问题,即使不确定集合的结够很简单,也会导致 NP 难的问题,所以对于这种问题的处理通常是采用它的近似的鲁棒规划问题。考虑一个不确定的优化问题{min{ : ( , ) 0} } Tx P c x F x U ? ?? ??,假设不确定集合为 n U V ?? ?,而 n?表示名义的数据,而 V 表示一个扰动的集合,假设 V 是一个包含原点的凸紧集。不确定问题 P 可以看成是一个不确定问题的参数族{min{ : ( , ) 0} } T n x P c x F x U V ? ?? ???? ????,0??表示不确定的水平。具有椭圆不确定性的不确定的凸二次规划问题的近似鲁棒问题 11 {{( , , ) ( , , ) ( , , )} 1, 1,..., } L n n n l l l m T i i i