我正在使用Scipy做一个优化问题,在这里我得到一个顶点为NNxNN
的顶点和键的扁平网络,将其两侧相连(即,使其具有周期性),并使能量函数最小化,从而使其 curl 成形状一个圆柱体。 (请参阅下面的链接。)
由于我具有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
-Dimension参数空间)-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
NN
(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
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显式地计算了该逆黑森州,因此需要更长的时间。像BFGS和L-BFGS之类的准牛顿法基于梯度计算Hessian的近似值(即曲率),这种方法在时间上更便宜,并且据推测也可以更好地估计点的曲率。因此,对于二次函数,Newton-CG收敛速度更快,而对于非二次函数,拟牛顿函数收敛效果更好。 L-BFGS是BFGS的较低内存版本,与完整的NxN矩阵相比,每一步存储的内存要少得多,因此它比BFGS快。
这种解释显示了牛顿-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
最佳答案
您的问题缺少两个重要信息:能量函数和初始猜测。能量函数可以是凸/非凸,平滑/分段平滑/不连续的。因此,很难根据您的情况来完全回答您的问题。但是,我可以解释BFGS和L-BFGS-B之间的一些关键区别。
两种方法都是解决非线性优化问题的迭代方法。它们都通过在每次迭代时使用函数的Hessian近似值来近似Newton方法。牛顿法的主要区别在于,它们没有在特定点上计算完整的Hessian,而是在先前的点上累积了梯度,并使用BFGS公式将它们汇总为Hessian的近似值。除非函数具有接近最佳值的二次泰勒展开,否则不能保证Newton和BFGS方法收敛。
自给定初始猜测以来,原始的BFGS方法会累积所有梯度。这种方法有两个问题。首先,内存可以无限期增加。其次,对于非线性问题,最初猜测时的Hessian通常不能代表解中的Hessian。因此,近似的Hessian将被偏置,直到在解决方案附近累积了足够的梯度为止。这可能会减慢收敛速度,但是以我的经验,应该仍然可以针对具有单个局部最小值的能量函数,使用良好的线搜索算法收敛。
L-BFGS与BFGS相同,但内存有限,这意味着一段时间后,旧的梯度会被丢弃,从而为新计算的梯度留出更多空间。这解决了存储器的问题,并且避免了初始梯度的偏差。但是,根据存储在内存中的渐变数量,可能永远无法精确估计Hessian,这可能是造成偏差的另一个原因。这也会减慢收敛速度,但同样,对于具有单个局部最小值的能量函数,它仍应与良好的线搜索算法收敛。
L-BFGS-B与L-BFGS相同,但对输入变量有一定的约束。 L-BFGS-B将停止优化域边界上的变量。由于您未指定任何约束,因此算法的这一方面不适用于您的问题。
我的假设是,您正在尝试使用距离解决方案较远的初始猜测来解决一个光滑但不凸的问题,并且最终得出的是局部最小值。由于您提到的是从平面配置开始的,所以如果您以奇异的方式开始会导致退化的Hessian,这可能会给其余的优化带来麻烦,我不会感到惊讶。在您的情况下,BFGS和L-BFGS之间的唯一区别是,每次迭代将计算出略有不同的梯度,并且L-BFGS方法最终将遵循导致全局最小值的路径。
关于python - SciPy优化: Newton-CG vs BFGS vs L-BFGS,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/42424444/