鲁棒优化的方法及应用概述.docx

鲁棒优化的方法及应用
杨威
在实际的优化中决策过程中，我们经常遇到这样的情形，数据是不确定的或者是非精确 的；最优解不易计算，即使计算的非常精确， 但是很难准确的实施；对于数据的一个小的扰
动可能导致解是不可行。鲁棒优化是一个建模技术，可以处理数据不确定但属于一个不确定
集合的优化问题。早在 19世纪70年代，Soyster就是最早开始研究鲁棒优化问题的学者之
一，他的文章给出了当约束矩阵的列向量属于一个椭球形不确定的集合时的鲁棒线性优化问 题。几年以后 Falk沿着这条思路做了非精确的线性规划。在以后的很长的一段时间里，鲁 棒优化方面都没有新的成果出现。 直到19世纪末，Ben-Tal,Nemirovski的工作以及这时计算
技术的发展，尤其是对于半定优化和凸优化内点算法的发展， 使得鲁棒优化又成为一个研究
的热点。
一个一般的数学规划的形式为
min n{x0 : f°(x, ) — X。乞 0, £(x, ) E0,i
-R ,x =R
其中x为设计向量，fo为目标函数，f!, f2,..., fm是问题的结构元素。•表示属于 特定问题的数据。U是数据空间中的某个不确定的集合。 对于一个不确定问题的相应的鲁棒
问题为
min n{x° : f°(x, ) -X。一 0, £(x, ) 一 0,i =1,...,m^ U}
x - R,x :R
这个问题的可行解和最优解分别称为不确定问题的鲁棒可行和鲁棒最优解。
这篇文章主要回顾了鲁棒优化的基本算法，目前的最新的研究结果及在经济上的应用。
1鲁棒优化的基本方法

一个不确定线性规划 {min{ cTx： Ax 3b} (c, A,b)乏U u Rn x Rmxhx Rm}所对应的鲁
x
棒优化问题为 min {t：t _cTx, Ax _b,(c, A,b)・U}，如果不确定的集合是一个计算上易处
x
理的问题，则这个线性规划也是一个计算上易处理的问题。并且有下列的结论：
假设不确定的集合由一个有界的集合 Z={ } rn的仿射像给出，如果 Z是
1线性不等式约束系统构成 P■岂P，则不确定线性规划的鲁棒规划等价于一个线性规划问
题。
2由锥二次不等式系统给出 P • - Pi||2空q「• -「i,i =1,...,M，则不确定线性规划的鲁棒规
划等价于一个锥二次的问题。
dim ：
3由线性矩阵不等式系统给出 P0亠二1P -0，则所导致的问题为一个半定规划问题。
i =1

考虑一个不确定的凸二次约束问题
{min{ cTx: xTAjX 兰2QTx + q，i =1,…,m} （A，E,cj二 e U}
对于这样的一个问题，即使不确定集合的结够很简单，也会导致 NP难的问题，所以对
于这种问题的处理通常是采用它的近似的鲁棒规划问题。
考虑一个不确定的优化问题 P二{min{ cTx： F（x, B 0K U}，假设不确定集合为
X
U = n V，而n表示名义的数据，而 V表示一个扰动的集合，假设 V是一个包含原 点的凸紧集。不确定问题 P可以看成是一个不确定问题的参数族
Pp={m『{ cTx: F（x上）兰0} + PV}，P> 0表示不确定的水平。
具有椭圆不确定性的不确定的凸二次规划问题的近似鲁棒问题
L
U ={{（ Cj，A，bJ =（c：, An，bn）+》©（d’A」1）}舊|©TQjd1,j =1,…,k}
1=1
k
其中 Qj _0? Qj >0
j^z
则问题可一转化为一个半定规划问题
T
min c x
k
2xTbn cn j
j仝
1 L
ci T 1 ci
—+ x b …—+ x
2 2
TbL
[Anx]T

i
§ xTbiZ
2
L
G T L
—x bi
2
Anx
k
■- 7 ij Qi
j T
[AZx]T
[ALx]t
A1xillALx
具有椭圆不确定集合的不确定锥二次冋题的近似鲁棒规划 考虑不确定锥二次规划
{min{ cTx: A,x bi
i,i =1,…,m} {（人山耳卫）}二刊}
它的约束为逐侧的不确定
U = （A,bi」i「）}角
{A’b/ U1eft
{ = ,£• U right
它的左侧的不确定的集合是一个椭圆
L
U 1eft -{{（ Ai,b）=（Ain,bin）+2：勺3馬）}点纤Qjd1,j =1,...,k}
1 =1
k
其中Qj _0广Qj >0
j4
右侧的不确定集合是有界的，它的半定表示为
R
V}
u rig