BFGS算法原理

我会带着你远行 2022-04-22 13:16 214阅读 0赞

今天，我来讲一种在机器学习中常用到的优化算法，叫做BFGS算法。BFGS算法被认为是数值效果最好的拟牛顿

法，并且具有全局收敛性和超线性收敛速度。那么接下来将会详细讲解。

Contents

1. 什么是拟牛顿法

2. 拟牛顿法原理

3. DFP算法原理

4. BFGS算法原理

5. BFGS算法的实现

1. 什么是拟牛顿法

前面Logisitc回归讲解中，我介绍了牛顿法。牛顿法的特点是：收敛速度快，迭代次数少，但是当Hessian

矩阵很稠密时，每次迭代的计算量很大。随着数据规模的增大，那么Hessian矩阵会越大，需要的存储空间会

增多，计算量也会增大，有时候大到不可计算，所以针对海量数据的计算，牛顿法不再适用。

拟牛顿法是在牛顿法的基础上引入了Hessian矩阵的近似矩阵，避免每次迭代都计算Hessian矩阵的逆，它

的收敛速度介于梯度下降法和牛顿法之间。拟牛顿法跟牛顿法一样，也是不能处理太大规模的数据，因为计算

量和存储空间会开销很多。拟牛顿法虽然每次迭代不像牛顿法那样保证是最优化的方向，但是近似矩阵始终是

正定的，因此算法始终是朝着最优化的方向在搜索。

2. 拟牛顿法原理

拟牛顿法的基本思想是在牛顿法中用Hessian矩阵的某个近似矩阵来代替它。在高数中，学过泰勒公式，如下

关于泰勒展开的更多内容，可以参考这里：泰勒公式介绍，泰勒公式应用。泰勒公式是用一个近似的多项式

来代替原来复杂的函数表达式。对于拟牛顿法来说，构造二次模型。如下

忽略高阶无穷小部分，进行求导得到

令，那么得到

牛顿迭代中，要求Hessian矩阵的逆，计算量增大，而拟牛顿法是用Hessian矩阵的逆矩阵来代替Hessian

矩阵。即如下迭代式

这个方程就是拟牛顿方程，这就是拟牛顿的核心公式啊。所以最关键的问题是如何得到每一步的。关

于这个问题，又有很多种方法来迭代计算，接下来主要介绍DFP算法和BFGS算法。

3. DFP算法原理

在上面的拟牛顿法原理介绍中，已经得到拟牛顿方程。现在来介绍一种算法，叫做DFP算法，它是Davidon、

Fletcher、Powell三位牛人名字的首字母缩写。在DFP算法中，假设有如下迭代

其中和均为实数，和均为维向量，那么带入上述的拟牛顿方程中，有如下推导

那么进一步有

接下来，我们重新记一下符号，设

那么得到

现在只要我们求出了，，，，那么问题也就解决了。那么为了更容易看出结论，继续作如下变换

那么只需要如下几个条件成立就可以了

带入原式最终得到

由于虽然是有矩阵相乘，但是实际上是向量相乘，然后又矩阵相加，所以时间复杂度为，比起普通

牛顿迭代矩阵求逆来说，时间复杂度大大降低，这就是DFP算法的原理。

4. BFGS算法原理

上面的DFP算法中，已经很好地解决了问题，接下来，继续学习BFGS算法。它是Broyden，Fletcher，

Goldfarb，Shanno四位牛人发明出来到现在的40多年时间里，它仍然被认为是最好的拟牛顿算法。假设

迭代如下

这样最终得到迭代式如下

这就是BFGS算法的原理。

5. BFGS算法的实现

BFGS算法的C++实现参考这里。在Python中，有一个优化算法工具，叫做scipy。scipy中的optimize子

包中提供了常用的最优化算法函数实现。我们可以直接调用这些函数完成我们的优化问题。optimize中函数

最典型的特点就是能够从函数名称上看出是使用了什么算法，可以参考这里。比如BFGS算法的用法如下

