Page 208 - Compact Numerical Methods For Computers

Chapter 16

DESCENT TO A MINIMUM II:
CONJUGATE GRADIENTS

16.1. CONJUGATE GRADIENTS METHODS
On a small computer, the principal objection to the Nelder-Mead and variable
2
metric methods is their requirement for a working space proportional to n ,
where n is the number of parameters in the function to be minimised. The
parameters b and gradient g require only n elements each, so it is tempting to
consider algorithms which make use of this information without the requirement
that it be collected in a matrix. In order to derive such a method, consider once
again the quadratic form
T T
S(b)=½b Hb-c b+(anyscalar) (15.11)
of which the gradient at b is
g=Hb- c . (15.17)
Then if the search direction at some iteration j is t , we have
j
y =g j+ l -g =k Ht j (15.18)
j
j
j
where k j is the step-length parameter.
If any initial step t is made subject only to its being ‘downhill’, that is
1
(16.1)
then the construction of search directions t , i=1, 2, . . . , n, conjugate with respect
i
to the Hessian H, is possible via the Gram-Schmidt process (see Dahlquist and
Björck 1974, pp 201-4). That is to say, given an arbitrary new ‘downhill’
direction q i at step i, it is possible to construct, by choosing coefficients Z , a
ij
direction
(16.2)

such that
for j<i. (16.3)

This is achieved by applying to both sides of equation (16.2), giving
(16.4)
by substitution of the condition (16.3) and the assumed conjugacy of the t , j= 1 ,
j
2, . . . , (i-1). Note that the denominator of (16.4) cannot be zero if H is positive
definite and t j is not null.
197