次梯度法

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

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

基本次梯度算法

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

$x^{(k+1)}=x^{(k)}-{\alpha }_k{g}^{(k)}$

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

$f_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}^{(k)}=\min \{f_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}^{(k-1)},f(x^{(k)})\}$。

步长的选取

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

• 恒定步长，${\alpha }_k=\alpha$。
• 恒定间隔，${\alpha }_k=\gamma /\Vert g^{(k)}{\Vert }_2$，得出$\Vert x^{(k+1)}-x^{(k)}{\Vert }_2=\gamma$。
• 步长平方可加，但步长不可加，即步长满足

${\alpha }_k\ge 0,\sum _{k=1}^{\mathrm{\infty }}{\alpha }_k^2<\mathrm{\infty },\sum _{k=1}^{\mathrm{\infty }}{\alpha }_k=\mathrm{\infty }$。

• 步长不可加但步长递减，即步长满足

${\alpha }_k\ge 0,\underset{k\to \mathrm{\infty }}{\lim }{\alpha }_k=0,\sum _{k=1}^{\mathrm{\infty }}{\alpha }_k=\mathrm{\infty }$。

• 间隔不可加但间隔递减，即${\alpha }_k={\gamma }_k/\Vert g^{(k)}{\Vert }_2$，其中

${\gamma }_k\ge 0,\underset{k\to \mathrm{\infty }}{\lim }{\gamma }_k=0,\sum _{k=1}^{\mathrm{\infty }}{\gamma }_k=\mathrm{\infty }$。注意：上述步长是在算法执行前所确定的，不依赖于算法运行过程中产生的任何数据。这是与标准梯度下降法的显著区别。

收敛结果

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

$\underset{k\to \mathrm{\infty }}{\lim }{f}_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}^{(k)}-f^{*}<ϵ$。基本次梯度算法的性能较差，因此一般的优化问题并不推荐使用。

有约束最优化

投影次梯度算法

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

最小化$f(x)x\in 𝒞$

其中$𝒞$为凸集。投影次梯度算方法的迭代公式为

$x^{(k+1)}=P(x^{(k)}-{\alpha }_k{g}^{(k)})$

其中$P$是在$𝒞$上的投影，$g^{(k)}$是在点$x^{(k)}$处$f$的次梯度。

一般约束问题

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

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

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

$x^{(k+1)}=x^{(k)}-{\alpha }_k{g}^{(k)}$

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

$g^{(k)}=\{\begin{array}{cc}\partial f_0(x)& \text{ if }{f}_i(x)\le 0\mathrm{\forall }i=1\dots m\\ \partial f_j(x)& \text{ for some }j\text{ such that }{f}_j(x)>0\end{array}$

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

参考资料

• Template:Cite book

• Template:Cite book

外部链接

• EE364a Template:Wayback and EE364b Template:Wayback, a Stanford course homepage