|GNU Scientific Library Reference Manual - Third Edition (v1.12)|
by M. Galassi, J. Davies, J. Theiler, B. Gough, G. Jungman, P. Alken, M. Booth, F. Rossi
Paperback (6"x9"), 592 pages, 60 figures
RRP £24.95 ($39.95)
35.8 Algorithms without Derivatives
The algorithms described in this section use only the value of the function at each evaluation point.
- Minimizer: gsl_multimin_fminimizer_nmsimplex2
- Minimizer: gsl_multimin_fminimizer_nmsimplex
- These methods use the Simplex algorithm of Nelder and Mead. They construct
n vectors p_i from the
starting vector x and the vector step_size as follows:
p_0 = (x_0, x_1, ... , x_n) p_1 = (x_0 + step_size_0, x_1, ... , x_n) p_2 = (x_0, x_1 + step_size_1, ... , x_n) ... = ... p_n = (x_0, x_1, ... , x_n+step_size_n)
These vectors form the n+1 vertices of a simplex in n dimensions. On each iteration the algorithm tries to improve the parameter vector p_i corresponding to the highest function value by simple geometrical transformations. These are reflection, reflection followed by expansion, contraction and multiple contraction. Using these transformations the simplex moves through the parameter space towards the minimum, where it contracts itself.
After each iteration, the best vertex is returned. Note, that due to the nature of the algorithm not every step improves the current best parameter vector. Usually several iterations are required.
The minimizer-specific characteristic size is calculated as the average distance from the geometrical center of the simplex to all its vertices. This size can be used as a stopping criteria, as the simplex contracts itself near the minimum. The size is returned by the function
nmsimplex2version of this minimiser is a new O(N) implementation of the earlier O(N^2)
nmsimplexminimiser. It calculates the size of simplex as the rms distance of each vertex from the center rather than the mean distance, which has the advantage of allowing a linear update.
|ISBN 0954612078||GNU Scientific Library Reference Manual - Third Edition (v1.12)||See the print edition|