椭球法是古老的优化方法，现在看来效率不高，现在主要用的是内点法，单纯形法。但我觉得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。