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

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维参数空间）

1. 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
   

2. Newton CG为smallNN（<；=8）找到了正确的最小值，但从NN=9开始，返回了错误的最小值（即一端压扁的圆柱体），对于更高的值，甚至停止收敛。注意：这种行为由于某种原因而加重了奇怪的NN的情况

    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
   

3. 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（即曲率）的近似值，这在时间上是更便宜的，而且也被认为是对一个点的曲率的更好估计。因此，对于二次函数，牛顿CG收敛得更快，而对于非二次函数，拟牛顿函数收敛得更好。L-BFGS是BFGS的一个低内存版本，它在每一步存储的内存都比完整的NxN矩阵少得多，因此它比BFGS快。

这个解释显示了牛顿CG和拟牛顿方法之间的分歧。它不能解释的是算法无法找到真正的最小值，特别是BFGS和L-BFGS之间的差异，这两种算法都应该以相同的方式工作。

我对长收敛时间的普遍直觉是，系统是关于最小值的非二次（即平坦）系统，因此算法随着收敛而振荡。除此之外，如果BFGS和L-BFGS真的以同样的方式工作，我相信Scipy算法的收敛容忍度之间一定存在一些差异。否则，bfg和L-bfg的工作方式并不完全相同，后者可能更准确地计算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

你的问题缺少两个重要信息：能量函数和初始猜测。能量函数可以是凸的/非凸的，光滑的/分段光滑的/不连续的。因此，在你的上下文中很难完全回答你的问题。但是，我可以解释BFGS和L-BFGS-B之间的一些关键区别

这两种方法都是求解非线性优化问题的迭代方法。他们在每次迭代时都用函数的Hessian近似来近似牛顿法。与牛顿法的关键区别在于，它们不是在特定点上计算完整的Hessian，而是在以前的点上累积梯度，并使用BFGS公式将它们组合起来作为Hessian的近似值。牛顿法和BFGS法不能保证收敛，除非函数在最优解附近有二次泰勒展开。

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

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

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

我的假设是，你试图用一个离解很远的初始猜测来解决一个光滑但非凸的问题，最终得到一个局部极小值。既然你提到你是从一个平面配置开始的，我不会惊讶你是从一个奇点开始的，这个奇点会导致一个退化的Hessian，这会给其他优化带来麻烦。在你的例子中，BFGS和L-BFGS的唯一区别是，每次迭代都会计算一个稍微不同的梯度，L-BFGS方法最终会沿着一条通向全局最小值的路径。