Page 234 - Numerical Methods for Chemical Engineering

Newton line search methods 223

get new search direction, β [k] = γ [k+1] · γ [k+1] γ [k] · γ [k] ,
p [k+1] =−γ [k+1] + β [k] [k]
p
end for k = 0, 1,... (1 + ε)N
An alternative expression for the step length, equivalent to (5.18), is

a [k] = γ [k] · γ [k] p [k] · y [k] (5.25)
In MATLAB this algorithm is used by pcg (more on this routine in Chapter 6). Note that
at each CG iteration, we only need to multiply the current solution estimate by A, a quick
procedure when A is sparse. Note also, that as no fill-in occurs, this method is well suited
to large, sparse systems.

Newton line search methods

The gradient vector provides information about the local slope of the cost function surface.
Further improvement in efficiency is gained by using knowledge of the local curvature of
the surface, as encoded in the real, symmetric Hessian matrix, with the elements
2
2
∂γ k ∂ F ∂ F
H jk = = = = H kj (5.26)
∂x j ∂x j ∂x k ∂x k ∂x j
[k]
Again, we use an iterative method with a line search direction p ,
p
x [k+1] = x [k] + a [k] [k] (5.27)
We use the Hessian to make better selections of the search directions and step lengths. For
small p, Taylor expansion of the gradient yields
[k] [k] [k] 2
γ x + p − γ x ≈ H x p + O[|p| ] (5.28)
[k]
As γ(x min ) = 0,weset γ(x [k] + p) = 0 to yield a linear system for p :
[k] [k] [k]
H x p =−γ x (5.29)
This appears to be equivalent to solving γ(x) = 0 by Newton’s method, but there is an
important difference. Newton’s method just looks for a point where the gradient is zero,
but we specifically want to find a minimum of F(x). Yet, the gradient is zero at maxima
and at saddle points as well. Thus, we must ensure that p [k] · γ [k] < 0, so that we can use a
backtrack line search, starting from a [k] = 1, to enforce

[k+1] [k] [k] [k] [k]
F x = F x + a p < F x (5.30)
How can we be assured that the search direction generated by (5.29) is indeed a descent
direction?