Broyden–Fletcher–Goldfarb–Shanno algorithm

Template:Prerequisites header ! Gradient descent | |- ! Newton's method in optimization | Template:Prerequisites footer

In mathematics, the Broyden-Fletcher-Goldfarb-Shanno (BFGS) method is a method to solve an unconstrained nonlinear optimization problem.

The BFGS method is derived from gradient descent. As such, it is a member of a broad class of hill-climbing optimization techniques.

The principal idea of the method is to construct an approximate Hessian matrix of second derivatives of the function to be minimized, by analyzing successive gradient vectors. This approximation of the function's derivatives allows the application of a quasi-Newton fitting method in order to move towards the minimum in the parameter space.

The Hessian matrix does not need to be computed at any stage. However, the method assumes that the function can be locally approximated as a quadratic in the region around the optimum.

Rationale

The search direction $\mathbf {p} _{k}$ at stage k is given by the solution of the analogue of the Newton equation

$B_{k}\mathbf {p} _{k}=-\nabla f(\mathbf {x} _{k})$.

A line search in the direction $\mathbf {p} _{k}$ is then used to find the next point $\mathbf {x} _{k+1}$.

Instead of requiring the full Hessian matrix at the point $\mathbf {x} _{k+1}$ to be computed as $B_{k+1}$, the approximate Hessian at stage k is updated by the addition of two matrices.

$B_{k+1}=B_{k}+U_{k}+V_{k}$

Both $U_{k}$ and $V_{k}$ are rank-one matrices but have different bases. The rank one assumption here means that we may write

$C=\mathbf {a} \mathbf {b} ^{T}$

So equivalently, $U_{k}$ and $V_{k}$ construct a rank-two update matrix which is robust against the scale problem often sufferred in the gradient descent searching.

(as in Broyden's method, the multidimensional analogue of the secant method). The quasi-Newton condition imposed on this update is

$B_{k+1}(\mathbf {x} _{k+1}-\mathbf {x} _{k})=-\left(\nabla f(\mathbf {x} _{k+1})-\nabla f(\mathbf {x} _{k})\right)$.

Algorithm

From an initial guess $\mathbf {x} _{0}$ and an approximate Hessian matrix $B_{0}$ the following steps are repeated until $x$ converges to the solution.

1. Obtain $\mathbf {s} _{k}$ by solving: $B_{k}\mathbf {s} _{k}=-\nabla f(\mathbf {x} _{k})$.
2. Perform a line search to find the optimal $\alpha _{k}$ in the direction found in the first step, then update $\mathbf {x} _{k+1}=\mathbf {x} _{k}+\alpha _{k}\mathbf {s} _{k}$.
3. $\mathbf {y} _{k}=\nabla f(\mathbf {x} _{k+1})-\nabla f(\mathbf {x} _{k})$.
4. $B_{k+1}=B_{k}+(\mathbf {y} _{k}\mathbf {y} _{k}^{\top })/(\mathbf {y} _{k}^{\top }\mathbf {s} _{k})-(B_{k}\mathbf {s} _{k}\mathbf {s} _{k}^{\top }B_{k}^{\top })/(\mathbf {s} _{k}^{\top }B_{k}\mathbf {s} _{k})$.

$f(\mathbf {x} )$ denotes the objective function to be minimized. Convergence can be checked by observing the norm of the gradient, $\left|\nabla f(\mathbf {x} _{k})\right|$. Practically, $B_{0}$ can be initialized with $B_{0}=I$, so that the first step will be equivalent to a gradient descent, but further steps are more and more refined by $B_{k}$, the approximation to the Hessian.

The first step of the algorithm is carried out using an approximate inverse of the matrix $B_{k}$, which is usually obtained efficiently by applying the Sherman–Morrison formula to the fourth line of the algorithm, giving

$B_{k+1}^{-1}=B_{k}^{-1}+(\mathbf {s} _{k}\mathbf {s} _{k}^{\top })(\mathbf {s} _{k}^{\top }\mathbf {y} _{k}+\mathbf {y} _{k}^{\top }B_{k}^{-1}\mathbf {y} _{k})/(\mathbf {s} _{k}^{\top }\mathbf {y} _{k})^{2}-(B_{k}^{-1}\mathbf {y} _{k}\mathbf {s} _{k}^{\top }+\mathbf {s} _{k}\mathbf {y} _{k}^{\top }B_{k}^{-1})/(\mathbf {s} _{k}^{\top }\mathbf {y} _{k})$

Credible intervals or confidence intervals for the solution can be obtained from the inverse of the final Hessian matrix.

Bibliography

• Broyden, C. G. Journal of the Institute of Mathematics and Its Applications 1970, 6, 76-90
• Fletcher, R. Computer Journal 1970, 13, 317
• Goldfarb, D. Mathematics of Computation 1970, 24, 23
• Shanno, D. F. Mathematics of Computation 1970, 24, 647
• Avriel, Mordecai 2003. Nonlinear Programming: Analysis and Methods. Dover Publishing. ISBN 0-486-43227-0.

See also

• L-BFGS method
• Newton's method in optimization