Page 236 - Numerical Methods for Chemical Engineering

Trust-region Newton method 225

[1]
[2]
is B , B ,...,
T
γ( γ) T B [k] x( x) B [k]
[k+1]
[k]
B = B + T − T (5.38)
( γ) x ( x) B [k] x
Equivalent update formulas exist for the approximate Hessian inverse or Cholesky factor,
which are more commonly used in practice than (5.38). For further details of such quasi-
Newton methods consult Nocedal & Wright (1999).

Trust-region Newton method

Newton line search algorithms perform badly when B [k] is nearly singular, as the search
directions become erratic. The trust-region Newton method, in which step length and search
direction are chosen concurrently, is more robust in this case. For small p, the cost function
may be approximated in the vicinity of x [k] by a quadratic model function
1
[k] [k] [k] [k] [k]
F x + p ≈ F x + γ · p + p · B p ≡ m (p) (5.39)
2
[k]
[k]
We assume that m (p) agrees well with F(x) within a trust region |p| < . The trust
[k]
radius is modified from one iteration to the next based on the observed level of dis-
agreement between the true and model cost functions. We obtain x [k] by finding (at least
[k]
approximately) a minimum, within the trust region, of the model function m (p).
[k]
The advantage of the trust-region method is that even if B [k] is nearly singular, m (p)
still has a useful minimum within the trust region. As long as F(x) is reduced, x [k+1] =
x [k] + x [k] is accepted, else the old value is recycled and the trust radius is reduced. If the
[k]
[k]
[k]
[k]
agreement between F(x [k+1] ) − F(x ) and m ( x ) − m (0) is good (poor), the trust
radius is increased (decreased) for the next iteration.
The dogleg method
The dogleg method solves the trust-region subproblem approximately, assuming that B [k]
is positive-definite, although perhaps nearly singular. We say that this method solves the
problem approximately, because we do not bother to find the true minimum, but merely an
[k]
easily-found point within the trust region that lowers m (p) more than the steepest descent
method does.
The dogleg method is based upon an analysis of how the trust-region minimum changes
[k] [k]
as a function of the trust radius . When is very large, we have effectively an
(n)
unconstrained problem and the trust-region minimum is the full Newton step p , the
[k]
global minimum of m (p),
B [k] p (n) =−γ [k] (5.40)
[k] [k]
On the other hand, when is very small, the curvature of m (p) may be neglected, and
the minimum is found by moving in the steepest descent direction as far as is allowed,

p (d) =− [k] γ [k] [k] (5.41)
γ