第二章主要就是介绍了两种凸优化的方法,重心法和椭球法,这两种方法都很老了,可能现在用的已经不多了,但是其中的思想还在。
重心法
重心法首先把St初始化为函数的定义域凸集X,然后迭代方式如下:
vol代表的是体积这个方法的本质和它的名字非常像,ct就是重心。
第(1)步:注意这里的积分表达式写的非常奇怪,用的是一重积分的符号,但是实际上x是一个向量,公式想要表达的意思就是找重心(好像这并不等价于按维度各自积分)
第(2)步:形成一个新的S,这个新的S剔除了原来的集合S中函数值大于ct的x。
简单解释:w是ct点的次梯度,如果(2)中的不等式小于0,说明函数值沿ct到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(St+1),所以说,t次迭代后,我们的集合已经小于Xε了,而由函数的凸的性质可以得知f(xε) <= f(x*) + 2εB,这个不难理解,因为凸函数一定增长越来越快的。得证!
椭球法
椭球的定义如下:
椭球法都依赖于引理2.2
语言描述一下,就是对于一个椭球,过中心点的平面w把它分成两半,总存在一个椭球,它包含小于0的那一半,且它的体积小于原椭球的体积的某个系数倍。并且定理还给出了新椭球的其中一个解有了上面这个定理不难想到,椭球法就是说一个函数的定义域是一个凸集,这个凸集是一个椭球,然后我们可以通过不断的缩小这个椭球来逼近最优解(注意,即使一个函数的定义域不是椭球,我们也可以找到一个它的外接椭球)
这个引理的证明贼复杂,书上16~17页有,这里就不证明了。椭球法的步骤:
- 找到函数的定义域的一个外接球(椭球的特例),即H0=R2In
- 利用一阶Oracle,对于任意的ct,如果x属于定义域,则给出此处的次梯度,如果ct不属于定义域,则给出ct和定义域之间的一个分离平面,使得(x-ct)wt<=0。
- 根据引理2.2的结论得出新的椭球,即根据引理2.2,这个椭球的体积满足:
- 重复步骤2和2
书上对于上述步骤的描述如下:
定理2.2
书上没有给证明,但是感觉和重心法的证明应该非常类似才对。这个算法复杂度是O(n2log(1/ε))。之所以多了一个n,我想是因为引理2.2中描述的椭球体积比例关系的公式中有一个n。注意这个算法的理论复杂度比重心法要高,但是它的价值在于实际使用时比重心法要快,因为这个方法没有什么奇怪的操作,分离平面相对好找,而重心法中的重心却不好求。
网友评论