Repeated 1d minimization with similar parameters (scipy)

Question

I have a function f(x,k1,k2) and I am trying to minimize it over x for different values of (k1,k2) on a 2d grid like so

for i,k1 in enumerate(np.logspace(-3.3,-1,20)):
    for j,k2 in enumerate(np.logspace(-3.3,-1,20)):
        if j==0:
            initial_guess = best_x_0
        else:
            initial_guess = best_x
        res = minimize(f,initial_guess,args=(k1,k2),bounds=((0.001,1),),tol=0.01,method='L-BFGS-B')

For given (k1,k2) this is a 1d problem and the function is relatively well behaved with only 1 minimum. However, evaluating it is very costly, ranging from a few seconds to up to about 10 minutes depending on the parameters. Obviously, there must be a more efficient way of solving this than treating it as many independent minimization problems. If the points (k1,k2) are close enough, and if I already have the minimum for one point, the minimum for the points around it should not be very different.

I looked at what Scipy has to offer but I did not find anything ideal for this purpose.

The functions in scipy.optimize.minimize_scalar do not require an initial guess and so I dont know how to take advantage of the 2d grid structure.

I also ran into issues using the 'L-BFGS-B' method of scipy.optimize.minimize. For example, using k1=k2=0.000501187233627 and an initial guess of x=0.02 it converges to x=0.022114610909 in 8 function evaluations. But if I use the same initial guess with k1=k2= np.logspace(-3.3,-1,20)[0] = 0.000501187233627272527534957103, when clearly there should not be any difference it get stuck on about x=0.01999926424 performing useless evaluations such as x=0.019966155,0.01999995105,0.0199951834.

What is the best way to accomplish this?

Answer 1

One approach is to be strategic about setting the initial values and the order in which the grid values of k1 and k2 are evaluated. In particular, you start with the 2x2 grid of lowest and highest values for k1, k2. Then consider, mid-points between the grid values, use averages of x solutions for the neighboring grid points as the initial_guess at a new grid point. You now have 3x3 grid with solutions. Go to midpoints, obtain 5x5 grid, etc. You will of course need to save all of these solutions rather than the best of them.

On the optimization method: since you have a 1d problem, I would try ‘Newton-CG’ with explicitly computed first and second derivatives if possible. This normally speeds up the convergence.

Answer 2

Just a guess, but with a 1d minimization of 2 parameters, the best fit is likely a single global minimum in k1,k2-space shaped like a 2d bowl (depending on the function). If true, that is your only local min. (It may be helpful to look up convex vs concave functions; maxima are negative minima too..) So, guess initial values of the parameters so that you can keep one parameter constant while trying 4 indexed values of the other parameter - one in each cardinal direction. Then vary the next parameter while keeping the former constant in the same way. If the optimization error decreases in any direction, then you know that is the direction of your minima. You can throw this in an iterator with if conditions (if error increases then pass) and let it run; you only care about a subinterval of minimized values, in which the global minima exists. You can even use the change in optimization error per parameter fluctuation to get an idea of a cutoff range. (Though I imagine scipy optimization routines in other answers are more convenient with know how.)