美文网首页
二、有限维的凸优化

二、有限维的凸优化

作者: cheerss | 来源:发表于2018-09-09 19:52 被阅读0次

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

重心法

重心法首先把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页有,这里就不证明了。椭球法的步骤:

  1. 找到函数的定义域的一个外接球(椭球的特例),即H0=R2In
  2. 利用一阶Oracle,对于任意的ct,如果x属于定义域,则给出此处的次梯度,如果ct不属于定义域,则给出ct和定义域之间的一个分离平面,使得(x-ct)wt<=0。
  3. 根据引理2.2的结论得出新的椭球,即根据引理2.2,这个椭球的体积满足:
  1. 重复步骤2和2

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

定理2.2

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

相关文章

  • 二、有限维的凸优化

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

  • 2018-03-17/凸优化(Convex Optimizati

    No.1 凸优化概念的理解 凸 优化 N0.2 最小二乘估计(Least Squares Estimator)的公...

  • 凸优化(二)——凸集

    〇、说明 凸优化主要学习《凸优化》(Stephen Boyd等著,王书宁等译)[1]这本书。学习过程中,对其内容的...

  • 机器学习(6)——凸优化理论(一)

    概述   凸优化,或叫做凸最优化,凸最小化,是数学最优化的一个子领域,研究定义于凸集中的凸函数最小化的问题。凸优化...

  • 凸优化笔记2-主要内容

    笔记主要内容 凸集、凸函数、凸优化 凸优化理论 若干算法

  • Convex Optimization Note 1 | Int

    凸优化,或叫做凸最优化,凸最小化,是数学最优化的一个子领域,研究定义于凸集中的凸函数最小化的问题。凸优化在某种意义...

  • 凸优化有什么用

    本文结构: 凸优化有什么用? 什么是凸优化? 凸优化有什么用? 鉴于本文中公式比较多,先把凸优化的意义写出来吧,就...

  • 凸优化相关概念学习笔记

    前言 由于凸优化具有一些很好的性质,比如: 凸问题中的局部最优解就是全局最优解 凸优化理论中的拉格朗日对偶为凸优化...

  • 凸优化&非凸优化

    凸优化指的是,如果得到了局部最优,那么这个局部最优就是全局最优。 讲凸优化就涉及到凸函数和凸集合集合C内任意两点间...

  • 凸优化(二)凸锥与常见凸集

    1. 概述 那么开始第二期,介绍凸锥和常见的集合,这期比较短(因为公式打得太累了),介绍凸集和凸锥与仿射集的意义在...

网友评论

      本文标题:二、有限维的凸优化

      本文链接:https://www.haomeiwen.com/subject/taedgftx.html