Ellipsoid Method

椭球法是古老的优化方法,现在看来效率不高,现在主要用的是内点法单纯形法。但我觉得ellipsoid method的思想比较独特,有必要好好了解一下。

主要思想:

考虑一个函数,只有一个最小值而且是凸的。先找到一个凸的集合包含这个点,然后按照一定规则收缩这个集合,到最后这个集合很小且包含那个点,那就达到目的了。

主要有两个问题,1.是怎样的集合 2.如何收缩集合。集合可以是一个多面体,这时就是cutting-plane method。收缩是根据subgradient g来的,因为f(x) >= f(x0) + g'(x-x0)。 可以舍去那一部分平面。达到收缩的目的。但是这里cutting-plane method慢啊,主要是找下一个x0很慢,要保证迭代少,必须要使x0尽可能平方集合。

所以就有了ellipsoid method。每次x0就是椭球的中心,然后使的椭球能包含上一次迭代的椭球和剩下的平面的交即可。这个简单也是最重要的部分,有人早就解决了。详见half ball lemma.

迭代过程:

为了把椭圆从矩阵的形式转换为能画的形式,费了一点劲。但是完美的结果,让我彻底相信了这个方法。迭代只有三步。但证明还是有点麻烦,见上面的half ball lemma。

ellipsoid_step1 ellipsoid_step2 ellipsoid_step3

上图是第一步迭代到第三步,可以看出椭圆越来越小,但是包含那个最优点。大概40步就有比较理想的结果。具体代码见github

参考:

  1. localization methods 
  2. EE364b