Optimization quasi-Newton

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. 

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. 

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. 

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. 

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. 

Gill, P.E. and W. Murray, "Quasi-Newton Methods for Unconstrained Optimization", J. Inst. Maths Applies, 9,91-108 (1972). 

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. 

Cite two circumstances in which the use of the simplex method of multivariate unconstrained optimization might be a better choice than a quasi-Newton method. 

Some of the most important variations are the so-called Quasi-Newton Methods, which update the Hessian progressively and therefore economize compute requirements considerably. The most successful scheme for that purpose is the so-called BFGS update. For a detailed overview of the mathematical concepts, see [78, 79] an excellent account of optimization methods in chemistry can be found in [80]. 

For process optimization problems, the sparse approach has been further developed in studies by Kumar and Lucia (1987), Lucia and Kumar (1988), and Lucia and Xu (1990). Here they formulated a large-scale approach that incorporates indefinite quasi-Newton updates and can be tailored to specific process optimization problems. In the last study they also develop a sparse quadratic programming approach based on indefinite matrix factorizations due to Bunch and Parlett (1971). Also, a trust region strategy is substituted for the line search step mentioned above. This approach was successfully applied to the optimization of several complex distillation column models with up to 200 variables. 

Dealing with Z BZ directly has several advantages if n — m is small. Here the matrix is dense and the sufficient conditions for local optimality require that Z BZ be positive definite. Hence, the quasi-Newton update formula can be applied directly to this matrix. Several variations of this basic algorithm... 

Gabay, D. Reduced quasi-Newton methods with feasibility improvement for nonlinearly constrained optimization, Math. Prog. Study 16 18 (1982). 

Kelley, C. T., and Sachs, E. W., Quasi-Newton method and unconstrained optimal control problem, SIAM J. Control [Pg.254]

At this point it may seem as though we can conclude our discussion of optimization methods since we have defined an approach (Newton s method) that will rapidly converge to optimal solutions of multidimensional problems. Unfortunately, Newton s method simply cannot be applied to the DFT problem we set ourselves at the beginning of this section To apply Newton s method to minimize the total energy of a set of atoms in a supercell, E(x), requires calculating the matrix of second derivatives of the form SP E/dxi dxj. Unfortunately, it is very difficult to directly evaluate second derivatives of energy within plane-wave DFT, and most codes do not attempt to perform these calculations. The problem here is not just that Newton s method is numerically inefficient—it just is not practically feasible to evaluate the functions we need to use this method. As a result, we have to look for other approaches to minimize E(x). We will briefly discuss the two numerical methods that are most commonly used for this problem quasi-Newton and... 

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. 

Culver, T. B., and Shoemaker, C. A. (1993). "Optimal control for groundwater remediation by differential dynamic programming with quasi-Newton approximations." Water Resour. Res., 29(4), 823-831. 

Newton s method and quasi-Newton techniques make use of second-order derivative information. Newton s method is computationally expensive because it requires analytical first-and second-order derivative information, as well as matrix inversion. Quasi-Newton methods rely on approximate second-order derivative information (Hessian) or an approximate Hessian inverse. There are a number of variants of these techniques from various researchers most quasi-Newton techniques attempt to find a Hessian matrix that is positive definite and well-conditioned at each iteration. Quasi-Newton methods are recognized as the most powerful unconstrained optimization methods currently available. 

Shanno, D.F., and Kettler, P.C.. "Optimal Conditioning of Quasi-Newton Methods", Math. Comp., 1970, 24, 657-664. 

D. F. Shanno and P. C. Kettler, Math. Comput., 24, 657 (1970). Optimal Conditioning of Quasi-Newton Methods. 

---