# What is the most appropriate derivative free optimization algorithm

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?

• 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)? Commented Mar 20, 2018 at 19:24
• My (hands-on) experience says use NM as your first resort. If it works reliably, job done at low effort. Otherwise, consider alternatives ;) Commented Jun 11 at 15:50

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

• Well I cannot view the paper myself, but I would question the statement "all algorithms that search for an extremum of a cost function perform exactly the same, when averaged over all possible cost functions". Do the authors prove that statement? The reason I ask, is that I recently implemented a "pure random" optimizer that basically "flings numerical faeces at the wall" and keeps track of the best solution. Needless to say, it was (empirically) equally awful at any function that I tried it on! I would be interested to learn what "class" of cost functions it is best suited to ;) Commented Mar 16 at 12:12

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.

• 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? Commented Mar 27, 2018 at 18:51
• 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. Commented Mar 27, 2018 at 20:01

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!