次梯度法

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

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

基本次梯度算法

记 $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 \$ 的次微分. 如果当前点为可行点, 算法采用目标函数的次梯度, 否则采用任一违反约束的函数的次微分.

参考资料

• 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