Page 198 - Compact Numerical Methods For Computers

Descent to a minimum I: variable metric algorithms 187

As in the one-dimensional root-finding problem, it is possible to seek such
solutions via a linear approximation from the current point b as in equation
(13.25), that is
g (b’)=g(b)+H(b)(b' -b) (15.7)

where H(b) is the Hessian matrix
(15.8)
of second derivatives of the function to be minimised or first derivatives of the
nonlinear equations. For convex functions, H is at least non-negative definite.
For the current purpose, suppose it is positive definite so that its inverse exists.
Using the inverse together with equations (15.6) implies
- l
b' =b-H (b)g(b) (15.9)
which is Newton’s method in n parameters. This is equivalent to equation (15.2)
with
B=H - 1 k = l . (15.10)
The step parameter k is rarely fixed, however, and usually some form of linear
search is used (§13.2). While Newton’s method may be useful for solving
nonlinear-equation systems if the n-dimensional equivalents of the one-
dimensional difficulties of the algorithm are taken care of, for minimisation
problems it requires that second derivatives be computed.
2
This means that n second derivative evaluations, n first derivative evaluations
and a matrix inverse are needed even before the linear search is attempted.
Furthermore the chances of human error in writing the subprograms to compute
these derivatives is very high-the author has found that most of the ‘failures’ of
his algorithms have been due to such errors when only first derivatives were
required. For these reasons, Newton’s method does not recommend itself for most
problems.
Suppose now that a method could be found to approximate H -1 directly from
the first derivative information available at each step of the iteration defined by
(15.2). This would save a great deal of work in computing both the derivative
matrix H and its inverse. This is precisely the role of the matrix B in generating the
conjugate search directions of the variable metric family of algorithms, and has
led to their being known also as quasi-Newton methods.

15.2. VARIABLE METRIC ALGORITHMS
Variable metric algorithms, also called quasi-Newton or matrix iteration al-
gorithms, have proved to be the most effective class of general-purpose methods
for solving unconstrained minimisation problems. Their development is continu-
ing so rapidly, however, that the vast array of possibilities open to a programmer
wishing to implement such a method is daunting. Here an attempt will be made to
outline the underlying structure on which such methods are based. The next
section will describe one set of choices of strategy.
All the variable metric methods seek to minimise the function S(b) of n