Nonlinear Optimization Using a Broyden Fletcher Goldfarb Shanno (BFGS) Algorithm

The Broyden Fletcher Goldfarb Shanno (BFGS) algorithm is a popular quasi Newton algorithm.

The quasi Newton algorithms are based on Newton's method for optimization and use an approximation of the Hessian matrix based on past positions and functional values rather than an analytically or numerically calculated one.

Quasi Newton algorithms use the same update formula as Newton's method.

The Hessian matrix for Newton's method is shown below.  In a quasi Newton algorithm, the Hessian matrix is not directly calculated, but rather is approximated based on the current and previous positions, gradients, and estimates of the Hessian matrix.

Gradient

BFGS Update Formula

A is the approximate inverse Hessian.

Example

Starting at x₁ = 3, x₂ = 3.

Iteration 1

Iteration 2

Iteration 3

Iteration 4