Page 179 - Compact Numerical Methods For Computers

Chapter 14
DIRECT SEARCH METHODS

14.1. THE NELDER-MEAD SIMPLEX SEARCH FOR THE
MINIMUM OF A FUNCTION OF SEVERAL PARAMETERS

The first method to be examined for minimising a function of n parameters is a
search procedure based on heuristic ideas. Its strengths are that it requires no
derivatives to be computed, so it can cope with functions which are not easily
written as analytic expressions (for instance, the result of simulations), and that it
always increases the information available concerning the function by reporting its
value at a number of points. Its weakness is primarily that it does not use this
information very effectively, so may take an unnecessarily large number of
function evaluations to locate a solution. Furthermore, the method requires (n+1)
by (n+2) storage locations to hold intermediate results in the algorithm, so is not
well adapted to problems in a large number of parameters. However. for more
than about five parameters the procedure appears to become inefficient. Justifica-
tion of the choice of this algorithm is postponed until §14.4.
The original paper of Nelder and Mead (1965) outlines quite clearly and
succinctly their method, which is based on that of Spendley et al (1962). The
method will be described here to point out some particular modifications needed
to improve its reliability on small machines, particularly those with arithmetic
having few digits in the mantissa.
A simplex is the structure formed by (n+1) points, not in the same plane, in an
n-dimensional space. The essence of the algorithm is as follows: the function is
evaluated at each point (vertex) of the simplex and the vertex having the highest
function value is replaced by a new point with a lower function value. This is done
in such a way that ‘the simplex adapts itself to the local landscape, and contracts
on to the final minimum.’ There are four main operations which are made on the
simplex: reflection, expansion, reduction and contraction. In order to operate on
the simplex, it is necessary to order the points so that the highest is b , the next-
H
to-highest b , and the lowest b . Thus the associated function values obey
L
N
S(b )>S(b )>S(b )>S(b ) (14.1)
i
L
N
H
for all i H, N or L. Figure 14.1 illustrates the situation.
The centroid of all the points other than b H is defined by
(14.2)