Page 95 - Numerical methods for chemical engineering

The trust-region Newton method 81

step satisfies the descent criterion (the 2-norm is reduced), it is accepted. Otherwise, the
fractional step length is reduced by one-half iteratively until the descent criterion is satisfied.
The algorithm of the reduced-step Newton method with a weak line search is

[0]
[0]
Guess x ; compute f(x ); initialize B [0]
for k = 0, 1, 2,..., k max
& & [k]
if f (x ) ≤ δ tol , STOP and ACCEPT solution x s ≈ x
[k] &
&
2
[k]
[k]
solve linear system B x [k] =− f (x )
for m = 0, 1, 2,..., m max
[k] −m
α = 2
[k+1] [k] [k] [k]
x = x + α x
[k+1]
calculate f x
2 2
& & & & [k]
if & f (x [k+1] & & f (x ) , STOP m iterations and accept α
)
[k] &
2 2
end of m = 0, 1, 2,..., m max for loop
end of k = 0, 1, 2,..., k max for loop
Performance of the reduced-step Newton method for an example
system of two equations
We now revisit the example system
2
3
f 1 (x 1 , x 2 ) = 3x + 4x − 145 = 0
1 2
(2.84)
2
3
f 2 (x 1 , x 2 ) = 4x + x + 28 = 0
1 2
T
that has a real solution at x s = [3 4] , using now the reduced-step Newton method. Once
again, the trajectories of the solution estimates are plotted as connected circles superimposed
on the contour plot of the 2-norm. Figure 2.13 shows the trajectory for the guess (2,1) that
converges in six iterations without the erratic first step of the full-step Newton trajectory
in Figure 2.9. With the guess (1,1), the reduced-step trajectory of Figure 2.14 likewise
shows better performance than the full-step trajectory of Figure 2.10. But, with a guess of
(2, −1), Figure 2.15 demonstrates that the reduced-step method can “hang up” by taking
only very small steps when the direction of the Newton step lies nearly perpendicular to the
local gradient of the 2-norm. Then, the trust-region Newton method, described below, does
better as it varies concurrently with both the step length and direction.

The trust-region Newton method

As noted in the example above, the reduced-step Newton method can fail when the search
direction is nearly perpendicular to the steepest descent direction so that only very short
steps are taken. This problem originates from the fact that the direction of the full Newton
step is always accepted; we reduce only the magnitude of the step to attain reduction of