Page 240 - Compact Numerical Methods For Computers

228 Compact numerical methods for computers
Hence the ratio
(18.33)
gives
a= l / ( 2r-1) (18.34)
as an estimate of the degree of the relationship between work and problem order,
n, of a given method. The limited extent of the tests and the approximation of
sums by integrals, however, mean that the results of such an analysis are no more
than a guide to the behaviour of algorithms. The results of the tests are presented
in table 18.5.
The conclusions which may be drawn from the table are loosely as follows.

(i) The Marquardt algorithm 23 is generally the most reliable and efficient.
Particularly if problems having ‘large’ residuals, which cause the Gauss-Newton
approximation (17.16) to be invalid, are solved by other methods or by increasing
the parameter phi in algorithm 23, it is extremely efficient, as might be expected
since it takes advantage of the sum-of-squares form.
(ii) The Marquardt algorithm using a numerical approximation (18.4) for the
Jacobian is even more efficient than its analytic-derivative counterpart on those
problems it can solve. It is less reliable, of course, than algorithms using analytic
derivatives. Note, however, that in terms of the number of parameters determined
successfully, only the variable metric algorithm and the Marquardt algorithm are
more effective.
(iii) The Nelder-Mead algorithm is the most reliable of the derivative-free
methods in terms of number of problems solved successfully. However, it is also
one of the least efficient, depending on the choice of measure w 1 or w , though in
0
some ways this is due to the very strict convergence criterion and the use of the
axial search procedure. Unfortunately, without the axial search, the number of
problems giving rise to ‘failures’ of the algorithm is 11 instead of four, so I cannot
recommend a loosening of the convergence criteria except when the properties of
the function to be minimised are extremely well known.
(iv) The conjugate gradients algorithm, because of its short code length and low
working-space requirements, should be considered whenever the number of
parameters to be minimised is large, especially if the derivatives are inexpensive
to compute. The reliability and efficiency of conjugate gradients are lower than
those measured for variable metric and Marquardt methods. However, this study,
by using equivalent function evaluations and by ignoring the overhead imposed by
each of the methods, is biased quite heavily against conjugate gradients, and I
would echo Fletcher’s comment (in Murray 1972, p 82) that ‘the algorithm is
extremely reliable and well worth trying’.
As a further aid to the comparison of the algorithms, this chapter is concluded
with three examples to illustrate their behaviour.

Example 18.1. Optimal operation of a public lottery
In example 12.1 a function minimisation problem has been described which arises
in an attempt to operate a lottery in a way which maximises revenue per unit