Page 188 - Compact Numerical Methods For Computers

Direct search methods 177
Algorithm 19. A Nelder-Mead minimisation procedure (cont.)
action := ‘HI-REDUCTION‘; {default to hi-side reduction}
if VR<VH then {save reflection -- then try reduction on lo-side
if function value not also < VN}
begin {STEP 21: replace H with reflection point}
for i := 1 to n do P[i,H] := Bvec[i];
P[n1,H] := VR; {and save its function value}
action := ‘LO-REDUCTION‘; {re-label action taken}
end; {R replaces H so reduction on lo-side}
{STEP 22: carry out the reduction step}
for i := 1 to n do Bvec[i] := (l-beta)*P[i,H]+beta*P[i,C];
f := fminfn(n,Bvec,Workdata,notcomp); {function calculation}
if notcomp then f := big; funcount := funcount+1;
{STEP 23: test reduction point}
if f<P[nl,H] then {replace H -- may be old R in this case,
so we do not use VH in this comparison}
begin {STEP 24: save new point}
for i := 1 to n do P[i,H] := Bvec[i];
P[nl,H] := f; {and its function value, which may now not be
the highest in polytope}
end {replace H}
else {not a new point during reduction}
{STEP 25: test for failure of all tactics so far to reduce the
function value. Note that this cannot be an ‘else’ statement
from the ‘if VR<VH’ since we have used that statement in STEP
21 to save the reflection point as a prelude to lo-reduction
tactic, a step which is omitted when we try the hi-reduction,
which has failed to reduce the function value.}
if VR>=VH then {hi-reduction has failed to find a point lower
than H, and reflection point was also higher}
begin {STEP 26: shrink polytope toward point L}
action := ‘SHRINK’;
calcvert := true; {must recalculate the vertices after this}
size := 0.0;
for j := 1 to nl do
begin
if j<>L then {ignore the low vertex}
for i := l to n do
begin
P[i,j] := beta*(P[i,j]-P[i,L])+P[i,L]; {note the form of
expression used to avoid rounding errors}
size := size+abs(P[i,j]-P[i,L]);
end; {loop on i and if j<>L}
end; {loop on j}
if size<oldsize then {STEP 27 -- test if shrink reduced size}
begin {the new polytope is ‘smaller*, so we can proceed}
shrinkfail := false; {restart after shrink}
oldsize := size;
end
else {shrink failed -- polytope has not shrunk}
begin {STEP 28 -- exit on failure}
writeln(‘Polytope size measure not decreased in shrink’);
shrinkfail := true;