5
$\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$
  • 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
5
$\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$
0
$\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$
  • $\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$ – Chris Rackauckas Mar 27 '18 at 20:01

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.