凸优化-次梯度算法

2020年08月06日 阅读数:315
这篇文章主要向大家介绍凸优化-次梯度算法,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。
02 October 2015

1. 次梯度

在优化问题中,咱们能够对目标函数为凸函数的优化问题采用梯度降低法求解,可是在实际状况中,目标函数并不必定光滑、或者到处可微,这时就须要用到次梯度降低算法。算法

次梯度(*Subgradient*)与梯度的概念相似,凸函数的First-order characterization是指若是函数f可微,那么当且仅当 为凸集,且对于 ,使得 ,则函数 为凸函数。这里所说的次梯度是指在函数 上的点 知足如下条件的

其中,函数 不必定要是凸函数,非凸函数也能够,即对于凸函数或者非凸函数而言,知足上述条件的 均为函数在该点的次梯度。可是,凸函数老是存在次梯度(能够利用epigraph和支撑平面理论证实),而非凸函数则不必定存在次梯度,即便 可微。该定义说明,用次梯度对原函数作出的一阶展开估计老是比真实值要小。dom

很明显,凸函数的次梯度必定存在,若是函数 在点 处可微,那么 ,为函数在该点的梯度,且惟一;若是不可微,则次梯度不必定惟一。可是对于非凸函数,次梯度则不必定存在,也不必定惟一。例如,凸函数 范数为凸函数,但不知足到处可微的条件,所以,函数的次梯度不必定惟一,以下图:函数

左一图为 ,函数在 时,次梯度惟一,且 ;当 时,次梯度为 中的任意一个元素;优化

左二图为 ,函数在 时,次梯度惟一,且 ;当 时,次梯度为 中的任意一个元素;atom

一样,绝对值函数 和最大值函数 在不可微点处次梯度也不必定惟一,以下图:spa

对于左二函数而言,其在知足 的点处,次梯度为任意一条直线在向量 之间。.net

同理,咱们还能够给出次微分(subdifferential)的定义,即:
code

  • 次微分是闭合且为凸集;
  • 若是函数 在点 处可微,那么次微分等于梯度;
  • 凸函数的次微分不为空,但非凸函数则不必定。

若是咱们还记得Normal cone是指给定任意集合 和点 ,那么咱们能够看出,对于集合 的边界上点的Normal cone就是函数 在该点的次微分。其中,

证实:orm

由于,对于函数的次梯度会知足 ,所以,ip

  • 对于 ,不知足Normal cone的定义;
  • 对于 ,知足Normal cone的定义;

既证。

2. 次梯度的性质

  • Scalingf:
  • Addition:
  • Affine composition:若是 ,那么
  • Finite pointwise maximum:若是 ,那么 ,意味着函数 的次微分等于全部能取得最大值的函数 在点 处的微分,具体实例可参考以前提到的最大值函数部分。

3. 为何要计算次梯度?

对于光滑的凸函数而言,咱们能够直接采用梯度降低算法求解函数的极值,可是当函数不到处光滑,到处可微的时候,梯度降低就不适合应用了。所以,咱们须要计算函数的次梯度。对于次梯度而言,其没有要求函数是否光滑,是不是凸函数,限定条件不多,因此适用范围更广。

次梯度具备如下优化条件(subgradient optimality condition):对于任意函数 (不管是凸仍是非凸),函数在点 处取得最值等价于:

即,当且仅当0属于函数 在点 处次梯度集合的元素时, 为最优解。

证实:

证实很简单,当次梯度 时,对于全部 ,存在 ,因此, 为最优解,即证。

4. 次梯度算法

次梯度算法(Subgradient method)与梯度降低算法相似,仅仅用次梯度代替梯度,即:

其中, ,为 在点 处的次梯度。

与梯度降低算法不一样的地方在于,次梯度算法并非降低算法,每次对于参数的更新并不能保证代价函数是呈单调递减的趋势,所以,通常请款下咱们选择:

另外一点与梯度降低算法不一样的是:次梯度算法没有明确的步长选择方法,相似Exact line searchBacktracking line search的方法,只有步长选择准则,具体以下:

  • Fixed step sizes: 
  • Diminishing step sizes: 选择知足如下条件的 :


Diminishing step sizes方法主要是保证步长逐渐变小,同时,变化幅度还不会特别快。这里须要注意的是,次梯度算法并不像梯度降低同样,能够在每一次迭代过程当中自适应的计算这次步长(adaptively computed),而是事先设定好的(pre-specified)。

可是,不少人会提出这样一个问题,若是你不能保证次梯度是单调的,如何保证最后能够收敛?

定理:若是 为凸函数,且知足Lipschitz continuous with G,若是固定步长为 ,那么次梯度算法知足:

证实:

对于 ,其中 。所以,咱们能够展开下式为:

由于, ,且由凸函数一阶性质可得 ,上式不等式能够写为:

对于任意 ,求和上式能够得到:

由于, ,因此:

若是令 为迭代 次内的最优解,那么 ,其中, ,所以:

因此,咱们能够获得

同时,由于函数知足Lipschitz continuous with G,因此, ,即函数的次梯度

综上所述,咱们能够证实下式成立: