椭球法是古老的优化方法,现在看来效率不高,现在主要用的是内点法,单纯形法。但我觉得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。
1 2 3 | gt = g/sqrt(g'*P*g); x = x - 1/(n+1)*P*gt; P = n^2/(n^2-1)*(P-2/(n+1)*P*gt*gt'*P); |
上图是第一步迭代到第三步,可以看出椭圆越来越小,但是包含那个最优点。大概40步就有比较理想的结果。具体代码见github。