Benchmarking the nelder-mead downhill simplex algorithm with many local restarts

ABSTRACT

We benchmark the Nelder-Mead downhill simplex method on the noisefree BBOB-2009 testbed. A multistart strategy is applied on two levels. On a local level, at least ten restarts are conducted with a small number of iterations and reshaped simplex. On the global level independent restarts are launched until $10^5 D$ function evaluations are exceeded, for dimension $D\ge20$ ten times less. For low search space dimensions the algorithm shows very good results on many functions. It solves 24, 18, 11 and 7 of 24 functions in 2, 5, 10 and 40-D.

REFERENCES

• 1: S. Finck, N. Hansen, R. Ros, and A. Auger. Real-parameter black-box optimization benchmarking 2009: Presentation of the noiseless functions. Technical Report 2009/20, Research Center PPE, 2009.
• 2: N. Hansen, A. Auger, S. Finck, and R. Ros. Real-parameter black-box optimization benchmarking 2009: Experimental setup. Technical Report RR-6828, INRIA, 2009.
• 3: N. Hansen, S. Finck, R. Ros, and A. Auger. Real-parameter black-box optimization benchmarking 2009: Noiseless functions definitions. Technical Report RR-6829, INRIA, 2009.
• 4: M. Luersen and R. Le Riche. Globalized Nelder-Mead method for engineering optimization. Computers and Structures, 82(23-26):2251--2260, 2004.
• 5: J. Nelder and R. Mead. The downhill simplex method. Computer Journal, 7:308--313, 1965.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems

General Terms:
Algorithms

Keywords:
CMA-ES, benchmarking, black-box optimization, direct search, evolutionary computation