Quasi-Newton methods procedures

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

We have referred to quasi-Newton methods rather than the quasi-Newton method because there are multiple definitions that can be used for the function F in this expression. The details of the function F are not central to our discussion, but you should note that this updating procedure now uses information from the current and the previous iterations of the method. This is different from all the methods we have introduced above, which only used information from the current iteration to generate a new iterate. If you think about this a little you will realize that the equations listed above only tell us how to proceed once several iterations of the method have already been made. Describing how to overcome this complication is beyond our scope here, but it does mean than when using a quasi-Newton method, the convergence of the method to a solution should really only be examined after performing a minimum of four or five iterations. 

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. 

Any quasi-Newton method for the minimization of E can be applied. We use the Broyden-Fletcher-Goldfarb-Shanno [24] procedure. 

The most efficient methods that use gradients, either numerical or analytic, are based upon quasi-Newton update procedures, such as those described below. They are used to approximate the Hessian matrix H, or its inverse G. Equation (C.4) is then used to determine the step direction q to the nearest minimum. The inverse Hessian matrix determines how far to move along a given gradient component of f, and how the various coordinates are coupled. The success of methods that use approximate Hessians rests upon the observation that when f = 0, an extreme point is reached regardless of the accuracy of H, or its inverse, provided that they are reasonable. 

As previously commented, the standard method for solving equations is Newton s method. But this requires the calculation of a Jacobian matrix at each iteration. Even assuming that accurate derivatives can be calculated, this is frequently the most time-consuming activity for some problems, especially if nested nonlinear procedures are used. On the other hand, we can also consider the class of quasi-Newton methods where the Jacobian is approximated based on differences in x and/(x), obtained from previous iterations. Here, the motivation is to avoid evaluation of the Jacobian matrix. 

Descent methods are specific (quasi-)Newton methods which look for minimizers only. They differ from the general (quasi-)Newton methods in the line search step which is added to ensure that the procedure makes a sufficient progress in the direction to a minimizer, particularly in the case when the initial guess is far away from a solution. Line search means that at a point x the energy functional E is minimized along the (quasi-)Newton vector p, i.e. a positive value is determined such that... 

A numerical procedure should always be tested by using different initial guesses. In particular the robustness, i.e. the influence of small perturbations of the guess to the outcome, should be examined. Since in particular the descent methods behave like quasi-Newton methods in the vicinity of a minimizer, differences between them will become evident only if the initial guesses are chosen outside of the domain of attraction. (Recall, descent methods have just been created for that case ). Therefore, a descent method should also be tested with initial guesses far away from a minimizer. 

By utilizing forces on FES, we can identify the SS and TS stmctures in solution with full optimization with respect to all coordinates of the solute molecules. For example, if we adopt the quasi-Newton method with the following Broyden-Fletcher-Goldfarb-Shanno (BFGS) procedure [26-29] for stractural optimization scheme in the FEG method, the i -F l)-th reactant structure is taken as,... 

In Chapter 4 the Gauss-Newton method for systems described by algebraic equations is developed. The method is illustrated by examples with actual data from the literature. Other methods (indirect, such as Newton, Quasi-Newton, etc., and direct, such as the Luus-Jaakola optimization procedure) are presented in Chapter 5. 

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. 

The SCF wavefunctions from which the electron density is fitted was calculated by means of the GAUSSIAN-90 system of programs [18]. The program QMOLSIM [3] used in the computation of the MQSM allows optimization of the mutual orientation of the two systems studied in order to maximize their similarity by the common steepest-descent, Newton and quasi-Newton algorithms [19]. The DIIS procedure [20] has been also implemented for the steepest-descent optimizations in order to improve the performance of this method. The MQSM used in the optimization procedure are obtained from fitted densities. This speeds the process. The exact MQSM were obtained from the molecular orientation obtained in this optimization procedure. 

---