二、有限维的凸优化

第二章主要就是介绍了两种凸优化的方法，重心法和椭球法，这两种方法都很老了，可能现在用的已经不多了，但是其中的思想还在。

重心法

重心法首先把S_t初始化为函数的定义域凸集X，然后迭代方式如下：

vol代表的是体积

这个方法的本质和它的名字非常像，c_t就是重心。
第(1)步：注意这里的积分表达式写的非常奇怪，用的是一重积分的符号，但是实际上x是一个向量，公式想要表达的意思就是找重心（好像这并不等价于按维度各自积分）
第(2)步：形成一个新的S，这个新的S剔除了原来的集合S中函数值大于c_t的x。

简单解释：w是c_t点的次梯度，如果(2)中的不等式小于0，说明函数值沿c_t到x方向是递减的，否则就是递增的，所以这里的取交集的操作，把函数的最小值的域又缩小了一点。

所以重心法的本质就是：每次都找到当前集合A的重心，A代表最小值所在的集合，最初这个集合当然就是函数的定义域。然后每次都剔除一些点，是A越来越小，直到离最优解足够近。这里的关键问题是，这样的方法有多快，我们多久可以找到最优点。这里理论复杂度其实和二分法非常像，每次都找近似的中位数，然后剔除掉大的值，所以这个算法的理论复杂度和二分法的理论复杂度的形式非常像，是

其中，函数的值域是[-B, B]，n是x的维度。为什么有n这个也不难理解，毕竟二分的时候要朝n个方向二分。

定理2.1

根据这个定理可知，重心法的收敛速度是指数的，在凸优化中也称为线性收敛（之所以叫这个名字是因为，在收敛速度是指数的情况下，精度ε的位数每翻一倍（如从0.01变成0.0001），迭代次数就要增加一倍才行，即精度的位数和迭代次数呈线性关系）。

重心法实际上用的不多，因为求重心比较困难，并没有非常高效的算法。

定理2.1证明：

这里证明需要使用一个引理2.1

一开始看这个引理总感觉很奇怪，w应该平分凸集才对，实际上并非如此，w是任意过重心的平面，而凸集不一定关于原点对称

从上面的引理可以很容易看出，重心法每次剔除完后剩下的体积不超过(1-1/e)。因此很容易得到：

一个ε优的解所构成的集合是：

可以得知，vol(Xε)=ε^n * vol(X)

所以，当ε > (1-1/e)^t/n时，vol(Xε) > vol(S_t+1)，所以说，t次迭代后，我们的集合已经小于Xε了，而由函数的凸的性质可以得知f(x_ε) <= f(x^*) + 2εB，这个不难理解，因为凸函数一定增长越来越快的。得证！

椭球法

椭球的定义如下：

椭球法都依赖于引理2.2

语言描述一下，就是对于一个椭球，过中心点的平面w把它分成两半，总存在一个椭球，它包含小于0的那一半，且它的体积小于原椭球的体积的某个系数倍。并且定理还给出了新椭球的其中一个解

有了上面这个定理不难想到，椭球法就是说一个函数的定义域是一个凸集，这个凸集是一个椭球，然后我们可以通过不断的缩小这个椭球来逼近最优解（注意，即使一个函数的定义域不是椭球，我们也可以找到一个它的外接椭球）

这个引理的证明贼复杂，书上16~17页有，这里就不证明了。椭球法的步骤：

1. 找到函数的定义域的一个外接球（椭球的特例），即H₀=R²I_n
2. 利用一阶Oracle，对于任意的c_t，如果x属于定义域，则给出此处的次梯度，如果c_t不属于定义域，则给出c_t和定义域之间的一个分离平面，使得(x-c_t)w_t<=0。
3. 根据引理2.2的结论得出新的椭球，即根据引理2.2，这个椭球的体积满足：

4. 重复步骤2和2

书上对于上述步骤的描述如下：

定理2.2

书上没有给证明，但是感觉和重心法的证明应该非常类似才对。这个算法复杂度是O(n²log(1/ε))。之所以多了一个n，我想是因为引理2.2中描述的椭球体积比例关系的公式中有一个n。注意这个算法的理论复杂度比重心法要高，但是它的价值在于实际使用时比重心法要快，因为这个方法没有什么奇怪的操作，分离平面相对好找，而重心法中的重心却不好求。