Page 182 - Compact Numerical Methods For Computers

Direct search methods 171
heuristically based on a largely intuitive conception of the minimisation problem.
As such there will always be functions which cannot be minimised by this method
because they do not conform to the idealisation. Despite this, the algorithm is
surprisingly robust and, if permitted to continue long enough, almost always finds
the minimum.
The thorniest question concerning minimisation algorithms must, therefore, be
addressed: when has the minimum been found? Nelder and Mead suggest using
the ‘standard error’ of the function values

(14.12)

where

(14.13)

The procedure is taken to have converged when the test value falls below some
preassigned tolerance. In the statistical applications which interested Nelder and
Mead, this approach is reasonable. However, the author has found this criterion
to cause premature termination of the procedure on problems with fairly flat areas
on the function surface. In a statistical context one might wish to stop if such a
region were encountered, but presuming the minimum is sought. it seems logical
to use the simpler test for equality between S(b ) and S(b ), that is, a test for
L
H
equal height of all points in the simplex.
An additional concern on machines with low-precision arithmetic is that it is
possible for a general contraction (14.10) not to reduce the simplex size. There-
fore, it is advisable to compute some measure of the simplex size during the
contraction to ensure a decrease in the simplex size, as there is no point in
continuing if the contraction has not been effective. A very simple measure is the
sum
(14.14)

where
(14.15)

Finally, it is still possible to converge at a point which is not the minimum. If,
for instance, the (n+1) points of the simplex are all in one plane (which is a line
in two dimensions), the simplex can only move in (n-1) directions in the
n-dimensional space and may not be able to proceed towards the minimum.
O’Neill (1971), in a FORTRAN implementation of the Nelder-Mead ideas,
tests the function value at either side of the supposed minimum along each
of the parameter axes. If any function value is found lower than the current
supposed minimum, then the procedure is restarted.
The author has found the axial search to be useful in several cases in avoiding
false convergence. For instance, in a set of 74 tests, six failures of the procedure
were observed. This figure would have been 11 failures without the restart facility.