BFGS method

From Wikipedia, the free encyclopedia

Prerequisites
Gradient descent
Newton's method in optimization

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.

1 Rationale
2 Algorithm
3 Bibliography
4 See also

[edit] 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 )$ .

[edit] Algorithm

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

Obtain $\mathbf{s}_k$ by solving: $B_k \mathbf{s}_k = -\nabla f(\mathbf{x}_k)$ .
Perform a line search to find the optimium $α k$ in the direction found in the first step, then update $\mathbf{x}_{k+1} = \mathbf{x}_k + \alpha_k\mathbf{s}_k$ .
$\mathbf{y}_k = \nabla f(\mathbf{x}_{k+1}) - \nabla f(\mathbf{x}_k)$ .
$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) / (\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$ , then the first step will be equivalent to a gradient descent, but further steps are more and more refined by $B$ , the approximation to the Hessian.

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

[edit] 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.