跳转到内容

次梯度法

本页使用了标题或全文手工转换
维基百科,自由的百科全书

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

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

基本次梯度算法

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

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

步长的选取

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

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

收敛结果

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

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

有约束最优化

投影次梯度算法

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

最小化

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

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

一般约束问题

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

最小化

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

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

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

参考资料

外部链接