ENH: stopping rule for dual_annealing function

[nurfatimaj]

Is your feature request related to a problem? Please describe.

Hi!

I am trying to incorporate dual_annealing into my estimation routine. To learn how to use the function and what to expect of it, I tried to test it on a simple quadratic function.

from scipy.optimize import dual_annealing
import numpy as np

def func(x):
    out = x ** 2
    return out

lb = [-10]
ub = [10]

ret = dual_annealing(func, bounds = list(zip(lb, ub)), maxiter = 10000000)

Since it is a straightforward and simple function with unique minimum at x = 0, I was expecting the optimiser to be finished very quickly. Which it did at first (with default maxiter parameter), but it also returned a message 'Maximum number of iterations reached'. Then, I increased the maxiter as shown above, curious when would it stop. But again, the optimiser ran close to 5,000,000 iterations before reaching the maximum function evaluation threshold.

So, currently, it seems the stopping rule of the optimiser does not depend on "goodness" of the solution, but on number of iterations.

Describe the solution you'd like.

I would have expected the code to stop once the solution got close enough to 0, within some tolerance level that a user can set when calling dual_annealing function. But I did not spot any such parameter in the manual and it doesn't seem to be the behaviour of the optimiser from the above example.

I read the referenced paper, which seems to have been the basis for the dual_annealing function: Xiang Y, Gubian S, Suomela B, Hoeng J. Generalized Simulated Annealing for Efficient Global Optimization: the GenSA Package for R. In the R package they develop, there is a possibility to set tolerance level.

Or if not tolerance level, then some other kind of stopping rule that would also allow the optimiser to exit if it has good confidence about the solution.

Describe alternatives you've considered.

Well, apart from using a different optimiser, the only other alternative I see is to set lower number for maxiter and hope that it is enough to reach a solution. Or run it with different values of maxiter and examine how the solution and function values change between the runs.

But I am not convinced these are good alternatives. It's easy to do with the function in the example. My actual function takes about 30 seconds to run. Doing it 10,000 times already amounts to 83 hours. I don't want to impose an assumption that 10,000 times is enough to reach the true solution. But I also don't want to wait for the solution longer than is necessary.

Additional context (e.g. screenshots, GIFs)

[tupui]

I would have expected the code to stop once the solution got close enough to 0

Hi @nurfatimaj. The issue is that in your case yes the optimal is 0, but in other cases there is no known optimal value so we cannot bound it (be it positive or negative).

Did you try to play with other parameters such as the tolerance?

[nurfatimaj]

Thank you for a reply!

I would like to disagree a little bit. I see the point that perhaps not every optimisation problem can be written in a way that has its minimum at 0. Even then, I would have liked a stopping rule that takes into account how good a solution the algorithm achieved so far. In another global optimisation algorithm, the scipy package has a stopping rule based on how long the algorithm was arriving at a given solution and then deciding that this must be it. I can see that with annealing simply copy-pasting this stopping rule is not a good idea since even after 10,000 iterations it occasionally visits far away points. But my hope is that there exists some kind of stopping rule that can take into account the quality of the solution and that perhaps your team might know of one.

Because consider the current situation. How do I know that the algorithm hits the maxiter or maxfun thresholds close to real solution? It can happen by chance that exactly at the final iteration, the visiting probability took it very far away. I can spot this since my problem has minimum at 0. How do I spot it when I don't know the ideal minimum a priori? Only thing left then will be to rerun the algorithm. Sure, my disliking of having to wait another 83 hours doesn't matter in the grand scheme of things. But is this really what we should expect the result of optimisation to be?

Now, when you say "Did you try to play with other parameters such as the tolerance?", could you please point me to the exact name of the parameter? These are the parameters I see from the documentation:

I'm not very good with python and also new to annealing optimisation, so it could very well be that I just didn't realise that one of them is a tolerance parameter.

Thanks a lot!

[tupui]

As any global optimization, you never know if you found the solution. You can have missed the real solution and got lost around a local minimum.

True, we do miss a parameter to stop the optimizer if there is no more progress (oversight on my side on this point). Here we can just control how "long" we want to look for a solution. The parameters which are provided are only changing the profile temperature and acceptance criteria (basically how far we look around from some solution).

@andyfaff is there a reason we don't have a tolerance option here? I remember some discussions in other issues about something similar.

[nurfatimaj]

The parameters which are provided are only changing the profile temperature and acceptance criteria (basically how far we look around from some solution).

Thanks! That was what I wasn't quite sure about and thought maybe I misunderstood some of them.

I'd be very much interested in learning if there are some reasons why one should not use tolerance. Otherwise, could you hint me in a direction of the simplest workaround?

[dschmitz89]

One stopping rule for dual_annealing could be to compare the points sampled by the annealer from which the local optimizations start. If no better solution was found within n iterations of the outer annealing process, the algorithm could terminate.
CC @sgubianpm ?