Trust-region Newton method

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). 

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 

We assume that m (p) agrees well with F(x) witiiin a trust region p A l. The trust radius is modified from one iteration to the next based on the observed level of disagreement between the true and model cost functions. We obtain Ax l by finding (at least approximately) a minimum, within the trust region, of the model function /nPl(p). 

The advantage of the trust-region method is that even if pPl is nearly singular, mS ip) still has a useful minimum within the trust region. As long as F(x) is reduced, x + J = x -I- Ax l is accepted, else the old value is recycled and the trust radius is reduced. If the agreement between / (x + l) — F(xPJ) and j[ i(Axt ) — j[ J(0) is good (poor), the trust radius is increased (decreased) for the next iteration. 

The dogleg method solves the trust-region subproblem approximately, assuming that pW 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 easily-found point within the trust region that lowers wP (p) more than the steepest descent method does. 

---

Problem Type Large bound-constrained optimization problems Method Trust region Newton method... 

LANCELOT Philippe Toint pht raath.fundp.ac.be Various Newton methods for constrained and unconstrained nonlinear optimization, specializing in laige-scale problems and including a trust-region Newton method and an algorithm for nonlinear least squares that exploits partial separability... 

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.

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. 

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... 

ECEPP/2 QCPE 454 http //qcpe5.chera.indiana.edu/qcpe.html Calls SUMSL, a quasi-Newton method based on a trust-region approach (by Gay)... 

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... 

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 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 ... 

---