Quasi-Newton

Quasi-Newton methods form an interesting class of algorithms that are theoretically closely related to nonlinear CG methods.6 95 96 They are found to perform very well in practice.6 100-102 109 110 QN research has been developing 

Quasi-Newton methods can be viewed as extensions of nonlinear CG methods, in which additional curvature information is used to accelerate convergence. Thus, the required analytic Hessian information, memory, and computational requirements are kept as low as possible, and the main strength of Newton methods—employing curvature information to detect and move away from saddle points efficiently—is retained. 

The basic idea in these methods is building up curvature information progressively. At each step of the algorithm, the current approximation to the Hessian (or inverse Hessian, as we shall see) is updated by using new gradient information. The updated matrix itself is not necessarily stored explicitly, as the updating procedure may be defined compactly in terms of a small set of stored vectors. This economizes memory requirements considerably and increases the appeal to large-scale applications. 

Consider the Taylor expansion for the one-dimensional function f(x) at step k of the method  

This is known as the secant approximation.6 In the extension of this idea to higher dimensions and to the second derivatives, we consider the expansion of the gradient 

---

In these methods, also known as quasi-Newton methods, the approximate Hessian is improved (updated) based on the results in previous steps. For the exact Hessian and a quadratic surface, the quasi-Newton equation and its analogue = Aq must hold (where - g " and... 

Although it was originally developed for locating transition states, the EF algoritlnn is also efficient for minimization and usually perfonns as well as or better than the standard quasi-Newton algorithm. In this case, a single shift parameter is used, and the method is essentially identical to the augmented Hessian method. 

A very pedagogical, highly readable introduction to quasi-Newton optimization methods. It includes a modular system of algoritlnns in pseudo-code which should be easy to translate to popular progrannning languages like C or Fortran. 

I he eigenvector-following (or Hessian mode) method implemented in HyperChem is based on an effieien t quasi-Newton like algorithm for loca tin g tran sitiori states, wh ieh can locate tran si-tion states for alternative rearran gern eri t/dissoeiation reactions, even when startin g from th e wron g regio n on th e poten tial en ergy surface. 

The synchniiuius Iran sit mclhod is com bined with quasi-Newton niethodslo find transition slates. Quasi-.Newlon m etliods are very rohu St an d effieien t in fin din g en ergy in in ini a. Based solely on local information, there is no unique way of moving uphill from eith er rcactari ts or products to reach a specific reaction state, sin ce all direcLion s away from a minimum go uphill. 

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. 

Quantum mechanical calculations are restricted to systems with relatively small numbers of atoms, and so storing the Hessian matrix is not a problem. As the energy calculation is often the most time-consuming part of the calculation, it is desirable that the minimisation method chosen takes as few steps as possible to reach the minimum. For many levels of quantum mechanics theory analytical first derivatives are available. However, analytical second derivatives are only available for a few levels of theory and can be expensive to compute. The quasi-Newton methods are thus particularly popular for quantum mechanical calculations. 

A transition structure is, of course, a maximum on the reaction pathway. One well-defined reaction path is the least energy or intrinsic reaction path (IRC). Quasi-Newton methods oscillate around the IRC path from one iteration to the next. Several researchers have proposed methods for obtaining the IRC path from the quasi-Newton optimization based on this observation. 

If the structure of the intermediate for a very similar reaction is available, use that structure with a quasi-Newton optimization. 

Quadratic synchronous transit followed by quasi-Newton. 

Try quasi-Newton calculations starting from structures that look like what you expect the transition structure to be and that have no symmetry. This is a skill that improves as you become more familiar with the mechanisms involved, but requires some trial-and-error work even for the most experienced researchers. 

Use a pseudo reaction coordinate with one parameter constrained followed by a quasi-Newton optimization. 

The HE, GVB, local MP2, and DFT methods are available, as well as local, gradient-corrected, and hybrid density functionals. The GVB-RCI (restricted configuration interaction) method is available to give correlation and correct bond dissociation with a minimum amount of CPU time. There is also a GVB-DFT calculation available, which is a GVB-SCF calculation with a post-SCF DFT calculation. In addition, GVB-MP2 calculations are possible. Geometry optimizations can be performed with constraints. Both quasi-Newton and QST transition structure finding algorithms are available, as well as the SCRF solvation method. 

Peng, C. and Schlegel, H.B., Combining Synchronous Transit and Quasi-Newton Methods to Find Transition States , Israel Journal of Chemistry, Vol. 33, 449-454 (1993)... 

In HyperChem, two different methods for the location of transition structures are available. Both arethecombinationsofseparate algorithms for the maximum energy search and quasi-Newton methods. The first method is the eigenvector-following method, and the second is the synchronous transit method. 

The steepest descent method is quite old and utilizes the intuitive concept of moving in the direction where the objective function changes the most. However, it is clearly not as efficient as the other three. Conjugate gradient utilizes only first-derivative information, as does steepest descent, but generates improved search directions. Newton s method requires second derivative information but is veiy efficient, while quasi-Newton retains most of the benefits of Newton s method but utilizes only first derivative information. All of these techniques are also used with constrained optimization. 

The development of an SC procedure involves a number of important decisions (1) What variables should be used (2) What equations should be used (3) How should variables be ordered (4) How should equations be ordered (5) How should flexibility in specifications be provided (6) Which derivatives of physical properties should be retained (7) How should equations be linearized (8) If Newton or quasi-Newton hnearization techniques are employed, how should the Jacobian be updated (9) Should corrections to unknowns that are computed at each iteration be modified to dampen or accelerate the solution or be kept within certain bounds (10) What convergence criterion should be applied ... 

It uses a linear or quadratic synchronous transit approach to get closer to the quadratic region of the transition state and then uses a quasi-Newton or eigenvalue-following algorithm to complete the optimization. 

The Synchronous Transit-Guided Quasi-Newton Method(s)... 

---