次梯度法是求解凸函数最优化（凸优化）问题的一种迭代法。次梯度法能够用于不可微的目标函数。当目标函数可微时，对于无约束问题次梯度法与梯度下降法具有同样的搜索方向。
虽然在实际的应用中，次梯度法比内点法和牛顿法慢得多，但是次梯度法可以直接应用于更广泛的问题，次梯度法只需要很少的存储需求。然而，通过将次梯度法与分解技术结合，有时能够开发出问题的简单分配算法。
基本次梯度算法
记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 。
*步长不可加但步长递减，即步长满足
:\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^* 。基本次梯度算法的性能较差，因此一般的优化问题并不推荐使用。
有约束最优化
投影次梯度算法
次梯度法的一个扩展版本是投影次梯度法，该方法用于求解有约束最优化问题
:最小化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 \ 的次微分。如果当前点为可行点，算法采用目标函数的次梯度，否则采用任一违反约束的函数的次微分。
参考资料
*
*
外部链接
- [http://www.stanford.edu/class/ee364a/ EE364a] and [http://www.stanford.edu/class/ee364b/ EE364b] , a Stanford course homepage
评论 (0)