次梯度法

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

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

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

基本次梯度算法[编辑]

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

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

其中g^{(k)}表示函数 f \ 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 \ 的次微分。如果当前点为可行点,算法采用目标函数的次梯度,否则采用任一违反约束的函数的次微分。

参考资料[编辑]

外部链接[编辑]