Broyden、Fletcher、Goldfarb 和 Shanno 算法，或称为 **BFGS 算法**，是一种局部搜索优化算法。
它是一种二阶优化算法，意味着它利用目标函数的二阶导数，并属于一类称为拟牛顿法的算法，这些算法在无法计算二阶导数的情况下，会近似二阶导数（称为 Hessian）。
BFGS 算法可能是最广泛使用的二阶数值优化算法之一，并且通常用于拟合机器学习算法，例如逻辑回归算法。
在本教程中，您将了解 BFGS 二阶优化算法。
完成本教程后，您将了解：
- 二阶优化算法是利用二阶导数的算法，对于多元目标函数，这被称为 Hessian 矩阵。
- BFGS 算法可能是数值优化中最流行的二阶算法，属于一类称为拟牛顿法。
- 如何使用 Python 中的 BFGS 和 L-BFGS-B 算法最小化目标函数。
开始您的项目，阅读我的新书《机器学习优化》，其中包含分步教程和所有示例的Python源代码文件。
让我们开始吧。
BFGS 优化算法入门指南
照片作者：Timo Newton-Syms，部分权利保留。
教程概述
本教程分为三个部分；它们是：
- 二阶优化算法
- BFGS 优化算法
- BFGS 的工作示例
二阶优化算法
优化涉及找到输入参数的值，以最大化或最小化目标函数。
牛顿法优化算法是利用目标函数二阶导数的算法。
您可能还记得，微积分中的函数一阶导数是函数在特定点的变化率或曲率。优化算法可以通过沿着导数（向下或向上）来找到函数的最小值（产生目标函数最小输出值的输入值）。
利用一阶导数的算法称为一阶优化算法。梯度下降优化算法就是一个例子。
- 一阶方法：利用一阶导数来寻找目标函数最优值的优化算法。
二阶导数是一阶导数的导数，即变化率的变化率。
二阶导数可以用来更有效地定位目标函数的最小值。从更普遍的角度来看，这似乎是合理的，因为我们拥有的关于目标函数的信息越多，优化它就越容易。
二阶导数不仅告诉我们应该向哪个方向移动（与一阶方法类似），还能估计在该方向上移动的距离，即步长。
另一方面，二阶信息允许我们对目标函数进行二次近似，并近似正确的步长以达到局部最小值……
— 第 87 页，Algorithms for Optimization，2019。
利用二阶导数的算法被称为二阶优化算法。
- 二阶方法：利用二阶导数来寻找目标函数最优值的优化算法。
牛顿法是一种二阶优化算法的例子。
当目标函数有多个输入变量时，可以将这些输入变量视为一个向量，这可能在线性代数中见过。
梯度是导数向多元函数的推广。它捕捉函数局部的斜率，使我们能够预测在任何方向上从一个点迈出一小步的影响。
— 第 21 页，Algorithms for Optimization，2019。
类似地，多个输入变量的一阶导数也可以是一个向量，其中每个元素称为偏导数。这个偏导数向量被称为梯度。
- 梯度：目标函数多个输入变量的偏一阶导数向量。
这个思想推广到多元输入的二阶导数，这是一个包含二阶导数的矩阵，称为 Hessian 矩阵。
- Hessian：目标函数多个输入变量的偏二阶导数矩阵。
如果二阶导数在计算导数的点上都是连续的，那么 Hessian 矩阵就是对称的方阵。在解决实值优化问题时，这通常是情况，也是使用许多二阶方法时的期望。
多元函数的 Hessian 是一个包含所有相对于输入的二阶导数的矩阵。二阶导数包含了关于函数局部曲率的信息。
— 第 21 页，Algorithms for Optimization，2019。
因此，通常将利用 Hessian 或沿着 Hessian 找到目标函数最小值（或最大值）的二阶优化算法进行描述。
现在我们对二阶优化算法有了高层次的理解，让我们更仔细地看看 BFGS 算法。
想要开始学习优化算法吗？
立即参加我为期7天的免费电子邮件速成课程（附示例代码）。
点击注册，同时获得该课程的免费PDF电子书版本。
BFGS 优化算法
BFGS 是一种二阶优化算法。
它是一个缩写，以算法的四位共同发现者命名：Broyden、Fletcher、Goldfarb 和 Shanno。
它是一种局部搜索算法，用于具有单一最小值的凸优化问题。
BFGS 算法可以最好地理解为属于一类称为拟牛顿方法的算法，这些算法是牛顿法优化算法的扩展。
牛顿法是一种利用 Hessian 矩阵的二阶优化算法。
牛顿法的一个限制是它需要计算 Hessian 矩阵的逆。这是一个计算成本很高的操作，并且可能不稳定，具体取决于目标函数的属性。
拟牛顿法是二阶优化算法，它利用梯度近似 Hessian 矩阵的逆，这意味着对于算法的每一步，Hessian 及其逆不必可用或精确计算。
拟牛顿法是用于非线性优化的最广泛使用的方法之一。它们被包含在许多软件库中，并且在解决各种小型到中型问题方面非常有效，特别是在 Hessian 难以计算时。
— 第 411 页，Linear and Nonlinear Optimization，2009。
不同的拟牛顿优化算法之间的主要区别在于计算逆 Hessian 近似的具体方式。
BFGS 算法是一种更新逆 Hessian 计算的特定方法，而不是在每次迭代时重新计算它。它或其扩展可能是最流行的拟牛顿或二阶数值优化算法之一。
最流行的拟牛顿算法是 BFGS 方法，以其发现者 Broyden、Fletcher、Goldfarb 和 Shanno 命名。
— 第 136 页，Numerical Optimization，2006。
当 Hessian 可用时，使用它的一个好处是，它可以用于确定移动的方向和步长，以更改输入参数来最小化（或最大化）目标函数。
像 BFGS 这样的拟牛顿法会近似逆 Hessian，然后可以使用它来确定移动的方向，但我们不再有步长。
BFGS 算法通过使用沿选定方向的线搜索来确定在该方向上移动的距离来解决此问题。
有关 BFGS 算法的推导和计算，我推荐本教程末尾的扩展阅读部分中的资源。
Hessian 及其逆的大小与目标函数的输入参数数量成正比。因此，对于数百万参数，矩阵的大小可能会变得非常大。
… BFGS 算法必须存储逆 Hessian 矩阵 M，这需要 O(n²) 内存，这使得 BFGS 对于大多数现代深度学习模型（通常有数百万个参数）来说都不切实际。
— 第 317 页，Deep Learning，2016。
有限内存 BFGS（或 L-BFGS）是 BFGS 算法的扩展，它解决了参数数量较多时的成本问题。它通过不要求存储整个逆矩阵的近似值来做到这一点，而是假设算法上一次迭代的逆 Hessian 的简化（用于近似）。
现在我们已经从高层次上熟悉了 BFGS 算法，让我们看看如何使用它。
BFGS 的工作示例
在本节中，我们将看一些使用 BFGS 优化算法的示例。
我们可以使用 SciPy 的 minimize() 函数在 Python 中实现 BFGS 算法来优化任意函数。
该函数接受多个参数，但最重要的是，我们可以将目标函数名称指定为第一个参数，将搜索的起始点指定为第二个参数，并将“method”参数指定为‘BFGS’。“jac”参数用于指定计算目标函数导数的函数名称。
|
1 2 3 |
... # 执行 bfgs 算法搜索 result = minimize(objective, pt, method='BFGS', jac=derivative) |
我们来看一个例子。
首先，我们可以定义一个简单的二维目标函数，一个碗状函数，例如 x²。它只是输入变量的平方和，其最小值为 f(0, 0) = 0.0。
|
1 2 3 |
# 目标函数 def objective(x): return x[0]**2.0 + x[1]**2.0 |
接下来，让我们定义目标函数的导数函数，即 [x*2, y*2]。
|
1 2 3 |
# 目标函数的导数 def derivative(x): return [x[0] * 2, x[1] * 2] |
我们将函数边界定义为每个维度范围为 -5 到 5 的盒子。
|
1 2 3 |
... # 定义输入范围 r_min, r_max = -5.0, 5.0 |
搜索的起始点将是搜索域中随机生成的位置。
|
1 2 3 |
... # 将起始点定义为从域中随机采样 pt = r_min + rand(2) * (r_max - r_min) |
然后，通过指定目标函数名称、初始点、要使用的算法（BFGS）和导数函数名称，将 BFGS 算法应用于寻找目标函数的最小值。
|
1 2 3 |
... # 执行 bfgs 算法搜索 result = minimize(objective, pt, method='BFGS', jac=derivative) |
然后，我们可以查看结果，报告算法是否成功完成的消息以及执行的目标函数评估的总数。
|
1 2 3 4 |
... # 总结结果 print('Status : %s' % result['message']) print('Total Evaluations: %d' % result['nfev']) |
最后，我们可以报告找到的输入变量及其在目标函数上的评估值。
|
1 2 3 4 5 |
... # 评估解 solution = result['x'] evaluation = objective(solution) print('Solution: f(%s) = %.5f' % (solution, evaluation)) |
将这些结合起来，完整的示例列在下面。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
# bfgs 算法凸函数局部优化 from scipy.optimize import minimize from numpy.random import rand # 目标函数 def objective(x): return x[0]**2.0 + x[1]**2.0 # 目标函数的导数 def derivative(x): return [x[0] * 2, x[1] * 2] # 定义输入范围 r_min, r_max = -5.0, 5.0 # 将起始点定义为从域中随机采样 pt = r_min + rand(2) * (r_max - r_min) # 执行 bfgs 算法搜索 result = minimize(objective, pt, method='BFGS', jac=derivative) # 总结结果 print('Status : %s' % result['message']) print('Total Evaluations: %d' % result['nfev']) # 评估解 solution = result['x'] evaluation = objective(solution) print('Solution: f(%s) = %.5f' % (solution, evaluation)) |
运行示例，将 BFGS 算法应用于我们的目标函数并报告结果。
注意：由于算法或评估过程的随机性，或数值精度差异，您的结果可能有所不同。考虑运行几次示例并比较平均结果。
在这种情况下，我们可以看到算法执行了四次迭代，并且发现了一个非常接近最小值 f(0.0, 0.0) = 0.0 的解，至少在有用的精度范围内。
|
1 2 3 |
状态：优化成功终止。 总评估次数：4 解：f([0.00000000e+00 1.11022302e-16]) = 0.00000 |
minimize() 函数还支持 L-BFGS 算法，该算法的内存需求比 BFGS 低。
具体来说，L-BFGS-B 版本算法中的“-B”后缀表示“带边界”版本，其中可以指定域的边界。
可以通过将“method”参数指定为“L-BFGS-B”来实现。
|
1 2 3 |
... # 执行 l-bfgs-b 算法搜索 result = minimize(objective, pt, method='L-BFGS-B', jac=derivative) |
更新后的完整示例如下。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
# l-bfgs-b 算法凸函数局部优化 from scipy.optimize import minimize from numpy.random import rand # 目标函数 def objective(x): return x[0]**2.0 + x[1]**2.0 # 目标函数的导数 def derivative(x): return [x[0] * 2, x[1] * 2] # 定义输入范围 r_min, r_max = -5.0, 5.0 # 将起始点定义为从域中随机采样 pt = r_min + rand(2) * (r_max - r_min) # 执行 l-bfgs-b 算法搜索 result = minimize(objective, pt, method='L-BFGS-B', jac=derivative) # 总结结果 print('Status : %s' % result['message']) print('Total Evaluations: %d' % result['nfev']) # 评估解 solution = result['x'] evaluation = objective(solution) print('Solution: f(%s) = %.5f' % (solution, evaluation)) |
运行示例应用程序，将 L-BFGS-B 算法应用于我们的目标函数并报告结果。
注意：由于算法或评估过程的随机性，或数值精度差异，您的结果可能有所不同。考虑运行几次示例并比较平均结果。
同样，我们可以看到函数的最优点在很少的评估次数中就被找到了。
|
1 2 3 |
Status : b'CONVERGENCE: NORM_OF_PROJECTED_GRADIENT_<=_PGTOL' 总评估次数：3 解：f([-1.33226763e-15 1.33226763e-15]) = 0.00000 |
将测试问题的维度增加到数百万个参数，并比较这两种算法的内存使用和运行时间，可能是一项有趣的练习。
进一步阅读
如果您想深入了解，本节提供了更多关于该主题的资源。
书籍
API
文章
总结
在本教程中，您了解了 BFGS 二阶优化算法。
具体来说，你学到了：
- 二阶优化算法是利用二阶导数的算法，对于多元目标函数，这被称为 Hessian 矩阵。
- BFGS 算法可能是数值优化中最流行的二阶算法，属于一类称为拟牛顿法。
- 如何使用 Python 中的 BFGS 和 L-BFGS-B 算法最小化目标函数。
你有什么问题吗？
在下面的评论中提出你的问题，我会尽力回答。
先生，我很高兴阅读它。
谢谢！
先生，我很高兴阅读它。这对我的学习非常有帮助。
很高兴听到这个消息。
BFGS 算法是否适用于任何成本函数？
我发现 Levenberg-Marquardt 算法仅推荐用于二次损失函数，并且发现它不适用于交叉熵。
BFGS 是否也有类似的情况？
不，并非如此。如果您不确定，可以尝试一下并与其他方法进行比较。
Jason，
这可能是 Scipy curve_fit 的一个有趣替代方案，但复杂函数的问题在于生成导数。使用观测数据与计算数据之间的差异作为近似是否足够？
此致，
Harald Flesche
我认为它不适用于近似导数。我相信它需要真实的导数。
非常感谢这篇文章，一个小小的评论是代码出现了以下错误而崩溃
TypeError: unsupported operand type(s) for -: ‘list’ and ‘list’
我通过使用 np.array() 修复了它
# bfgs 算法凸函数局部优化
from scipy.optimize import minimize
from numpy.random import rand
import numpy as np
# 目标函数
def objective(x)
return x[0]**2.0 + x[1]**2.0
# 目标函数的导数
def derivative(x)
return np.array([x[0] * 2, x[1] * 2])
# 定义输入范围
r_min, r_max = -5.0, 5.0
# 将起始点定义为从域中随机采样
pt = np.array(r_min + rand(2) * (r_max – r_min))
# 执行 bfgs 算法搜索
result = minimize(objective, pt, method=’BFGS’, jac=derivative)
# 总结结果
print(‘Status : %s’ % result[‘message’])
print(‘Total Evaluations: %d’ % result[‘nfev’])
# 评估解
solution = result[‘x’]
evaluation = objective(solution)
print(‘Solution: f(%s) = %.5f’ % (solution, evaluation))
感谢您的评论，但我没有在原始代码中看到任何使用 Python 列表的地方。
感谢这篇文章。我正在处理一个分布，需要使用 BFGS 算法优化其负对数似然来估计参数（总共有三个参数）。近似 Hessian 矩阵是奇异的，因此返回的参数估计值并不可靠，因为估计值的偏差和均方误差非常大。
我该如何解决这个问题？
虽然一些矩阵技巧可能适用，但通常如果您找不到 Hessian，那意味着它不是优化方法的正确选择。我们有如此多不同的优化算法的原因是，每种算法都有其局限性。没有一种方法可以解决所有问题。
感谢您的见解。
我很想请您帮助我了解解决这类问题的算法（至少列出它们）。谢谢。
不客气。
谢谢您的分享，非常有启发性。
非常欢迎您，Olalekan！我们非常感谢您的支持！