Approximate Newton search direction

Thus, the approximate Newton search direction in TN methods is obtained by allowing a nonzero residual norm rk = rj = H p + gA at each step. The size of this residual is monitored systematically according to the progress made. This formulation leads to a doubly nested iteration structure for every outer Newton iteration k (associated with xk) there corresponds an inner loop for pk p p 1,. . . . ... 

Newton variants are constructed by combining various strategies for the individual components above. These involve procedures for formulating Hk or Hk, dealing with structures of indefinite Hessians, and solving for the modified Newton search direction. For example, when Hk is approximated by finite differences, the discrete Newton subclass emerges.5 91-94 When Hk, or its inverse, is approximated by some modification of the previously constructed matrix (see later), QN methods are formed.95-110 When is nonzero, TN methods result,111-123 because the solution of the Newton system is truncated before completion. 

Truncated Newton methods were introduced in the early 1980s111-114 and have been gaining popularity ever since.82-109 110 115-123 Their basis is the following simple observation. An exact solution of the Newton equation at every step is unnecessary and computationally wasteful in the framework of a basic descent method. That is, an exact Newton search direction is unwarranted when the objective function is not well approximated by a convex quadratic and/or the initial point is distant from a solution. Any descent direction will suffice in that case. As a solution to the minimization problem is approached, the quadratic approximation may become more accurate, and more effort in solution of the Newton equation may be warranted. 

Remark 6.1 IftheJacobian Je(0) has full rank, then the approximation (0)Je(0) of the Hessian H is positive definite and the Gauss-Newton search direction A0 is a downhill direction. 

Newton s method makes use of the second-order (quadratic) approximation of fix) at x and thus employs second-order information about fix), that is, information obtained from the second partial derivatives of fix) with respect to the independent variables. Thus, it is possible to take into account the curvature of fix) at x and identify better search directions than can be obtained via the gradient method. Examine Figure 6.9b. 

Procedures that compute a search direction using only first derivatives of/provide an attractive alternative to Newton s method. The most popular of these are the quasi-Newton methods that replace H(x ) in Equation (6.11) by a positive-definite approximation W ... 

Another technique for handling the mass balances was introduced by Castillo and Grossmann (1). Rather than convert the objective function into an unconstrained form, they implemented the Variable Metric Projection method of Sargent and Murtagh (32) to minimize Gibbs s free energy. This is a quasi-Newton method which uses a rank-one update to the approximation of H l, with the search direction "projected" onto the intersection of hyperplanes defined by linear mass balances. 

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. 

First, when Hk is not positive-definite, the search direction may not exist or may not be a descent direction. Strategies to produce a related positive-definite matrix Hk, or alternative search directions, become necessary. Second, far away from x, the quadratic approximation of expression [34] may be poor, and the Newton direction must be adjusted. A line search, for example, can dampen (scale) the Newton direction when it exists, ensuring sufficient decrease and guaranteeing uniform progress toward a solution. These adjustments lead to the following modified Newton framework (using a line search). 

Efficient minimization of the energy is an essential part of the simulation of solids as it is a pre-requisite for any subsequent evaluation of physical properties and normally represents the computationally most demanding stage. The most efficient minimizers are those which are based on the Newton-Raphson method, in which the Hessian or some approximation to it is used. The minimization search direction, x, is then given by ... 

The subspaces could be spanned by the usual search directions current gradient g xk) Newton step n(xjb), truncated Newton step n xk). Or we can use the iteration history of the solver (which is very cheap) old gradient values, previous iteration steps. And it is possible to use curve approximations, or any other useful information at hand. The choice should be adapted to the problem (size, costs, known behavior, etc.). 

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

This formula is exact for a quadratic function, but for real problems a line search may be desirable. This line search is performed along the vector — x. . It may not be necessary to locate the minimum in the direction of the line search very accurately, at the expense of a few more steps of the quasi-Newton algorithm. For quantum mechanics calculations the additional energy evaluations required by the line search may prove more expensive than using the more approximate approach. An effective compromise is to fit a function to the energy and gradient at the current point x/t and at the point X/ +i and determine the minimum in the fitted function. 

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

Newton s method can be applied to the unconstrained minimization problem as well to minimize g(x), take /(x) = g (x) and use Newton s method to search for a zero of /(x). Each step of the method can be interpreted as constructing a quadratic approximation of g(x) and stepping directly to the minimum of this approximation. 

Early in the quasi-Newton procedure, when one is not very close to a minimum, the procedure may well predict large coordinate changes for which the quadratic approximation to the PES may be quite inaccurate and the predicted quasi-Newton step might make things worse, rather than better. To avoid this problem, one imposes a trust radius. When the length of a predicted step exceeds the trust radius, the coordinate changes are reduced by a scale factor also, the direction of the step may be varied from the quasi-Newton prediction using some other search procedure. 

---