稳健性最优化简介
2008-9-28 19:09:34【来源：网络】
稳健性最优化，英文是robust optimization，本质上是一类半无限最优化问题(semi-infinite programming)。只不过它研究的更为具体一些，在方法论上，更加注重于把半无限最优化问题用转化称一个多项式可解的确定性最优化问题或者用一个多项式可解的确定性最优化问题来逼近。
稳健性最优化开始于1998，由EI. Ghaoui,etc和Ben-Tal and Nemirovski等等倡导。目前稳健性最优化问题的研究方法有3种。第一种，也是最先的，由Ghaoui,Febret等等开始使用，来自于robust control的，叫做分式线性型（fractional linear representaion)。他们研究可以表示为fractional linear representation的不确定性（叫做结构不确定性：structual uncertainty)。
在这种假定下，他们研究了robust最小二乘问题以及robust semi-definite programming问题，或者了一些结果。第二种方法是Ben-Tal 和Nemirovski采用的研究非结构不确定性的方法。他们采用semi-definite programming的方法论，研究了robust linear optimization, robust quadradic optimization和robust semi-definite programming,并且证明了一些近似结果。
他们最重要的结果表明：对于如下robust linear optimization
min c^Tx
s.t. Ax<=b, \forall [A,b]\in U
其中，U是不确定集合。
当U 是椭球，或者多胞形，或者是半正定约束表成的集合，半无限线性规划可以转化乘相应的二次规划，线性规划以及半正定规划。对于robust quadratic optimization来说，结果是近似的。他们证明了著名的approximate S-lemma。这个结果很技术性，也很重要。
第三种方法由Shuzhong Zhang提出。他的方法论基于所谓的D-induced duality理论。这个理论对robust optimization 构造了一个统一框架。
他的方法论首先研究如下问题
集合{ M| B(x,y)= x^TM_iy>=0,\forall x\in K, y\in D^*}
在什么时候多项时可表出。其中K,D是凸闭proper,solid锥。
这个方法论统一了Ben-Tal,Nemirovski,和Ghaoui,Febret等的结果。他们的结果都可以用D-induced duality的语言写出。但是目前还没有其他的结果。我的博士论文就是做这方面的工作--希望能够找到更多的可以多项式表出的cases。或者用多项式可解的问题来近似D-induced duality 问题并且获得好的近似度。
robust optimization 一般来说是NP-hard的。关于这个概念我会在另外一个介绍性文章中说明。关于这个结果的一个例子由Nemirovski给出。这也是robust optimization要发展近似算法的原因。这个领域目前只有5年时间，还有很多工作可以做。
要步入robust optimization 领域，需要掌握interior point method,semi-definite programming
和conic optimization。这些都是目前国际上运筹学方面的主流研究领域，应用十分广泛。
