次梯度法

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

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

基本次梯度算法

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

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

步长的选取

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

恒定步长，。
恒定间隔，，得出。
步长平方可加，但步长不可加，即步长满足
。
步长不可加但步长递减，即步长满足
。
间隔不可加但间隔递减，即，其中
。注意：上述步长是在算法执行前所确定的，不依赖于算法运行过程中产生的任何数据。这是与标准梯度下降法的显著区别。

收敛结果

对于恒定间隔的步长以及恒定步长，次梯度算法收敛到最优值的某个邻域，即
。基本次梯度算法的性能较差，因此一般的优化问题并不推荐使用。

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

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

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

一般约束问题

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

最小化

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

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

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

参考资料




外部链接
 EE364a  and  EE364b , a Stanford course  homepage

Category:最优化算法