Page 233 - Numerical Methods for Chemical Engineering

222 5 Numerical optimization

to be A-conjugate to the old one,

p [k] · Ap [k+1] = 0 (5.22)
then p [k] · γ(x [k+2] ) = 0, and performing a line minimization along p [k+1] will do nothing
[k]
to alter the fact that we have found the optimal coordinate in the direction p . The N vectors
[1]
[2]
p , p ,..., p [N] generated by this method are linearly independent. As after N iterations
we will have found the correct coordinates of the minimum in each of these directions, we
are guaranteed to have found the exact position of the minimum. Thus, in the absence of
round-off error, the conjugate gradient algorithm terminates after at most N iterations. Note
[k]
that this method is somewhat misnamed, as by (5.22) it is the search directions {p } that
[k]
are conjugate, not the gradients {γ }, which in fact may be shown to be orthogonal.
To implement the A-conjugacy condition, p [k] · Ap [k+1] = 0, we write the new search
direction as the linear combination
[k+1] [k+1] [k] [k]
p =−γ + β p (5.23)
Multiplying by A and enforcing A-conjugacy yields

p
p [k] · Ap [k+1] = 0 =−p [k] · Aγ [k+1] + β [k] [k] · Ap [k]
γ [k+1] · Ap [k] γ [k+1] · γ [k+1]
β [k] = = (5.24)
p [k] · Ap [k] γ [k] · γ [k]
The latter form for β [k] is obtained from the first through use of conditions that follow
from A-conjugacy. If this formula for β [k] is applied to a nonquadratic cost function,
the CG-FR method is obtained. Because the relations above assume the cost function to
be quadratic, the CG-FR method is not guaranteed to terminate in N iterations; however, once
the algorithm is close enough to the minimum for quadratic approximation to be accurate,
the self-terminating aspects of the conjugate gradient method become useful. The CG-FR
and CG-PR formulas agree for a quadratic cost function (as γ [k] · γ [k+1] = 0). Whenever
the cost function is far from quadratic, the orthogonality of the gradients will be lost, and
the additional term in the CG-PR formula pushes the search direction towards the steepest
descent direction. This usually improves the performance, and the CG-PR method is the
recommended choice of gradient method.
T
1 T
The conjugate gradient algorithm to minimize F(x) = x Ax − b x, solving Ax = b,
2
is
[0]
make initial guess x ; set initial gradient, γ [0] = Ax [0] − b
set initial search direction, p [0] =−g [0]
for k = 0, 1,..., (1 + ε)N, where ε ≥ 0 allows for round-off error
[k]
if γ ≤ δ tol , STOP and ACCEPT x [k] as solution
perform line search.
[k]

y [k] = Ap , a [k] =− p [k] · γ [k] p [k] · y [k]
p
x [k+1] = x [k] + a [k] [k]
[k] [k]
compute new gradient, γ [k+1] = γ [k] + a y