Page 203 - Compact Numerical Methods For Computers

192 Compact numerical methods for computers
direction to ensure that rounding errors in updating B and forming t via (15.29)
have not accidentally given a direction in which the function S cannot be
reduced. Therefore, a restart is suggested in any of the following cases:
T
(i) t g>0, that is, the direction of search is ‘uphill’.
(ii) b'=b, that is, no change is made in the parameters by the linear search
along t.
If either case (i) or case (ii) occurs during the first step after B has been set to
the unit matrix, the algorithm is taken to have converged.
(iii) Since the method reduces S along t, it is expected that
T
t g(b')
will be greater (less negative) than
T
t g(b).
T
Figure 15.1 illustrates this idea. Therefore, t y=d 1 should be positive. If it is not
T
there exists the danger that B may no longer be positive definite. Thus if t y <0,
the matrix B is reset to unity.
This completes the general description of a variable metric algorithm suitable
for small computers. I am indebted to Dr R Fletcher of Dundee University for
suggesting the basic choices of the Broyden-Fletcher-Shanno updating formula
and the acceptable point search. Note particularly that this search does not
require the gradient to be evaluated at each trial point

Algorithm 21. Variable metric minimiser
The algorithm needs an order-n square matrix B and five order-n vectors b, x, c, g and t. Care
should be taken when coding to distinguish between B and b.

procedure vmmin(n: integer; {the number of parameters in the
function to be minimised}
var Bvec, X: rvector; {the parameter values on
input (Bvec) and output (X) from minmeth}
var Fmin: real; {’minimum’ function value}
Workdata: probdata; {user defined data area}
var fail: boolean; {true if method has failed}
var intol: real); {user-initialized convergence
tolerance}
{alg21.pas == modified Fletcher variable metric method.,
Original method due to R. Fletcher, Computer Journal, vol 13,
pp. 317-322, 1970
Unlike Fletcher-Reeves, we do not use a quadratic interpolation,
since the search is often approximately a Newton step
Copyright 1988 J.C.Nash
}
const
Maxparm = 25; {maximum allowed number of parameters in the
present code. May be changed by the user,
along with dependent constants below.}
stepredn = 0.2; {factor to reduce stepsize in line search}