Menu
What's the best way to initialize a simplex for use in a Nelder-Mead simplex search from a user's 'guess' vertex?
859
The Nelder-Mead simplex method uses a simplex to traverse the space in search of a minimum. — Page 105, Algorithms for Optimization, 2019. The algorithm works by using a shape structure (called a simplex) composed of n + 1 points (vertices), where n is the number of input dimensions to the function.
Nelder–Mead in n dimensions maintains a set of n + 1 test points arranged as a simplex. It then extrapolates the behavior of the objective function measured at each test point in order to find a new test point and to replace one of the old test points with the new one, and so the technique progresses.
Nelder Mead's simplex method is considered as a fast and simple algorithm.
Abstract. Nelder–Mead simplex method (NM), originally developed in deterministic optimization, is an efficient direct search method that optimizes the response function merely by comparing function values.
I'm not sure if there is a best way to choose the initial simplex in the Nelder-Mead method, but the following is what is done in common practice.
The construction of the initial simplex S is obtained from generating n+1 vertices x0,..,xn around what you call a user's "guess" vertex xin in a N dimensional space. The most frequent 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-th coordinate axis in R^n and hj is a step-size in the direction of ej.
hj = 0.05 if (x0)j is non-zero
hj = 0.00025 if (x0)j=0
with (x0)j the j-th component of x0. Note that this is the choice in Matlab's fminsearch routine, which is based on the Nelder-Mead scheme.
You can find some more information in
F. Gao, L. Han, "Implementing the Nelder-Mead simplex algorithm with adaptive parameters", Comput. Optim. Appl., DOI 10.1007/s10589-010-9329-3
132
I think there is no general rule to determine best the initial simplex of the Nelder-Mead optimization because this required at least a vague knowledge of the response surface.
However, it can be a reasonable policy to set the points in such a way that the simplex covers virtually the entire possible range. The algorithm of Nelder-Mead will shrink automatically the simplex and aproximate to the optimum. The practical advantage of this policy is that you will obtain a better overall-knowledge of the response-function.
We have done some tests with HillStormer("http://www.berkutec.com"). This program permits to test these policies on testfunctons and we found that this plicy works rather well.
Please remember that the first simplex-opereation is añways a reflection. If the starting simplex covers the whole permitted range the reflection necessarily will give a point off limits. But HillStormer allows to use linear constraints and can avoid this problem.
You can find some more information in the system-help of HillStormer.
B. Kühne
31
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
