Newton line search methods

In MATLAB this algorithm is nsed by peg (more on this routine in Chapter 6). Note that at each CG iteration, we only need to mnltiply the current solution estimate by A, a quick procedure when A is sparse. Note also, that as no fill-in occurs, this method is well suited to large, sparse systems. 

The gradient vector provides information about the local slope of the cost function surface. Further improvement in efficiency is gained by using knowledge of the local curvature of the surface, as encoded in the real, symmetric Hessian matrix, with the elements 

we nse an iterative method with a line search direction 

We use die Hessian to make better selections of ffie search directions and step lengths. For small p, Taylor expansion of the gradient yields 

This appears to be equivalent to solving 7(x) = 0 1 Newton s method, but there is an important difference. Newton s method just looks for a point where the gradient is zero, but we specifically want to find a minimum of F x). W t, the gradient is zero at maxima and at saddle points as well. Thus, we must ensure that 7( 1 0, so that we can use a backtrack line search, starting from = 1, to enforce 

---

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

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. 

By far the most popular technique for optimization in the global region—at least in connection with updated Hessians—are the line search methods. The idea behind these schemes is that although the Newton or quasi-Newton step may not be satisfactory and therefore must be discarded, it still contains useful information. In particular, we may use the step to provide a direction for a one-dimensional minimization of the function. We then carry out... 

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

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

If the mixture has gelled, the program proceeds to calculate P(Fa° ) and P(Fg° ) using a binary search method (lines 2510-2770). This method is more convenient that the earlier approach of Bauer and Budde (10) who used Newton s method, since derivatives of the functions are not required. The program also calculates the probability generating functions used to calculate sol fractions and the two crosslink densities (lines 2800-3150). Finally, the sol fraction and crosslink densities are calculated and printed out (lines 3160-3340). The program then asks for a new percents of reaction for the A and B groups. To quit enter a percent reaction for A of >100. 

If fix) is convex, H(x) is positive-semidefinite at all points x and is usually positive-definite. Hence Newton s method, using a line search, converges. If fix) is not strictly convex (as is often the case in regions far from the optimum), H(x) may not be positive-definite everywhere, so one approach to forcing convergence is to replace H(x) by another positive-definite matrix. The Marquardt-Levenberg method is one way of doing this, as discussed in the next section. 

Of course, Newton s method does not always converge. GRG assumes Newton s method has failed if more than ITLIM iterations occur before the Newton termination criterion (8.86) is met or if the norm of the error in the active constraints ever increases from its previous value (an occurrence indicating that Newton s method is diverging). ITLIM has a default value of 10. If Newton s method fails but an improved point has been found, the line search is terminated and a new GRG iteration begins. Otherwise the step size in the line search is reduced and GRG tries again. The output from GRG that shows the progress of the line search at iteration 4 is... 

There Eire other Hessian updates but for minimizations the BFGS update is the most successful. Hessism update techniques are usually combined with line search vide infra) and the resulting minimization algorithms are called quasi-Newton methods. In saddle point optimizations we must allow the approximate Hessian to become indefinite and the PSB update is therefore more appropriate. 

Quadratic convergence means that eventually the number of correct figures in Xc doubles at each step, clearly a desirable property. Close to x Newton s method Eq. (3.9) shows quadratic convergence while quasi-Newton methods Eq. (3.8) show superlinear convergence. The RF step Eq. (3.20) converges quadratically when the exact Hessian is used. Steepest descent with exact line search converges linearly for minimization. 

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. 

While the steepest descent search direction s can be shown to converge to the minimum with a proper line search, in practice the method has slow and often oscillatory behavior. Most Quasi-Newton procedures, however, make this choice for the initial Step, for there is no information yet on G. 

In our experience the Newton and Quasi-Newton methods with the line search described is faster to reach a minimum than the restricted step method with confidence region. This latter method is a more "conservative" method as discussed in the results section. The restricted step methods, however, are very effective in searching for transition states [40,41]. 

The number of line searches, energy and gradient evaluations are given in Table VI for both the Newton and Quasi-Newton methods. Table VI clearly indicates that the use of an exact inverse Hessian requires less points to arrive at the optimum geometry. However in Table VI we have not included the relative computer times required to form the second derivative matrix. If this is taken into account, then the Newton s method with its requirement for an exact Hessian matrix is considerably slower than the quasi-Newton procedures. 

Note, that in general cases of an arbitrary nonlinear operator A, algorithm (5.45) may not converge (see for details Fletcher, 1995), and, in fact, (m ) may not even decrease with the iteration number n. This undesirable possibility can be eliminated by introducing a line search on every step of the Newton method ... 

In a similar way we can construct an algorithm of the regularized Newton method with a linear line search ... 

Quasi-Newton Methods In some sense, quasi-Newton methods are an attempt to combine the best features of the steepest descent method with those of Newton s method. Rec that the steepest descent method performs well during early iterations and always decreases the value of the function, whereas Newton s method performs well near the optimum but requires second order derivative information. Quasi-Newton methods are designed to start like the steepest descent method and finish like Newton s method while using only first order derivative information. The basic idea was originally proposed by Davidon (1959) and subsequently developed by Fletcher and PoweU (1963). An additioneil feature of quasi-Newton methods is that the minimum of a convex quadratic function ctm be found in at most n iterations if exact line searches are used. The basic... 

The BFGS formula is generally preferred to (26) since computational results have shown that it requires considerably less effort, especially when inexact line searches are used. Quasi-Newton methods, also referred to as variable metric methods, are much more widely used than either the steepest descent or Newton s method. For additional details and computational comparisons, see Fletcher (1987, pp. 44-74). 

The term with second order derivatives is ignored by the Gauss-Newton method. Let 0 denote the set of parameters that makes the value of the objective function a minimum. If any rv(0 ) (1 < v < n) is not small then the approximation of the Hessian matrix H (cf. (6.10)) is poor and a line search may be needed for the method to be convergent. 

At step k, this results in a rank k update to the Hessian, as opposed to the rank 1 and 2 formulas used in the quasi-Newton methods, leading to improved convergence properties. The line search is avoided by using a constrained quartic polynomial to estimate the position of the minimum. The energy and gradient at the line search minimum are obtained by interpolation rather than by recalculation. 

In the quasi-Newton method, the next geometry is obtained from the Newton formula (15.72) plus a line search. A commonly used alternative to the quasi-Newton method is to calculate the next set of nuclear coordinates by a modified form of (15.72) in which the current coordinates Xj, Fj are replaced by linear combinations of the current coordinates and the coordinates in all the previous search steps, and the current gradient components... 

---