Broyden–Fletcher–Goldfarb–Shanno algorithm

In numerical optimization, the Broyden–Fletcher–Goldfarb–Shanno (BFGS) algorithm is an iterative method for solving unconstrained nonlinear optimization problems. Like the related Davidon–Fletcher–Powell method, BFGS determines the descent direction by preconditioning the gradient with curvature information. It does so by gradually improving an approximation to the Hessian matrix of the loss function, obtained only from gradient evaluations (or approximate gradient evaluations) via a generalized secant method.

Since the updates of the BFGS curvature matrix do not require matrix inversion, its computational complexity is only $\mathcal(n^)$, compared to $\mathcal(n^)$ in Newton's method. Also in common use is L-BFGS, which is a limited-memory version of BFGS that is particularly suited to problems with very large numbers of variables (e.g., >1000). The BFGS-B variant handles simple box constraints. The BFGS matrix also admits a compact representation, which makes it better suited for large constrained problems.

The algorithm is named after Charles George Broyden, Roger Fletcher, Donald Goldfarb and David Shanno.

Rationale

The optimization problem is to minimize $f(\mathbf)$, where $\mathbf$ is a vector in $\mathbb^n$, and $f$ is a differentiable scalar function. There are no constraints on the values that $\mathbf$ can take.

The algorithm begins at an initial estimate $\mathbf_0$ for the optimal value and proceeds iteratively to get a better estimate at each stage.

The search direction p_''k'' at stage ''k'' is given by the solution of the analogue of the Newton equation:

:$B_k \mathbf_k = -\nabla f(\mathbf_k),$

where $B_k$ is an approximation to the Hessian matrix at $\mathbf_k$, which is updated iteratively at each stage, and $\nabla f(\mathbf_k)$ is the gradient of the function evaluated at x_''k''. A line search in the direction p_''k'' is then used to find the next point x_''k''+1 by minimizing $f(\mathbf_k + \gamma\mathbf_k)$ over the scalar $\gamma > 0.$

The quasi-Newton condition imposed on the update of $B_k$ is

:$B_ (\mathbf_ - \mathbf_k) = \nabla f(\mathbf_) - \nabla f(\mathbf_k).$

Let $\mathbf_k = \nabla f(\mathbf_) - \nabla f(\mathbf_k)$ and $\mathbf_k = \mathbf_ - \mathbf_k$, then $B_$ satisfies

:$B_ \mathbf_k = \mathbf_k$,

which is the secant equation.

The curvature condition $\mathbf_k^\top \mathbf_k > 0$ should be satisfied for $B_$ to be positive definite, which can be verified by pre-multiplying the secant equation with $\mathbf_k^T$. If the function is not strongly convex, then the condition has to be enforced explicitly e.g. by finding a point x_''k''+1 satisfying the Wolfe conditions, which entail the curvature condition, using line search.

Instead of requiring the full Hessian matrix at the point $\mathbf_$ to be computed as $B_$, the approximate Hessian at stage ''k'' is updated by the addition of two matrices:

:$B_ = B_k + U_k + V_k.$

Both $U_k$ and $V_k$ are symmetric rank-one matrices, but their sum is a rank-two update matrix. BFGS and DFP updating matrix both differ from its predecessor by a rank-two matrix. Another simpler rank-one method is known as symmetric rank-one method, which does not guarantee the positive definiteness. In order to maintain the symmetry and positive definiteness of $B_$, the update form can be chosen as $B_ = B_k + \alpha\mathbf\mathbf^\top + \beta\mathbf\mathbf^\top$. Imposing the secant condition, $B_ \mathbf_k = \mathbf_k$. Choosing $\mathbf = \mathbf_k$ and $\mathbf = B_k \mathbf_k$, we can obtain:

:$\alpha = \frac,$
:$\beta = -\frac.$

Finally, we substitute $\alpha$ and $\beta$ into $B_ = B_k + \alpha\mathbf\mathbf^\top + \beta\mathbf\mathbf^\top$ and get the update equation of $B_$:

:$B_ = B_k + \frac - \frac.$

Algorithm

Consider the following unconstrained optimization problem
line search