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。

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

参考：

1. localization methods 
2. EE364b