Quasi-Newton method

Quasi - Newton methods are a class of numerical methods for the solution of nonlinear minimization problems. The methods are based on Newton's method, however, the inverse of the Hessian matrix calculated directly, but approach them simply to reduce the computational complexity per iteration.

The first algorithm was the mid-1950s by William Davidon, a physicist at Argonne National Laboratory, developed. The most commonly used algorithms are Broyden - Fletcher- Goldfarb - Shanno ( BFGS ), named after Roger Fletcher, Donald Goldfarb, David F. Shanno, Charles George Broyden and Davidon - Fletcher -Powell (DFP ) ( Fletcher, Davidon and Michael JD Powell ).

Basic algorithm

A doubly differentiable function is approximated with a Taylor expansion up to the second degree.

The derivative of the function q must result in a minimum zero. It follows:

If the Hessian matrix is positive definite, then it is at said zero of the derivative of q actually a minimum of q and this can be approximated iteratively using Newton's method:

The problem here is that the inverse of the Hessian matrix is calculated and these must be positive definite., The quasi -Newton method is replaced by a scalar and a matrix

The derivation of equation above gives reshaped for and

From this it can be deduced:

It is now thought that the Hessian function are approximately the same for and in and concludes:

For choosing a correction term of the form:

The equation can be switched so that

Thus applies

This allows the matrix uniquely determined, but this is not always positive definite with only one correction term.

Davidon - Fletcher- Powell ( DFP)

The matrix is approximated with the matrix, and two correction terms:

Properties

If a quadratic function, the algorithm provides for exact arithmetic after a finite number of iterations, the exact solution. For all other functions