8
$\begingroup$

We can use random optimization/ derivative free/ direct search to find the minimum of some black box function $f$.

If I have some 2D black box function, $f(x,y)$ - which I know to be convex - what is the best derivative-free method to use?

i.e. from a speed perspective is it best to use e.g. Nelder-Mead, Compass/Pattern search, MADS etc?

$\endgroup$
1
  • 6
    $\begingroup$ It would be helpful if you could define "appropriate". I assume you are looking for the highest-performance solution? How expensive is it to compute $f(x,y)$, say, relative to $exp(x)$? Is the computing platform highly parallel (e.g. a GPU)? $\endgroup$
    – njuffa
    Mar 20 '18 at 19:24
8
$\begingroup$

As the "No Free Lunch Theorems for Search" [1] states that there is no one particular optimization algorithm that works best for every problem, i.e., citing the authors:

all algorithms that search for an extremum of a cost function perform exactly the same, when averaged over all possible cost functions. In particular, if algorithm A outperforms algorithm B on some cost functions, then loosely speaking there must exist exactly as many other functions where B outperforms A.

However, for a really good guidance, I would suggest to look at the recent article [2] (written by two well-known optimizers), which presents a review and comparison of 22 derivative-free algorithms performed on a test set consisting of 502 convex/nonconvex, smooth/nonsmooth optimization problems.

References

1: Wolpert, D. H., & Macready, W. G. (1995). No free lunch theorems for search (Vol. 10). Technical Report SFI-TR-95-02-010, Santa Fe Institute.

2: Rios, L. M., & Sahinidis, N. V. (2013). Derivative-free optimization: a review of algorithms and comparison of software implementations. Journal of Global Optimization, 56(3), 1247-1293.

$\endgroup$
2
$\begingroup$

As @Remis says, it's very problem-dependent. I think the best thing to do is use a nice package with a suite of methods and just test them all. NLopt.jl makes it easy to try quite a large number of algorithms (including a lot of derivative-free methods). The one that's best for your problem is the one that performs best.

$\endgroup$
2
  • $\begingroup$ I got a glimpse of what Julia has to offer for numerical ODEs (thanks to some of your previous posts), and I must say I'm positively impressed. does Julia offer other functionality similar to that of Python's numpy/scipy? if so, could you point me to some good reference material that can get me started with the language? $\endgroup$
    – GoHokies
    Mar 27 '18 at 18:51
  • $\begingroup$ Python's numpy equivalent is just Julia's base library. See how it's all covered in the manual. For what SciPy offers, Julia offers the same stuff but through a confederation of packages (much like R). A good source to search through packages is JuliaObserver, for example you can find Optim.jl and JuMP near the top for optimization. The language is still relatively new (with 1.0 coming this summer) but has a lot of unique packages already. $\endgroup$ Mar 27 '18 at 20:01
2
$\begingroup$

I faced a similar question, and in general it is tough in Python world because choosing a derivative-free optimizer requires one to compare scipy.optimize, dlib, ax-platform, hyperopt, nevergrad, optuna, bayesopt, platypus, pymoo, pySOT and skopt (and more by the time you read this) and there is barely a convention in common.

I finally decided I would just do it once and for all. So now I compute Elo ratings for 60+ derivative free optimizers, as explained in a blog article HumpDay: A Package to Help You Choose a Python Global Optimizer. You can also put your objective function directly into a colab notebook and it will show you which package does the best job.

I won't presume to know which will work in your case, but don't overlook the following: dlib, pySOT (dycors); skopt; nevergrad (ngopt8); shgo. Ping me if you'd like to add your objective function to the test suite. I do have a sneaking suspicion that an Algorithm from the 1960s is going to work just fine in your case.

btw if you go with Julia instead, more power to you!

$\endgroup$

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.