次梯度法

维基百科,自由的百科全书
跳转至: 导航搜索

次梯度法是求解凸函数最优化凸优化)问题的一种迭代法. 次梯度法能够用于不可微的目标函数. 当目标函数可微时, 对于无约束问题次梯度法与梯度下降法具有同样的搜索方向.

虽然在实际的应用中, 次梯度法比内点法牛顿法慢得多, 但是次梯度法可以直接应用于更广泛的问题, 次梯度法只需要很少的存储需求. 然而, 通过将次梯度法与分解技术结合, 有时能够开发出问题的简单分配算法.

基本次梯度算法[编辑]

f:\mathbb{R}^n \to \mathbb{R} 为定义在 \mathbb{R}^n 上的凸函数. 次梯度算法使用以下的迭代格式

x^{(k+1)} = x^{(k)} - \alpha_k g^{(k)} \

其中 g^{(k)} 表示函数  f \ at x^{(k)} \ 次梯度. 如果 f \  可微, 他的次梯度就是梯度向量 \nabla f . 有时, -g^{(k)} 不是函数 f \  x^{(k)} 处的下降方向. 因此采用一系列可能的 f_{\rm{best}} \ 来追踪目标函数的极小值点, 即

f_{\rm{best}}^{(k)} = \min\{f_{\rm{best}}^{(k-1)} ,  f(x^{(k)}) \}.

步长的选取[编辑]

次梯度方法有许多可采用的步长. 以下为 5 种能够保证收敛性的步长规则

  • 恒定步长, \alpha_k = \alpha.
  • 恒定间隔, \alpha_k = \gamma/\lVert g^{(k)}  \rVert_2, 得出 \lVert x^{(k+1)} - x^{(k)}  \rVert_2 = \gamma.
  • 步长平方可加, 但步长不可加, 即步长满足
\alpha_k\geq0,\qquad\sum_{k=1}^\infty \alpha_k^2 <  \infty,\qquad \sum_{k=1}^\infty \alpha_k = \infty.
  • 步长不可加但步长递减, 即步长满足
\alpha_k\geq0,\qquad \lim_{k\to\infty} \alpha_k = 0,\qquad  \sum_{k=1}^\infty \alpha_k = \infty.
  • 间隔不可加但间隔递减, 即\alpha_k = \gamma_k/\lVert g^{(k)}  \rVert_2, 其中
\gamma_k\geq0,\qquad \lim_{k\to\infty} \gamma_k = 0,\qquad  \sum_{k=1}^\infty \gamma_k = \infty.

注意: 上述步长是在算法执行前所确定的, 不依赖于算法运行过程中产生的任何数据. 这是与标准梯度下降法的显著区别.

收敛结果[编辑]

对于恒定间隔的步长以及恒定步长, 次梯度算法收敛到最优值的某个邻域, 即

\lim_{k\to\infty} f_{\rm{best}}^{(k)} - f^*  <\epsilon.

基本次梯度算法的性能较差,因此一般的优化问题并不推荐使用。

有约束最优化[编辑]

投影次梯度算法[编辑]

次梯度法的一个扩展版本是投影次梯度法, 该方法用于求解有约束最优化问题

最小化 f(x) \ \quad x\in\mathcal{C}

其中 \mathcal{C} 为凸集. 投影次梯度算方法的迭代公式为

x^{(k+1)} = P \left(x^{(k)} - \alpha_k g^{(k)} \right)

其中 P 是在 \mathcal{C} 上的投影, g^{(k)} 是在点 x^{(k)}f \   的次梯度.

一般约束问题[编辑]

次梯度法可扩展到求解求解不等式约束问题

最小化 f_0(x) \quad f_i (x) \leq 0,\quad i = 1,\dots,m

其中 f_i 为凸函数. 该算法与无约束优化问题具有相同的形式

x^{(k+1)} = x^{(k)} - \alpha_k g^{(k)} \

其中 \alpha_k>0 是步长, g^{(k)} 是目标函数或约束函数在 x 处的次梯度

g^{(k)} = 
\begin{cases} 
  \partial f_0 (x)  & \text{ if } f_i(x) \leq 0 \; \forall i = 1  \dots m \\
  \partial f_j (x)  & \text{ for some } j \text{ such that } f_j(x)  > 0 
\end{cases}

其中 \partial f 代表 f \ 的次微分. 如果当前点为可行点, 算法采用目标函数的次梯度, 否则采用任一违反约束的函数的次微分.

参考资料[编辑]

外部链接[编辑]