In general metaheuristic algorithms, such as Genetic Algorithm, are among the best derivative-free optimization methods. But if you take into account that the objective function is unimodal, other methods such as Nelder-Mead or Quadratic Fit could be better.

Although I'm not an expert in this field I would suggest you to read this thread [1] where you will find not only useful information on how to solve your problems (Python implementation often linked directly in the emails) but also the literature about benchmarks results obtained on similar problems with the most common approaches. It should definitely help you to reduce the number of alternatives ....

HTH

[1] http://mail.scipy.org/pipermail/scipy-dev/2014-March/019640.html

In general metaheuristic algorithms, such as Genetic Algorithm, are among the best derivative-free optimization methods. But if you take into account that the objective function is unimodal, other methods such as Nelder-Mead or Quadratic Fit could be better.

I am afraid that lack of smoothness is a big problem, even if the function is unimodal. However, I think that global optimisation algorithms such as DIRECT or UCT should actually work in this scenario, with some modifications to take advantage of the unimodality.

As you probably know there is no free lunch. However, I would suggest using an algorithm from the family of Covariance Matrix Adaptation Evolution Strategies (CMA-ES), which were shown to perform very well in various benchmarks. You can find some source code here: https://www.lri.fr/~hansen/cmaes_inmatlab.html

Also, here (http://coco.gforge.inria.fr/doku.php) you can find the results of the Black-Box Optimization Benchmarking Workshops (2009-2013).

There have been extensive tests by Rios and Sahinidis (http://archimedes.cheme.cmu.edu/?q=dfocomp), and by N. Hansen (https://www.lri.fr/~hansen/cec2005.html and newer), and the BBOB comparisons (http://coco.gforge.inria.fr/doku.php)

However, the question about "the best derivative-free algorithm..." is like asking what the best mathematical theorem is. In optimization it is extremely important to know the structure of your problem before choosing your algorithm. Otherwise, you will not get good solutions. Do you have a formula for your function, does it come from a simulation, does it have a special structure, is it possible to get (sub)gradients, e.g. via automatic differentiation?

Hi Hermann,

I’m looking for effective algorithms on unimodal problem with the purpose to use them as local search methods in a hybrid algorithm for multi-modal optimization. The general idea is to use Minimum Population Search for finding the most promising attraction basins and then converge towards the local optima using a “good” unimodal optimizer. Since multimodal problems can be so diverse it is hard to predict the structure of the unimodal sub-problem (i.e. converging to the attraction basin’s optimum). For example, in molecular docking, the size and shapes of the attraction basins strongly varies if the ligand docks inside a cavity or on the surface of the molecule.

For now I’m just looking for different algorithms to empirically test them on different unimodal functions. Since the idea is to use them as local search hybrids, we can suppose that the initial point is “near” the local optima. Since the global search method will consume some computational resources, the ability to converge “fast” (with few function evaluations) will also be very important. Let’s assume for now that automatic differentiation is not possible…

You can find several metheuristics such as genetic algortihms (the most well known), simulated annealing but also ant colony optimization, swarm optimization algorithm... I've heard also about an optimisation algorithm based on gravitation equations. A classification is given here : see the link below.

For Matlab, just google the name of the algorithm you want followed by matlab and you'll easily find tons of matlab files. The same holds for C or python I guess. An example : Particle Swarm Optimization Using C# (http://visualstudiomagazine.com/articles/2013/11/01/particle-swarm-optimization.aspx): this site provides a download link for the code.

Good luck !

I've recently heard about DCA (Difference of Convex functions Algorithm) which provides a very powerful tool for nonconvex global oprimization, under constraints if needed. You can find information here (http://www.sciencedirect.com/science/article/pii/S0167637796000363) or on the website of Le Thi Hoai An (http://lita.sciences.univ-metz.fr/~lethi/index.php/dca.html) ans lts of publications.

http://en.wikipedia.org/wiki/Metaheuristic#mediaviewer/File:Metaheuristics_classification.svg

Hi Antonio!

For your problem characteristics I would go with MCS, LGO, TOMLAB/GLCCLUSTER, and TOMLAB/MULTIMIN. Those should be best for a small number of function values. I would recommend evolutionary algorithms only if you can spend a somewhat higher number of function evaluations.

Hello Antonio,

Just to add to my previous comment. From what I understand, CMA-ES are quite efficient in their use of function evaluations and they are best suited for *continuous optimization* problems (so bear that in mind). I've used an algorithm called (1+1)-Cholesky-CMA-ES (http://link.springer.com/article/10.1007%2Fs10994-009-5102-1) in the past as the local search method of a memetic algorithm, where the problem is multimodal (optimization of recurrent neural networks), and local search helped a lot.

Another thing you might want to consider is the dimensionality of the problem. I've seen methods that scale well for high dimensions and others that don't. Also, you could use surrogate models to assist with the search if function evaluations are very expensive. See the publication list of Ilya Loshchilov for surrogate models and some work regarding high dimensions: https://www.researchgate.net/profile/Ilya_Loshchilov/contributions. Regarding high dimensions, "cooperative coevolution" has also shown very promising results: http://www.sciencedirect.com/science/article/pii/S002002550800073X.

I would be very interested to see the results of your experiments.

When your function is unimodal , a lot of optimization methods should work but in case you want to use an algorithm with powerful "exploitation" abilities you could use

PSO, GA, Hill Climming(simple and could be effective in unimodal case) ,Nelder-Mead method ,...

Nelder-Mead only works well in 2D. There it is the absolutely best DFO algorithm. In higher dimensions it loses its effectivity quite fast.

Hill Climbing in higher dimension needs very clever direction sampling to work. (This is due to the fact that the geometry of high dimensional spaces differs significantly from low dimensional spaces. You need to sample uniformly distributed on an n-sphere, what you should _not_ implement in R^n for high n by uniform distribution on a cube and normalizing the result vector!) Otherwise, it needs a very high number of function evaluations to find a good direction of ascent (or descent).

Usually, for a small number of function evaluations, methods that build a local model of the function tend to work better. BTW: That makes CMA-ES such a good evolutionary algorithm since it does not evolve points but local models of the function. However, this usually is not enough if the number of function evaluations is really small, since the model needs some time to adapt to the function. But it is, of course, worth a try since a good implementation exists, and with DFO you never know...

The "best" depends on the problem at hand. Many decades ago I used a hill-climbing (Hooke-Jeeves) algorithm for my PhD thesis work since it was insensitive to some pathological nonlinearities. If the function is better behaved, it is probably not the best choice.

hi Antonio,

the original authors of CMA-ES and I have been working on a fast and up-to-date library for CMA-ES and related algorithms, you can find it here: https://github.com/beniz/libcmaes

It is designed to be very fast, scalable and easy to use.

Hi Everyone,

Thank you VERY much for all the answers! Here are some PRELIMINARY results. I will present more results as I get or implement more algorithms... The presented results show the convergence curves for Nelder-Mead, Genetic Algorithm, PSO and CMA-ES on the unimodal Sphere and Elliptic functions of the Large Scale Global Optimization benchmark. These are high-dimensional, ill-conditioned and non-separable functions (see the attached link for more information).

As it can be noticed Nelder-Mead shows a very slow convergence. We have obtain very good results with hybrid algorithms using Nelder-Mead on small dimensional molecular docking problems (results will be published soon ), but as expected, in high-dimensional search spaces Nelder-Mead's simplex collapses too fast. GA and PSO are somehow better, but still away from CMA-ES. However, even CMA-ES need over 1.000.000 function evaluations to reach solutions near the optimum (which is too much for hybridizing and restarts).

I'll keep testing more algorithms... some of your suggestions seem very promising. It would be great if you could provide a MATLAB code :)

hi Antonio, others and I are working on pushing CMA-ES to large-scale optimization.

If you can share the function you are trying to optimize, we can include it into our benchmarks and tell you whether better performances and results can be obtained. Libcmaes contains an implementation of active CMA-ES and sep-CMA-ES that might prove useful to you.

I made good experiences with the simplex method which is available in the "Numerical Recipes" - a collection of algorithms implemented in different programming languages http://nr.com/. Caution! Don't confuse the simplex algorithm of numerical optimization with the simplex method known in linear programming - that is something completely different!

I believe, the simple genetic algorithm (whether in binary coded chromosome or not) is the best optimizer for any sort of unimodal optimization problems. It has been widely tested over a range of benchmark and real-life problems. MATLAB also has some code for this in its GATOOLS.

In case the debate is still open, let me add a few algorithms that I do not think have been mentioned here. (Excuse me if they have, and I have missed those posts.) While the problem is said to be unimodal - which would be a relatively easy function and no really a global optimization problem, - there are several posts related to meta-heuristics, which are normally not recommended for well-behaved and expensive functions. (In such cases it is important to utilize the information from all computed points in the best possible manner, such that the number of needed function evaluations of the "real" objective is minimized.) So while I may talk nonsense here, let me suggest testing a surrogate or interpolating function (depending on the nature of the simulation used to evaluate the objective function). In the case of interpolating algorithms, we have these:

1. Jones et al (Global opt of expensive functions): http://link.springer.com/article/10.1023/A:1008306431147#page-1

2. Gutmann (A radial basis function approach for global opt.): http://link.springer.com/article/10.1023/A:1011255519438#page-1

3. Jacobsson et al (A method for simulation based optimization based on radial basis functions):

http://link.springer.com/article/10.1007%2Fs11081-009-9087-1#page-1

In case tests have not been completed yet, perhaps one or two of these would be a good point testing. There are matlab versions of several of these, one being the Matlab-utilizing Tomlab package.

Python  Library for EA: 

https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&cad=rja&uact=8&ved=0CCUQFjAB&url=https%3A%2F%2Fdeap.googlecode.com%2F&ei=LXDGU4SRNsfZ0QXM24CQBQ&usg=AFQjCNHLAR6l7zmXmlQ7imsqWjfg7YosMw&bvm=bv.71126742,d.d2k

https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&cad=rja&uact=8&ved=0CCcQFjAB&url=https%3A%2F%2Fpypi.python.org%2Fpypi%2Finspyred&ei=RnDGU5ehNarK0QX4zoCoCA&usg=AFQjCNGZnSSCS1kWUbuUSdJ9wk1vA3N6DA&bvm=bv.71126742,d.d2k

Variant PSO versions in JAVA:

http://www.cilib.net/

Fibonacci search is an alternative,

The best derivative -free methods  are  dixotomii methods  in the case one dimensial function.  When a function has many variables, then derivative free method is coordinate  Descent method  

There is an algorithm called simplex which is mot the one we are using for linear programming. In a n dimensional nonlinear optimization problems if you hose an initial point , the algorithm let you make a n+1 (simplex) initial points from which the algorithm searches to find the optimal solution within the per-specified resolution. 

PSO 

MATLAB programming codes for PSO

https://www.researchgate.net/publication/296636431_Codes_in_MATLAB_for_Particle_Swarm_Optimization?ev=prf_pub

regards

Code Codes in MATLAB for Particle Swarm Optimization

A fast local derivative-free local search that is optimal for convex functions is LBFGS https://en.wikipedia.org/wiki/Limited-memory_BFGS

When you define the objective function and the derivative, you can write a simple finite difference for the gradient function if you do not have a first derivative.

Since unimodal might be referring to the CDF, you might have a function that is convex and concave in your question, so you might need to make the search global by creating sample points over your search space and use local search at each of the sample points.

There are various ways to create sample points, such as quasi-monte carlo or an adaptive grid sampling, or many other methods.

LBFGS is not a derivative-free method. Actually, it is a limited memory quasi-Newton method that uses gradient information and estimates the Hessian of the function, and whose convergence relies on the fact that the objective function is C^2.

Usually, finite difference gradients are not very accurate, and for high dimensional problems for every gradient $O(n)$ function evaluations are needed. That usually rules out its usage in high dimensional settings, especially for expensive functions.

One quick correction to the above that I couldn't see how to edit later is CDF should be PDF.

AND, I did clearly state gradient in the answer I posted because he may not have been aware that even if he doesn't have a first derivative defined, use of the finite difference method as a gradient can be a very good substitute.   

And that actually handles high dimension better than many others, and so does quasi-monte carlo... seems as if you might have brought up strengths as criticisms.

Gradient based methods are indeed better in higher dimensions than derivative-free methods IF the gradient is readily available. If you need to spend thousands of function evaluations for a single gradient that speed advantage evaporates very quickly, unless one function evaluation is really cheap. But then usually the gradient is readily available, and you would not even consider using a derivative-free method.

Derivative-free methods are also very important if the objective function is computed by some simulation, so that the function values are not very accurate or somewhat noisy. Then, numerical gradients - since numerical differentiation is roughening - quickly become very imprecise, often losing the descent property altogether.

Quasi-Monte-Carlo has its main advantage in integration of high dimensional functions, not in global optimization of high dimensional functions.

Quasi-Monte-Carlo still can have an advantage in the sampling of high dimensional space (when sampling is used in global optimization) and that is in their use of Low Discrepancy Sequences or Halton methods.