fbpx
维基百科

次梯度法

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

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

基本次梯度算法

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

 

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

 

步长的选取

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

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

收敛结果

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

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

有约束最优化

投影次梯度算法

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

最小化 

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

 

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

一般约束问题

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

最小化 

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

 

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

 

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

参考资料

  • Bertsekas, Dimitri P. Nonlinear Programming. Cambridge, MA.: Athena Scientific. 1999. ISBN 1-886529-00-0. 

外部链接

次梯度法, 是求解凸函数最优化, 凸优化, 问题的一种迭代法, 能够用于不可微的目标函数, 当目标函数可微时, 对于无约束问题与梯度下降法具有同样的搜索方向, 虽然在实际的应用中, 比内点法和牛顿法慢得多, 但是可以直接应用于更广泛的问题, 只需要很少的存储需求, 然而, 通过将与分解技术结合, 有时能够开发出问题的简单分配算法, 目录, 基本次梯度算法, 步长的选取, 收敛结果, 有约束最优化, 投影次梯度算法, 一般约束问题, 参考资料, 外部链接基本次梯度算法, 编辑记f, displaystyle, mat. 次梯度法是求解凸函数最优化 凸优化 问题的一种迭代法 次梯度法能够用于不可微的目标函数 当目标函数可微时 对于无约束问题次梯度法与梯度下降法具有同样的搜索方向 虽然在实际的应用中 次梯度法比内点法和牛顿法慢得多 但是次梯度法可以直接应用于更广泛的问题 次梯度法只需要很少的存储需求 然而 通过将次梯度法与分解技术结合 有时能够开发出问题的简单分配算法 目录 1 基本次梯度算法 1 1 步长的选取 1 2 收敛结果 2 有约束最优化 2 1 投影次梯度算法 2 2 一般约束问题 3 参考资料 4 外部链接基本次梯度算法 编辑记f R n R displaystyle f mathbb R n to mathbb R 为定义在R n displaystyle mathbb R n 上的凸函数 次梯度算法使用以下的迭代格式 x k 1 x k a k g k displaystyle x k 1 x k alpha k g k 其中g k displaystyle g k 表示函数f displaystyle f 在x k displaystyle x k 的次梯度 如果 f displaystyle f 可微 他的次梯度就是梯度向量 f displaystyle nabla f 有时 g k displaystyle g k 不是函数f displaystyle f 在x k displaystyle x k 处的下降方向 因此采用一系列可能的f b e s t displaystyle f rm best 来追踪目标函数的极小值点 即 f b e s t k min f b e s t k 1 f x k displaystyle f rm best k min f rm best k 1 f x k 步长的选取 编辑 次梯度方法有许多可采用的步长 以下为5种能够保证收敛性的步长规则 恒定步长 a k a displaystyle alpha k alpha 恒定间隔 a k g g k 2 displaystyle alpha k gamma lVert g k rVert 2 得出 x k 1 x k 2 g displaystyle lVert x k 1 x k rVert 2 gamma 步长平方可加 但步长不可加 即步长满足a k 0 k 1 a k 2 lt k 1 a k displaystyle alpha k geq 0 qquad sum k 1 infty alpha k 2 lt infty qquad sum k 1 infty alpha k infty 步长不可加但步长递减 即步长满足a k 0 lim k a k 0 k 1 a k displaystyle alpha k geq 0 qquad lim k to infty alpha k 0 qquad sum k 1 infty alpha k infty 间隔不可加但间隔递减 即a k g k g k 2 displaystyle alpha k gamma k lVert g k rVert 2 其中g k 0 lim k g k 0 k 1 g k displaystyle gamma k geq 0 qquad lim k to infty gamma k 0 qquad sum k 1 infty gamma k infty 注意 上述步长是在算法执行前所确定的 不依赖于算法运行过程中产生的任何数据 这是与标准梯度下降法的显著区别 收敛结果 编辑 对于恒定间隔的步长以及恒定步长 次梯度算法收敛到最优值的某个邻域 即 lim k f b e s t k f lt ϵ displaystyle lim k to infty f rm best k f lt epsilon 基本次梯度算法的性能较差 因此一般的优化问题并不推荐使用 有约束最优化 编辑投影次梯度算法 编辑 次梯度法的一个扩展版本是投影次梯度法 该方法用于求解有约束最优化问题 最小化f x x C displaystyle f x quad x in mathcal C 其中C displaystyle mathcal C 为凸集 投影次梯度算方法的迭代公式为 x k 1 P x k a k g k displaystyle x k 1 P left x k alpha k g k right 其中P displaystyle P 是在C displaystyle mathcal C 上的投影 g k displaystyle g k 是在点x k displaystyle x k 处f displaystyle f 的次梯度 一般约束问题 编辑 次梯度法可扩展到求解不等式约束问题 最小化f 0 x f i x 0 i 1 m displaystyle f 0 x quad f i x leq 0 quad i 1 dots m 其中f i displaystyle f i 为凸函数 该算法与无约束优化问题具有相同的形式 x k 1 x k a k g k displaystyle x k 1 x k alpha k g k 其中a k gt 0 displaystyle alpha k gt 0 是步长 g k displaystyle g k 是目标函数或约束函数在x displaystyle x 处的次梯度 g k f 0 x if f i x 0 i 1 m f j x for some j such that f j x gt 0 displaystyle g k begin cases partial f 0 x amp text if f i x leq 0 forall i 1 dots m partial f j x amp text for some j text such that f j x gt 0 end cases 其中 f displaystyle partial f 代表f displaystyle f 的次微分 如果当前点为可行点 算法采用目标函数的次梯度 否则采用任一违反约束的函数的次微分 参考资料 编辑Bertsekas Dimitri P Nonlinear Programming Cambridge MA Athena Scientific 1999 ISBN 1 886529 00 0 Shor Naum Z Minimization Methods for Non differentiable Functions Springer Verlag 1985 ISBN 0 387 12763 1 外部链接 编辑EE364a 页面存档备份 存于互联网档案馆 and EE364b 页面存档备份 存于互联网档案馆 a Stanford course homepage 取自 https zh wikipedia org w index php title 次梯度法 amp oldid 69455912, 维基百科,wiki,书籍,书籍,图书馆,

文章

,阅读,下载,免费,免费下载,mp3,视频,mp4,3gp, jpg,jpeg,gif,png,图片,音乐,歌曲,电影,书籍,游戏,游戏。