The trust-region Newton method

Performance of the reduced-step Newton method for an example system of two equations 

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 frill Newton step is always accepted we rednce only the magnitude of the step to attain rednction of 

---

Newton line search algorithms perform badly when 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 smallp, the cost function may be approximated in the vicinity of x by a quadratic model function... 

Figure 5.9 The trust-region Newton dogleg method finds the position on the two connected line segments that minimizes the model function while lying within the trust region.

Since the Newton eigenvector method is equivalent to the level-shifted Newton method of Section 12.3, it yields the same set of solutions. In our discu.s.sion of the level-shifted Newton method, we noted that, for excited states, it is not always possible to obtain a solution consistent with the first-order condition on the energy and the condition on the length of the step. The same situation may arise in the NEO method as well for excited states, it may not always be possible to generate a step (12.4.22) to the boundary of the trust region. In such situations, we may instead adjust a so as to yield the shortest possible step and then scale the resulting step down to the desired length. 

The dogleg method is based upon an analysis of how the trust-region minimum changes as a function of the trust radius A l. When A is very large, we have effectively an unconstrained problem and the trust-region minimum is the fiill Newton step the global minimum of m p). 

The dogleg method allows us to identify quickly a point within the trust region that lowers the model cost function at least as much as the Cauchy point. The advantage over the Newton line search procedure is that the full Newton step is not automatically accepted as the search direction, avoiding the problems inherent in its erratic size and direction when... 

In the trust-region or restricted-step method [19], the Newton step (10.8.2) is taken only if it is smaller than or equal to the trust radius h ... 

Difficulty 3 can be ameliorated by using (properly) finite difference approximation as substitutes for derivatives. To overcome difficulty 4, two classes of methods exist to modify the pure Newton s method so that it is guaranteed to converge to a local minimum from an arbitrary starting point. The first of these, called trust region methods, minimize the quadratic approximation, Equation (6.10), within an elliptical region, whose size is adjusted so that the objective improves at each iteration see Section 6.3.2. The second class, line search methods, modifies the pure Newton s method in two ways (1) instead of taking a step size of one, a line search is used and (2) if the Hessian matrix H(x ) is not positive-definite, it is replaced by a positive-definite matrix that is close to H(x ). This is motivated by the easily verified fact that, if H(x ) is positive-definite, the Newton direction... 

Although line searches are typically easier to program, trust region methods may be effective when the procedure for determining the search direction p is not necessarily one of descent. This may be the case for methods that use finite-difference approximations to the Hessian in the procedure for specifying p (discussed in later sections). As we shall see later, in BFGS quasi-Newton or truncated Newton methods line searches may be preferable because descent directions are guaranteed. 

How is it possible to overcome the discussed shortcomings of line search methods and to embed more information about the function into the search for the local minimum One answer are trust-region methods (or restricted step methods). They do a search in a restricted neighborhood of the current iterate and try to minimize a quadratic model of /. For example in the double-dogleg implementation, it is a restricted step search in a two-dimensional subspace, spanned by the actual gradient and the Newton step (and further reduced to a non-smooth curve search). For information on trust region methods see e.g. Dennis and Schnabel [2], pp. 129ff. 

The method therefore reduces to Newton s method in the local region with its rapid rate of convergence. Notice that in each iteration we always first try the Newton step Eq. (42), resorting to the level-shifted step Eq. (41) only if the Newton step is larger than the trust radius. 

If we relax the condition that the algorithms should be globally convergent, then quasi-Newton methods may be quite useful and cost-effective, as demonstrated by Culot et al [49]. These authors use a trust-region based quasi-Newton method with an exact initial Hessian and converge in a modest number of iterations (ten to twenty) provided the initial guess is a reasonable one. 

Notice that the quasi-Newton methods, descent methods and trust region methods form a hierarchy with respect to the goodness of the initial guess when searching for a minimizer of E, see Table 3. Whenever x ... 

Many Newton methods (see next section for details) based on trust-region approaches determine a candidate Sk by solving the linear system... 

Table 10.4 Convergence of Hartree-Fock calculations on the water molecule in the cc-pVQZ basis using the standard SCF method, the DIIS method and the Newton trust-region method. For each iteration, we have listed the energy relative to the converged energy in Eh. The calculations have been carried out at the geometries Rref and 2/ tef of Section 5.3.3...

In the Newton trust-region method, we must in each iteration solve a linear set of equations (10.8.2) or (10.8.6). The number of nonredundant parameters is usually so large that these equations... 

For a comparison of Newton s method and the SCF method, we return to Table 10.4. For each iteration, we have here listed the errors in the energy obtained using the second-order trust-region method, the naive SCF method and the DIIS method for the water molecule in the cc-pVQZ... 

---