Page 183 - Compact Numerical Methods For Computers

172 Compact numerical methods for computers

14.2. POSSIBLE MODIFICATIONS OF THE NELDER-MEAD
ALGORITHM
Besides choices for (a, b, b' and g other than (14.11) there are many minor
variations on the basic theme of Nelder and Mead. The author has examined
several of these, mainly using the Rosenbrock (1960) test function of two
parameters
(14.16)
starting at the point (-1·2, 1).

(i) The function value S(b ) can be computed at each iteration. If S(b )<S(b ),
L
C
C
b is replaced by b . The rest of the procedure is unaffected by this change, which
C
L
is effectively a contraction of the simplex. If there are more than two parameters,
the computation of b C can be repeated. In cases where the minimum lies within
the current simplex, this modification is likely to permit rapid progress towards
the minimum. Since, however, the simplex moves by means of reflection and
expansion, the extra function evaluation is often unnecessary, and in tests run by
the author the cost of this evaluation outweighed the benefit.
(ii) In the case that S(b ) <S( b ) the simplex is normally expanded by extension
R
L
along the line (b -b ). If b is replaced by b , the formulae contained in the first
R C R E
two lines of equation (14.4) permit the expansion to be repeated. This modifica-
tion suffers the same disadvantages as the previous one; the advantages of the
repeated extension are not great enough-in fact do not occur often enough-to
offset the cost of additional function evaluations.
(iii) Instead of movement of the simplex by reflection of b H through b , one could
C
consider extensions along the line (b -b ), that is, from the ‘low’ vertex of the
C
L
simplex. Simple drawings of the two-dimensional case show that this tends to
stretch the simplex so that the points become coplanar, forcing restarts. Indeed,
a test of this idea produced precisely this behaviour.
(iv) For some sets of parameters b, the function may not be computable, or a
constraint may be violated (if constraints are included in the problem). In such
cases, a very large value may be returned for the function to prevent motion in
the direction of forbidden points. Box (1965) has enlarged on this idea in his
Complex Method which uses more than (n+1) points in an attempt to prevent all
the points collapsing onto the constraint.
(v) The portion of the algorithm for which modifications remain to be suggested
is the starting (and restarting) of the procedure. Until now, little mention has been
made of the manner in which the original simplex should be generated. Nelder
and Mead (1965) performed a variety of tests using initial simplexes generated by
equal step lengths along the parameter axes and various ‘arrangements of the
initial simplex.’ The exact meaning of this is not specified. They found the rate of
convergence to be influenced by the step length chosen to generate an initial
simplex. O’Neill (1971) in his FORTRAN implementation permits the step along
each parameter axis to be specified separately, which permits differences in the
scale of the parameters to be accommodated by the program. On restarting, these
steps are reduced by a factor of 1000. General rules on how step lengths should