计算科学 - BFGS 中函数调用的数量如何随空间的维度而变化？ - 吾爱随笔录

BFGS 中函数调用的数量如何随空间的维度而变化？

计算科学优化复杂

2021-12-11 13:47:55

问题

对于 BFGS 优化中函数调用次数与搜索空间维度的缩放，是否有任何估计？具体来说，我假设用户提供了梯度的（自由）表达式，以便在其评估中不进行任何函数调用。

请注意，仅当该点处的函数已被计算时，梯度才可免费使用。这是由于一个分析技巧。我也对 BFGS 算法中进行的任何操作的缩放不感兴趣。与函数调用相比，我再次考虑那些免费的。

是否有定理在某些条件下保证一定的空间复杂度？是否有一些例子的实验数据？要查找此类数据需要哪些搜索词？

所有缩放似乎都关注优化算法中的计算步骤，而不是函数调用数量的缩放。在我的情况下，单个函数调用比完整优化运行中的任何和所有其他操作加在一起要贵几个数量级。

细节

我正在寻找一个局部最小值，它不必是全局最小值。我对也是（两次）可微的连续函数感兴趣。（至少一般来说，在最坏的情况下，它们在某些点上可能是分段线性的。但我当然也对表现更好的完全可微函数的示例感兴趣。）

1个回答

这在很大程度上取决于您的目标函数。如果你知道你的目标函数是高度多模态和复杂的，那么 BFGS 只会给你一个局部最小值。如果这对你来说足够了，那么一切都很好。否则 - 如果您需要一个全局最优值或只是一个非常好的局部最小值/最大值，那么当您使用全局优化算法时，问题会变得更加棘手。根据您的问题的大小 - 就变量的数量而言 - 它可以从相对简单到几乎不可能找到全局最优值。另一方面，凸目标函数不应该在任何维度上对 BFGS（或其他算法）造成任何困难。

也就是说，如果我们针对一个相对常见的测试函数（Rosenbrock 或“Banana”函数）考虑 BFGS 方法，我们可以看一下这段代码：

import numpy as np
import scipy.optimize as optimize
import matplotlib.pyplot as plt

def rosen(x):
    global fun_calls
    fun_calls += 1
    return np.sum(100.0*(x[1:] - x[:-1]**2.0)**2.0 + (1 - x[:-1])**2.0)
    
    
def rosen_gradient(x):
    xm = x[1:-1]
    xm_m1 = x[:-2]
    xm_p1 = x[2:]
    der = np.zeros_like(x)
    der[1:-1] = 200*(xm-xm_m1**2) - 400*(xm_p1 - xm**2)*xm - 2*(1-xm)
    der[0] = -400*x[0]*(x[1]-x[0]**2) - 2*(1-x[0])
    der[-1] = 200*(x[-1]-x[-2]**2)
    return der
    
    
def main():

    global fun_calls
    nvars = np.arange(2, 101)
    nfuns = []
    
    for n in nvars:
    
        x0 = -3.14159265*np.ones((n, ))
        lb = -5.0*np.ones_like(x0)
        ub = 10.0*np.ones_like(x0)
        bounds = zip(lb, ub)
        fun_calls = 0
        out = optimize.fmin_l_bfgs_b(rosen, x0, fprime=rosen_gradient, maxfun=10000)
        nfuns.append(fun_calls)

    m, q = np.polyfit(nvars, nfuns, 1)
    fig = plt.figure()
    ax = fig.add_subplot(111)
    ax.plot(nvars, nfuns, 'b.', ms=13, zorder=1, label='Function Calls')
    ax.plot(nvars, nvars*m+q, 'r-', lw=2, zorder=2, label=r'Fit: $y = %0.2f\cdot x + %0.2f$'%(m, q))
    ax.legend(loc=0, fancybox=True, shadow=True, fontsize=16)
    
    ax.grid()
    ax.set_xlabel('Problem Dimension', fontsize=16, fontweight='bold')
    ax.set_ylabel('Function Calls', fontsize=16, fontweight='bold')
    ax.set_title('Rosenbrock Function', fontsize=18, fontweight='bold')
    plt.show()
    
        
if __name__ == '__main__':
    main()

此代码将生成此图片（至少对我而言）：