6
$\begingroup$

Is there any estimate for the scaling of the number of function calls in BFGS-optimization with the dimensionality of the search space? Specifically I am assuming a (free) expression for the gradient is supplied by the user so that no function calls are made in its evaluation. (Note the gradient is only available for free if the function at that point has already been computed. This is due to an analytical trick.) I am also not interested in any of the scaling of the manipulations that are done in the BFGS algorithm. Again I consider those free compared to the function calls.

Are there theorems guaranteeing something (given some conditions)? Is there experimental data on this for some examples? What would be search terms to look for to find this kind of data? All scaling seems to focus on the computational steps in the optimization algorithm and not on the scaling of the number of function calls. In my case a single function call is orders of magnitude more expensive than any and all other manipulations in a full optimization run added together.


I am looking to find a local minimum, it does not have to be the global minimum. I am interested in continuous functions that are also (twice) differentiable. (At least generically, at worst they might be piece-wise linear at some points. But I am of course also interested in examples in better behaved fully differentiable functions.)

$\endgroup$
7
  • 1
    $\begingroup$ The conditioning of the problem is a critical factor that needs to be taken into account. $\endgroup$ – Brian Borchers Apr 12 at 17:56
  • $\begingroup$ I would say that your question is too general and a complete answer cannot be given without further information regarding your objective function. The examples given in the answer of @Infinity77 are really nice, but keep in mind that Rosenbrock's function becomes more ill conditioned as the dimension increases. As the previous comment says, the conditioning of the problem is critical. Theoretically, if the condition number of the Hessian does not deteriorate when the dimension increases, the number of iterations should not increase too much. Taking a look at the quadratic case might help. $\endgroup$ – Beni Bogosel Apr 14 at 21:06
  • $\begingroup$ @Beni, I disagree a bit. The question is explicitly about whether there is some kind of generic estimate and I think that kind of question is extremely important to have on this stackexchange. For my problem I don't have a specific function in mind but a class of (very complicated and expensive so I cannot give an example) functions. If the answer really is that no prediction of any use can be made than that is a very useful answer as well. Based on the answer by Infinity77 I do not think this is the case. It seems that generically the scaling is not terrible. cont'd ... $\endgroup$ – Kvothe Apr 15 at 7:56
  • $\begingroup$ @Beni, if you have a counter example to this scaling that would be much appreciated as well. I understand that the conditioning number has to do with how much the function changes under a small change. I don't know whether there is an easy or useful answer for this. BFGS should be scale invariant after a sufficient number of steps so what does small even mean exactly, I guess with respect to the space I actually want the BFGS to explore. Anyway I am happy to add more data on the type of functions I have in mind if requested. I saw I did not add any information on continuity so I will add that. $\endgroup$ – Kvothe Apr 15 at 8:00
  • $\begingroup$ @Beni, Also what do you mean about the Rosenbrock's function becoming more ill-conditioned. Does that not give additional evidence in favor of the scaling behaviour being generic. The Rosenbrock function shows linear scaling for a large range of dimensions. You also say it is both well-conditioned (for a low dimensionality) and ill-conditioned (for a large dimensionality). Both show linear scaling so it seems that the ill-conditioning itself is not that much of a problem then. Do you agree? $\endgroup$ – Kvothe Apr 15 at 8:02
10
$\begingroup$

That very much depends on your objective function. If you know that your objective function is highly multi-modal and complex, then BFGS is only going to give you a local minimum. If that is enough for you, then all is good. Otherwise - if you need a global optimum or simply an extremely good local minimum/maximum, then the problem becomes much more intractable as you're looking at using global optimization algorithms. Depending on the size of your problem - in terms of number of variables - it can range from relatively simple to almost impossible to locate a global optimum. On the other hand, convex objective functions shouldn't pose any difficulty on BFGS (or other algorithms) in any dimension.

That said, if we consider the BFGS method against a relatively common test function (the Rosenbrock or "Banana" function), we can take a look at this code:

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()
    
    

This code will produce this picture (at least for me):

enter image description here

Note that I have provided also the gradient of the objective function. This picture will of course vary depending on the function itself. There are also test objective functions in the literature for which the global optimum becomes exponentially more difficult to find as the dimension increases. That said, the curse of dimensionality is almost unavoidable in nonlinear optimization.


EDIT

I have done some more tests, just for fun, with other test functions. I don't have analytical gradients for those but I used the Python package autograd (https://github.com/HIPS/autograd) to get them (and carefully counting which objective evaluations come from L-BFGS-B and which ones from autograd).

Surprise surprise: there is not that much of a pattern:

enter image description here

2D representation of the test functions from my work on Global Optimization:

Rosenbrock http://infinity77.net/go_2021/scipy_test_functions_nd_R.html#go_benchmark.Rosenbrock: Rosenbrock

Wavy

http://infinity77.net/go_2021/scipy_test_functions_nd_W.html#go_benchmark.Wavy: Wavy

Alpine

http://infinity77.net/go_2021/scipy_test_functions_nd_A.html#go_benchmark.Alpine01 Alpine

Brown

http://infinity77.net/go_2021/scipy_test_functions_nd_B.html#go_benchmark.Brown Brown

DixonPrice

http://infinity77.net/go_2021/scipy_test_functions_nd_D.html#go_benchmark.DixonPrice DixonPrice

Griewank

http://infinity77.net/go_2021/scipy_test_functions_nd_G.html#go_benchmark.Griewank Griewank

Enjoy :-)

$\endgroup$
3
  • $\begingroup$ Thank you! This is the kind of thing I was looking for! I understand that it is function dependent but I would like to get a generic idea of an estimate for which I think this is an appropriate test function. (And I am satisfied with finding a local minimum. I will add that to the question.) The fact that this scales linearly is really promising! $\endgroup$ – Kvothe Apr 13 at 12:44
  • $\begingroup$ You're welcome :-) . Please keep in mind that I have only tested this with one objective function (Rosenbrock), so I'd be careful to generalize to all problems and say that BFGS "scales linearly". It may well be the case, but I am not aware of any literature regarding this (but I am sure it exists) and the experimental data I provided is extremely limited... $\endgroup$ – Infinity77 Apr 13 at 13:09
  • $\begingroup$ Thank you for adding more examples. To me there does seem to be a pattern. All examples look like they scale linearly at worst (or at least definitely less than quadratically). It is funny that finding a minimum becomes easier in the Griewank function, but perhaps there are simply more minima so that there is one closer to the initial point. (The functions I am interested in minimizing look more like the Rosenbrock, Brown and DixonPrice functions.) $\endgroup$ – Kvothe Apr 14 at 9:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.