Page 181 - Compact Numerical Methods For Computers

170 Compact numerical methods for computers
In the case where b R is not a new lowest point, but is less than b , the
N
next-to-highest point, that is
S( b )<S(b )<S(b ) (14.5)
L
R
N
b is replaced by b and the procedure repeated. In the remaining situation, we
H R
have S(b ) at least as great as S(b ) and should reduce the simplex.
R N
There are two possibilities. (a) If
S(b )<S(b )<S(b ) (14.6)
R
N
H
then the reduction is made by replacing b H by b R and finding a new vertex
between b C and b R (now b ). This is a reduction on the side of the reflection
H
(‘low’ side). (b) If
S(b )>S(b ) (14.7)
H
R
the reduction is made by finding a new vertex between b C and b (‘high’ side).
H
In either of the above cases the reduction is controlled by a factor b between 0
and 1. Since case (a) above replaces b H by b the same formula applies for the
R
new point b S (‘S’ denotes that the simplex is smaller) in both cases. b H is used to
denote both b and b since in case (a) b has become the new highest point in
R H R
the simplex
(14.8)
The new point b then replaces the current b , which in case (a) is, in fact, b ,
R
H
S
unless
S(b )>min(S(b ),S(b )). (14.9)
S
R
H
The replacement of b by b in case (a) will, in an implementation, mean that
H R
this minimum has already been saved with its associated point. When (14.9) is
satisfied a reduction has given a point higher than S(b ), so a general contraction
N
of the simplex about the-lowest point so far, b , is suggested. That is
L
(14.10)
for all i L. In exact arithmetic, (14.10) is acceptable for all points, and the
author has in some implementations omitted the test for i = L. Some caution is
warranted, however, since some machines can form a mean of two numbers which
is not between those two numbers. Hence, the point b L may be altered in the
operations of formula (14.10).
Different contraction factors b and b' may be used in (14.8) and (14.10). In
practice these, as well as a and g can be chosen to try to improve the rate of
convergence of this procedure either for a specific class or for a wide range of
problems. Following Nelder and Mead (1965), I have found the strategy
a = 1 g = 2 b' = b = 0·5 (14.11)
to be effective. It should be noted, however, that the choice of these values is
based on limited testing. In fact, every aspect of this procedure has been evolved