SciPy 优化：Newton-CG vs BFGS vs L-BFGS

Question

我正在使用 Scipy 做一个优化问题，我正在使用一个平面网络的顶点和大小为 NNxNN 的键，连接它的两侧（即，使其成为周期性的），最小化能量函数，使其卷曲形成一个圆柱体。（请参阅下面的链接。）

因为我有函数energy(xyz-position)而且它是渐变的，所以我决定使用Scipy手册中推荐的三种方法——Newton-CG、BFGS、L-BFGS-B -- 比较他们的表现。

我调用优化函数如下，只是根据大小写将'Newton-CG'替换为'BFGS'和'L-BFGS-B'：

from scipy.optimize import minimize
res = minimize(energy, xyzInit, method='Newton-CG', jac = energy_der,  options={'disp': True})

我发现了以下一般行为（我给出了 NN=9 情况下的输出数据，对应于 3*9^2=243 维参数 space）-

BFGS 系统地未能找到正确的最小值（对于低 NN），并且对于大 NN 根本无法收敛。最终结果见 https://plot.ly/~apal90/162/。

 NN=9
 Method: BFGS
 Warning: Desired error not necessarily achieved due to precision loss.
 Current function value: 204.465912
 Iterations: 1239
 Function evaluations: 1520
 Gradient evaluations: 1508
 Time taken for minimisation: 340.728140116

Newton-CG 找到了小 NN (<=8) 的正确最小值，但从 NN=9 开始，返回了一个不正确的最小值（即，一个圆柱体被压扁了一个结束），并且对于更高的值甚至停止收敛。注意：由于某些原因，这种行为会因奇数 NN 而加剧。参见 https://plot.ly/~apal90/164/
```
 NN=9
 Method: Newton-CG
 Optimization terminated successfully.
 Current function value: 7.954412
 Iterations: 49
 Function evaluations: 58
 Gradient evaluations: 1654
 Hessian evaluations: 0
 Time taken for minimisation: 294.203114033
```
L-BFGS-B 找到了正确的最小值，而且速度太快了，对于我测试的所有 NN（最多 NN=14）。参见 https://plot.ly/~apal90/160/
```
 NN=9
 Method: L-BFGS-B
 Time taken for minimisation: 36.3749790192
```

问题：为什么L-BFGS-B在这种情况下优于其他两种方法？特别是，为什么它比 BFGS 好得多，因为两者都应该是准牛顿方法，以完全相同的方式工作（据我所知）。

我对这种情况的看法：所有三种方法都在每个点 x 处进行二次逼近。为此，它需要一个梯度和一个 Hessian 矩阵。如果没有给出Hessian，则必须通过算法计算。在我们的例子中，只有梯度是明确给出的，这是在每一步都由算法计算出来的。更具体地说，我们需要的是 Hessian 矩阵的逆矩阵，这是一个非常昂贵的步骤，尤其是在更高维度上。现在，Newton-CG 明确地计算了这个逆 Hessian，因此需要更长的时间。像 BFGS 和 L-BFGS 这样的拟牛顿方法基于梯度计算 Hessian 矩阵的近似值（即曲率），这在时间上更便宜，而且据推测这也是对点曲率的更好估计。因此，对于二次函数，Newton-CG 收敛得更快，而对于非二次函数，拟牛顿函数收敛得更好。 L-BFGS 是 BFGS 的低内存版本，它在每一步存储的内存都比完整的 NxN 矩阵少得多，因此它比 BFGS 更快。

这个解释显示了 Newton-CG 和拟牛顿方法之间的分歧。它没有解释的是算法无法找到真正的最小值，尤其是 BFGS 和 L-BFGS 之间的差异，它们都应该以相同的方式运行。

我对长收敛时间的一般预感是系统关于最小值是非二次的（即平坦的），因此算法随着收敛而振荡。除此之外，如果 BFGS 和 L-BFGS 真的以相同的方式工作，我相信 Scipy 算法的收敛容差水平之间一定存在一些差异。否则，BFGS 和 L-BFGS 的工作方式并不相同，后者计算 Hessian 矩阵的准确性可能要高得多。

参考文献--

http://www.scipy-lectures.org/advanced/mathematical_optimization/#newton-and-quasi-newton-methods

https://en.wikipedia.org/wiki/Newton%27s_method_in_optimization

https://en.wikipedia.org/wiki/Quasi-Newton_method

https://docs.scipy.org/doc/scipy-0.18.1/reference/optimize.minimize-bfgs.html#optimize-minimize-bfgs

https://docs.scipy.org/doc/scipy-0.18.1/reference/optimize.minimize-lbfgsb.html#optimize-minimize-lbfgsb

Answer 1

您的问题缺少两个重要信息：能量函数和初始猜测。能量函数可以是convex/non-convex、smooth/piecewise-smooth/discontinuous。因此，很难在您的上下文中完全回答您的问题。但是，我可以解释 BFGS 和 L-BFGS-B 之间的一些主要区别。

这两种方法都是求解非线性优化问题的迭代方法。它们都通过在每次迭代中使用函数的 Hessian 近似值来近似牛顿法。与牛顿法的主要区别在于，它们不是计算特定点的完整 Hessian，而是累积先前点的梯度，并使用 BFGS 公式将它们放在一起作为 Hessian 的近似值。 Newton 和 BFGS 方法不能保证收敛，除非函数具有接近最优的二次泰勒展开。

原始的 BFGS 方法累积了自给定初始猜测以来的所有梯度。这种方法有两个问题。首先，内存可以无限增加。其次，对于非线性问题，初始猜测中的 Hessian 矩阵通常不能代表解中的 Hessian 矩阵。因此，近似的 Hessian 矩阵将有偏差，直到在解附近积累了足够的梯度。这会减慢收敛速度，但根据我的经验，对于具有单个局部最小值的能量函数，仍应使用良好的线搜索算法收敛。

L-BFGS 与 BFGS 相同，但内存有限，这意味着一段时间后，旧的梯度将被丢弃，为新计算的梯度留下更多 space。这解决了内存问题，并且避免了初始梯度的偏差。然而，根据内存中保存的梯度数量，Hessian 矩阵可能永远无法精确估计，并且可能成为偏差的另一个来源。这也会减慢收敛速度，但同样，对于具有单个局部最小值的能量函数，它仍应使用良好的线搜索算法收敛。

L-BFGS-B 与 L-BFGS 相同，但对输入变量有约束。 L-BFGS-B 将停止优化域边界上的变量。由于您没有指定任何约束，算法的这一方面不适用于您的问题。

我的假设是，您正在尝试使用与解决方案相差甚远的初始猜测来解决一个平滑但非凸的问题，并且您最终会遇到局部最小值。既然你提到你从一个平面配置开始，我不会感到惊讶你从一个导致退化的 Hessian 的奇点开始，这可能会给优化的其余部分带来麻烦。在您的情况下，BFGS 和 L-BFGS 之间的唯一区别是每次迭代都会计算出略有不同的梯度，并且 L-BFGS 方法最终将遵循通向全局最小值的路径。

SciPy 优化：Newton-CG vs BFGS vs L-BFGS

SciPy optimisation: Newton-CG vs BFGS vs L-BFGS

python

optimization

scipy

newtons-method