运行结果如下

\---------------------   
作者：acdreamers   
来源：CSDN   
原文：https://blog.csdn.net/ACdreamers/article/details/44664941   
版权声明：本文为博主原创文章，转载请附上博文链接！

发表评论取消回复

表情：

评论列表（有 0 条评论，214人围观）

还没有评论，来说两句吧...

相关阅读

相关【SciPy库】scipy.optimize.fmin_l_bfgs_b进行L-BFGS优化

【时间】2020.01.07 【题目】【SciPy库】scipy.optimize.fmin\_l\_bfgs\_b进行L-BFGS优化具体用法参考官方文档：[scipy

我就是我/ 2023年06月28日 06:18/ 0 赞/ 1 阅读

相关 dfp 算法matlab,MATLAB拟牛顿法之DFP与BFGS算法

DFP算法原理由于博主使用WPS编辑的文本，公式无法赋值粘贴，这里以截图的方法给出了推导过程。博主会上传该DOC文档。 ![watermark,type\_ZmFuZ3p

我就是我/ 2023年01月16日 09:54/ 0 赞/ 125 阅读

相关 dfp matlab,MATLAB拟牛顿法之DFP与BFGS算法

DFP算法原理由于博主使用WPS编辑的文本，公式无法赋值粘贴，这里以截图的方法给出了推导过程。博主会上传该DOC文档。 ![a02a3020e0af0aca826eb79

﹏ヽ暗。殇╰゛Y/ 2023年01月16日 04:56/ 0 赞/ 148 阅读

相关 BFGS优化算法简介

【翻译自：[ A Gentle Introduction to the BFGS Optimization Algorithm][A Gentle Introduction

左手的ㄟ右手/ 2022年10月17日 00:48/ 0 赞/ 159 阅读

相关机器学习算法1牛顿法,拟牛顿法,DFP,BFGS,L-BFGS 原理及代码详解(4)

![70][] ![70 1][] ![70 2][] 此上最后部分LBFGS算法的展开式有疑议正确参考如下图所示: ![70 3]

- 日理万妓/ 2022年05月27日 12:23/ 0 赞/ 200 阅读

相关机器学习算法1牛顿法,拟牛顿法,DFP,BFGS,L-BFGS 原理及代码详解(3)

![70][] ![70 1][] ![70 2][] ![70 3][] 拟牛顿_BFGS算法算法描述:

川长思鸟来/ 2022年05月27日 12:21/ 0 赞/ 205 阅读

相关机器学习算法1牛顿法,拟牛顿法,DFP,BFGS,L-BFGS 原理及代码详解(2)

![70][] ![70 1][] ![70 2][] ![70 3][] 牛顿法的优点是具有二阶收敛速度，缺点是：

深碍√TFBOYSˉ_/ 2022年05月27日 12:20/ 0 赞/ 362 阅读

相关机器学习算法1牛顿法,拟牛顿法,DFP,BFGS,L-BFGS 原理及代码详解(1)

一.牛顿法 Taylor公式 – Maclaurin公式: ![70][] ![70 1][] 1.求根问题: 牛顿法的最初提出是用来求解方程的根的。我们

青旅半醒/ 2022年05月27日 10:08/ 0 赞/ 351 阅读

相关 BFGS算法原理

今天，我来讲一种在机器学习中常用到的优化算法，叫做BFGS算法。BFGS算法被认为是数值效果最好的拟牛顿法，并且具有全局收敛性和超线性收敛速度。那么接下来将会详细讲解。

我会带着你远行/ 2022年04月22日 13:16/ 0 赞/ 215 阅读

相关数值优化：理解L-BFGS算法

[为什么80%的码农都做不了架构师？>>> ][80_] ![hot3.png][] ![数值优化：理解L-BFGS算法][L-BFGS] 译自《Numerical Op

小灰灰/ 2022年01月15日 10:43/ 0 赞/ 132 阅读