次梯度法

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

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

基本次梯度算法

记$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}\geq 0,\qquad \sum _{k=1}^{\infty }\alpha _{k}^{2}<\infty ,\qquad \sum _{k=1}^{\infty }\alpha _{k}=\infty$。

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

$\alpha _{k}\geq 0,\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}\geq 0,\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\$的次微分。如果当前点为可行点，算法采用目标函数的次梯度，否则采用任一违反约束的函数的次微分。

参考资料

• Bertsekas, Dimitri P. Nonlinear Programming. Cambridge, MA.: Athena Scientific. 1999. ISBN 1-886529-00-0. 

• Shor, Naum Z. Minimization Methods for Non-differentiable Functions. Springer-Verlag. 1985. ISBN 0-387-12763-1. 

外部链接

• EE364a （页面存档备份，存于互联网档案馆） and EE364b （页面存档备份，存于互联网档案馆）, a Stanford course homepage