Selection of the initial simplex in the Nelder-Mead optimization algorithm

Question

What is the best way to initialize a simplex for use in Nelder-Mead simplex searches from the top of the user's guessing?

Answer 1

I'm not sure if there is a better way to select the initial simplex in the Nelder-Mead method, but here's what is done in normal practice.

The construction of the initial simplex S obtained from the generation of n+1 vertices x0,..,xn around what you call the end vertex xin user in the dimension space N The most common choice is

 x0=xin 

and the remaining N vertices are then generated so that

 xj=x0+hj*ej 

where ej is the unit vector of the j coordinate axis in R^n , and hj is the step size in the direction ej .

 hj = 0.05 if (x0)j is non-zero hj = 0.00025 if (x0)j=0 

with the (x0) jjth component x0. Note that this is a choice in the Matlab fminsearch program, which is based on the Nelder-Mead scheme.

You can find more information in

F. Gao, L. Han, "Implementation of the Nelder-Mead Algebra Algorithm with Adaptive Parameters", vol. Optim. Appl., DOI 10.1007 / s10589-010-9329-3

Answer 2

I think there is no general rule to better define the initial Nelder-Mead optimization simplex, because this requires at least a dim knowledge of the response surface.

However, it may be prudent to set points so that the simplex covers almost the entire possible range. The Nelder-Mead algorithm will automatically shorten the simplex and is close to optimal. The practical advantage of this policy is that you will get a better overall knowledge of the response function.

We did some tests with HillStormer ( "http://www.berkutec.com" ). This program allows you to test these policies on testfunctons, and we found that this plicy works pretty well.

Remember that the first simplex operation is a reflection. If the initial simplex covers the entire allowed range, reflection will certainly give limit values. But HillStormer allows you to use linear constraints and can avoid this problem.

You can find more information in the HillStormer system help.

V. Kuehne