Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It only takes a minute to sign up.
Sign up to join this community
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?
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.
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.
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
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$
– Chris Rackauckas
Mar 27 '18 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!
