Page 180 - Compact Numerical Methods For Computers

Direct search methods 169

FIGURE 14.1. Points generated by the Nelder-Mead simplex algorithm
in two dimensions. Point 1, b L , the lowest vertex in the simplex; point
2, b N , the next-to-highest vertex: and point 3, b H , the highest vertex.
Point 4, b C , the centroid of all points except b H , that is, of b N and b L .
Also one of the points generated by a general contraction of the
simplex towards b L . Point 5, b R , the reflection of b H through b c ; point 6,
b E , the result of extension of the line (b C , b R ); point 7, the result of
reduction of the line (b C , b R ) which occurs when b R is lower than b H
but higher than b N ; and point 8, the result of reduction of the line
(b C , b H ). Point 9, one of the points of the simplex generated by a
general contraction of the simplex made up of vertices 1, 2 and 3
towards b L .

The operation of reflection then reflects b through b using a reflection factor (a,
C
H
that is
b = b +a(b -b )
C
R
H
C
= ( l +a)b -ab . (14.3)
C
H
If S(b ) is less than S(b ) a new lowest point has been found, and the simplex can
R
L
be expanded by extending the line (b -b ) to give the point
C
R
(14.4)
where g, the expansion factor, is greater than unity or else (14.4) represents a
contraction. If S(b )<S(b ) then b H is replaced by b E and the procedure
R
E
repeated by finding a new highest point and a new centroid of n points b .
C
Otherwise b is the new lowest point and it replaces b .
R H