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

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

基本次梯度算法

编辑

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

 

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

 

步长的选取

编辑

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

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

收敛结果

编辑

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

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

有约束最优化

编辑

投影次梯度算法

编辑

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

最小化 

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

 

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

一般约束问题

编辑

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

最小化 

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

 

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

 

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

参考资料

编辑

外部链接

编辑