次梯度法是求解凸函数最优化（凸优化）问题的一种迭代法。次梯度法能够用于不可微的目标函数。当目标函数可微时，对于无约束问题次梯度法与梯度下降法具有同样的搜索方向。虽然在实际的应用中，次梯度法比内点法和牛顿法慢得多，但是次梯度法可以直接应用于更广泛的问题，次梯度法只需要很少的存储需求。然而，通过将次梯度法与分解技术结合，有时能够开发出问题的简单分配算法。

基本次梯度算法

记 为定义在 上的凸函数。次梯度算法使用以下的迭代格式：

其中 表示函数 f在 的次梯度. 如果 f可微，他的次梯度就是梯度向量 有时，不是函数 f在 处的下降方向。因此采用一系列可能的 来追踪目标函数的极小值点，即

步长的选取

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

1、恒定步长，

2、恒定间隔， ，得出。

3、步长平方可加，但步长不可加，即步长满足

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

5、间隔不可加但间隔递减，即，其中

注意：上述步长是在算法执行前所确定的，不依赖于算法运行过程中产生的任何数据。这是与标准梯度下降法的显著区别。

收敛结果

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

基本次梯度算法的性能较差，因此一般的优化问题并不推荐使用。

有约束最优化

投影次梯度算法

次梯度法的一个扩展版本是投影次梯度法，该方法用于求解有约束最优化问题：最小化 ,其中 C为凸集。投影次梯度算方法的迭代公式为:

其中P是在C的投影，是在点 处 的次梯度。

一般约束问题

次梯度法可扩展到求解求解不等式约束问题，最小化，其中 为凸函数。该算法与无约束优化问题具有相同的形式：

其中，是步长，是目标函数或约束函数在 x处的次梯度

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

参考资料