Quasi-Newton methods updating Hessian matrix

The main difference between the modified Newton and quasi-Newton methods is in the evaluation of the Hessian the modified Newton methods approximate the matrix using local information in the neighborhood of xj the quasi-Newton methods update the matrix using gradient values evaluated at each iteration. 

Quasi-Newton methods update the Hessian by exploiting the information obtained during the search and update either the factorization of the Hessian or its inverse matrix. 

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 = HAq and its analogue H Ag - = Aq - must hold (where Ag - = g - g and similarly for Aq - ). These equations, which have only n components, are obviously insufficient to determine the n(n + l)/2 independent components of the Hessian or its inverse. Therefore, the updating is arbitrary to a certain extent. It is desirable to have an updating scheme that converges to the exact Hessian for a quadratic function, preserves the quasi-Newton conditions obtained in previous steps, and—for minimization—keeps the Hessian positive definite. Updating can be performed on either F or its inverse, the approximate Hessian. In the former case repeated matrix inversion can be avoided. All updates use dyadic products, usually built... 

A brief description of optimizations methods will be given (also see refs. 41-44). In contrast to other fields, in computational chemistry great effort is given to reduce the number of function evaluations since that part of the calculation is so much more time consuming. Since first derivatives are now available for almost all ab initio methods, the discussion will focus on methods where first derivatives are available. The most efficient methods, called variable metric or quasi-Newton methods, require an approximate matrix of second derivatives that can be updated with new information during the course of the optimization. Some of the more common methods have different equations for updating the second derivative matrix (also called the Hessian matrix). 

The idea - on which the quasi-Newton methods are based - is Hessian updating, supposing that the Hessian is available in its approximate form B in x , through the addition of an opportune matrix Q ... 

As explained at the beginning of this section, a quasi-Newton method is obtained when in the classical Newton process the Hessian matrix is approximated by estimate matrices which are computed by an update formula. Subsequently a few results pertaining to the behaviour of convergence of some quasi-Newton methods are presented. Furthermore, the applicability of these methods for locating minimizers and/or saddle points of energy functionals is discussed. 

The computational effort in evaluating the Hessian matrix is significant, and quasi-Newton approximations have been used to reduce this effort. The Wilson-Han-Powell method is an enhancement to successive quadratic programming where the Hessian matrix, (q. ), is replaced by a quasi-Newton update formula such as the BEGS algorithm. Consequently, only first partial derivative information is required, and this is obtained from finite difference approximations of the Lagrangian function. 

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. 

---