本站原创文章，转载请说明来自《老饼讲解-BP神经网络》www.bbbdata.com
BFGS是Broyden、Fletcher、Goldfarb、Shanno四人的合称，它是目前效果最佳的拟牛顿算法
本文讲解BFGS算法的原理、公式推导以及算法流程，并展示BFGS算法的代码实现
通过本文，可以快速了解BFGS拟牛顿算法是什么，以及如何用代码具体实现一个BFGS算法
本节介绍BFGS的原理，以及相关公式推导
BFGS-算法原理
BFGS算法是一种拟牛顿优化算法，它是目前最常用、最具效果的拟牛顿算法
它的命名来自四个人名：Broyden、Fletcher、Goldfarb、Shanno，合起来就是BFGS
要了解BFGS算法， 需要先了解拟牛顿算法，下面简单回顾拟牛顿算法
拟牛顿算法
拟牛顿法的迭代公式如下：
其中，是目标函数在处的梯度
对于，需满足如下条件：
(1)
该式称为拟牛顿条件
其中， ，即第k-1次的迭代量
，即第k-1次迭代后梯度的增量
(2) 是正定矩阵
要求是正定矩阵，是为了保障迭代量一定是下降量
的取值方法不是固定的，不同的拟牛顿算法，就有不同的取值方法
BFGS算法
BFGS算法就是拟牛顿算法的一种具体实现
在拟牛顿法中，必须保证B满足拟牛顿条件，即：
即：
BFGS算法假设由如下三个矩阵组成 ：
则拟牛顿条件变为：
可知，将所在项分别凑出其余两项时，上式就可成立，即：
(1)
(2)
因此，BFGS算法构造了以下的公式，以满足上述两条公式，从而满足拟牛顿条件
只要简单将它们代入(1)(2) 式，消掉分子分母，即可验证它们是符合(1)(2) 式
当初始值为正定矩阵时，按上式的迭代，会一直都是正定矩阵，具体证明略
BFGS迭代公式-总结
总的来说，BFGS的迭代公式为：
其中，是目标函数在处的梯度
的初始值为一个正定矩阵，它的迭代公式如下：
其中，
本节介绍BFGS算法的具体算法流程
BFGS算法流程
BFGS算法是一种拟牛顿算法，它提供的迭代量h仅仅是一个下降量
如果只按照h进行迭代，会很不可控，因此，在实际应用中，一般需要搭配搜索算法来确定迭代步长
BFGS算法的具体流程如下：
一、初始化
1. 初始化解，矩阵
B必须初始化为一个正定矩阵，例如单位矩阵
2. 计算初始梯度
二、迭代
1. 计算迭代量：
2. 线性搜索迭代步长
(1) 线性搜索迭代步长
(2) 如果找到合适的学习率，则更新迭代量：
(3) 如果没找到合适的学习率，则退出训练
3. 更新
4. 更新梯度
(1) 先保存当前的G为，再计算当前梯度G
(2) 计算G的增量：
5. 更新
6. 检查退出条件
(1) 是否已达到最大迭代次数
(2) 梯度是否过小
三、输出
输出最终的解x
附：线性搜索的算法流程
输入如下：
1. 目标函数：
2. 当前搜索方向：
3. 当前梯度：
流程如下：
一、设置搜索参数
初始学习率：
设置衰减系数：
设置最大搜索次数：
设置搜索阈值：
二、线性搜索学习率
1. 初始化
(1) 将学习率置为初始学习率：
(2) 初始化搜索标记：
2. 逐步搜索m步：
计算搜索判断条件：
如果满足搜索判断条件：
将搜索标记置为，并退出搜索
否则：
下降学习率：
三、输出
1. 输出是否找到合适的学习率：
2. 输出找到的学习率：
本节展示BFGS拟牛顿算法的具体代码实现
BFGS算法-代码实现
下面使用BFGS算法来求函数的最小值
由于算法需要使用目标函数的梯度，所以需要先算出梯度，如下：
，
BFGS算法的具体实现代码如下：
"""
BFGS拟牛顿法求y= (x1-2)^2+(x2-3)^2的最小解
本代码来自:www.bbbdata.com 老饼讲解
"""
import numpy as np
# 目标函数
def f(x): # 目标函数
return (x[0,0]-2)**2+(x[1,0]-3)**2 # 返回目标函数值
# 线性搜索函数
def lr_search(f,h,G): # 线性搜索函数
m = 100 # 线性搜索的最大次数
lr_init = 1 # 初始学习率
lr_desc = 0.9 # 学习率衰减系数
gamma = 0.5 # 线性搜索的阈值系数
# 线性搜索
is_find = 0 # 学习率是否有效
lr = lr_init # 初始学习率
for t in range(m): # 逐步搜索
is_find = f(x+lr*h)<= f(x)+gamma*lr*G.T@h # 当前学习率是否有效
if(is_find): # 如果有效
break # 退出搜索
lr = lr * lr_desc # 对学习率误差
return is_find,lr # 返回查找结果
# BFGS主流程
x = np.array([[0],[0]]) # 初始化x
B = np.eye(len(x)) # 初始化二阶矩阵B
G = np.array([[2*x[0,0]-4], [2*x[1,0]-6]]) # 计算梯度G
for i in range(100): # 最大迭代100次
# -----计算迭代量并更新x-----
h = -np.linalg.inv(B)@G # 计算迭代量
[is_find,lr] = lr_search(f,h,G) # 线性搜索学习率
if(is_find==0): # 如果没有搜索到有效的学习率
break # 退出训练
h = lr*h # 更新迭代量
x = x + h # 更新x
# ----------更新B-----------
Gp = G # 备份当前的梯度
G = np.array([[2*x[0,0]-4], [2*x[1,0]-6]]) # 计算当前梯度G
dG = G-Gp # 计算梯度的增量
P = dG@dG.T/(dG.T@h) # 计算P
Q = -B@h@h.T@B/(h.T@B@h) # 计算Q
B = B+P+Q # 更新二阶矩阵B
print("第",i+1,"轮迭代:x=[",x[0,0],",",x[1,0],"],y=",f(x)) # 打印当前结果
if((max(abs(G))< 0.001) ):break # 如果梯度过小，则退出迭代代码运行结果如下：
可以看到，经过2轮迭代后，已经达到目标的最小解[2,3]了~
老饼语
BFGS算法与DFP算法很像，差异在于DFP算法替代的是牛顿法中的，而BFGS则只是替代
由于BFGS替代的是，所以还需要进一步求逆才能得到，这使得BFGS算法的计算要比DFP更加复杂
但是，大家公认的是，在实践中BFGS就是比DFP的效果要更加好，因此更常用的是BFGS，而不是DFP
为什么BFGS比DFP更好呢？
目前这一点在理论上似乎还没有严谨的证明，老饼没有进一步去深究，如果有好的材料，大家可以推荐给老饼
好了，以上就是拟牛顿法BFGS算法的算法流程与具体代码实现了~
End
评论