# Broyden–Fletcher–Goldfarb–Shanno algorithm

(Redirected from BFGS method)

In numerical optimization, the Broyden–Fletcher–Goldfarb–Shanno (BFGS) algorithm is an iterative method for solving unconstrained nonlinear optimization problems.[1] 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.[2]

Since the updates of the BFGS curvature matrix do not require matrix inversion, its computational complexity is only ${\displaystyle {\mathcal {O}}(n^{2})}$, compared to ${\displaystyle {\mathcal {O}}(n^{3})}$ 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.[3]

The algorithm is named after Charles George Broyden, Roger Fletcher, Donald Goldfarb and David Shanno.[4][5][6][7]

## Rationale

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

The algorithm begins at an initial estimate for the optimal value ${\displaystyle \mathbf {x} _{0}}$ and proceeds iteratively to get a better estimate at each stage.

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

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

where ${\displaystyle B_{k}}$ is an approximation to the Hessian matrix, which is updated iteratively at each stage, and ${\displaystyle \nabla f(\mathbf {x} _{k})}$ is the gradient of the function evaluated at xk. A line search in the direction pk is then used to find the next point xk+1 by minimizing ${\displaystyle f(\mathbf {x} _{k}+\gamma \mathbf {p} _{k})}$ over the scalar ${\displaystyle \gamma >0.}$

The quasi-Newton condition imposed on the update of ${\displaystyle B_{k}}$ is

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

Let ${\displaystyle \mathbf {y} _{k}=\nabla f(\mathbf {x} _{k+1})-\nabla f(\mathbf {x} _{k})}$ and ${\displaystyle \mathbf {s} _{k}=\mathbf {x} _{k+1}-\mathbf {x} _{k}}$, then ${\displaystyle B_{k+1}}$ satisfies

${\displaystyle B_{k+1}\mathbf {s} _{k}=\mathbf {y} _{k}}$,

which is the secant equation.

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

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

${\displaystyle B_{k+1}=B_{k}+U_{k}+V_{k}.}$

Both ${\displaystyle U_{k}}$ and ${\displaystyle 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 ${\displaystyle B_{k+1}}$, the update form can be chosen as ${\displaystyle B_{k+1}=B_{k}+\alpha \mathbf {u} \mathbf {u} ^{\top }+\beta \mathbf {v} \mathbf {v} ^{\top }}$. Imposing the secant condition, ${\displaystyle B_{k+1}\mathbf {s} _{k}=\mathbf {y} _{k}}$. Choosing ${\displaystyle \mathbf {u} =\mathbf {y} _{k}}$ and ${\displaystyle \mathbf {v} =B_{k}\mathbf {s} _{k}}$, we can obtain:[8]

${\displaystyle \alpha ={\frac {1}{\mathbf {y} _{k}^{T}\mathbf {s} _{k}}},}$
${\displaystyle \beta =-{\frac {1}{\mathbf {s} _{k}^{T}B_{k}\mathbf {s} _{k}}}.}$

Finally, we substitute ${\displaystyle \alpha }$ and ${\displaystyle \beta }$ into ${\displaystyle B_{k+1}=B_{k}+\alpha \mathbf {u} \mathbf {u} ^{\top }+\beta \mathbf {v} \mathbf {v} ^{\top }}$ and get the update equation of ${\displaystyle B_{k+1}}$:

${\displaystyle B_{k+1}=B_{k}+{\frac {\mathbf {y} _{k}\mathbf {y} _{k}^{\mathrm {T} }}{\mathbf {y} _{k}^{\mathrm {T} }\mathbf {s} _{k}}}-{\frac {B_{k}\mathbf {s} _{k}\mathbf {s} _{k}^{\mathrm {T} }B_{k}^{\mathrm {T} }}{\mathbf {s} _{k}^{\mathrm {T} }B_{k}\mathbf {s} _{k}}}.}$

## Algorithm

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

1. Obtain a direction ${\displaystyle \mathbf {p} _{k}}$ by solving ${\displaystyle B_{k}\mathbf {p} _{k}=-\nabla f(\mathbf {x} _{k})}$.
2. Perform a one-dimensional optimization (line search) to find an acceptable stepsize ${\displaystyle \alpha _{k}}$ in the direction found in the first step. If an exact line search is performed, then ${\displaystyle \alpha _{k}=\arg \min f(\mathbf {x} _{k}+\alpha \mathbf {p} _{k})}$ . In practice, an inexact line search usually suffices, with an acceptable ${\displaystyle \alpha _{k}}$ satisfying Wolfe conditions.
3. Set ${\displaystyle \mathbf {s} _{k}=\alpha _{k}\mathbf {p} _{k}}$ and update ${\displaystyle \mathbf {x} _{k+1}=\mathbf {x} _{k}+\mathbf {s} _{k}}$.
4. ${\displaystyle \mathbf {y} _{k}={\nabla f(\mathbf {x} _{k+1})-\nabla f(\mathbf {x} _{k})}}$.
5. ${\displaystyle B_{k+1}=B_{k}+{\frac {\mathbf {y} _{k}\mathbf {y} _{k}^{\mathrm {T} }}{\mathbf {y} _{k}^{\mathrm {T} }\mathbf {s} _{k}}}-{\frac {B_{k}\mathbf {s} _{k}\mathbf {s} _{k}^{\mathrm {T} }B_{k}^{\mathrm {T} }}{\mathbf {s} _{k}^{\mathrm {T} }B_{k}\mathbf {s} _{k}}}}$.

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

The first step of the algorithm is carried out using the inverse of the matrix ${\displaystyle B_{k}}$, which can be obtained efficiently by applying the Sherman–Morrison formula to the step 5 of the algorithm, giving

${\displaystyle B_{k+1}^{-1}=\left(I-{\frac {\mathbf {s} _{k}\mathbf {y} _{k}^{T}}{\mathbf {y} _{k}^{T}\mathbf {s} _{k}}}\right)B_{k}^{-1}\left(I-{\frac {\mathbf {y} _{k}\mathbf {s} _{k}^{T}}{\mathbf {y} _{k}^{T}\mathbf {s} _{k}}}\right)+{\frac {\mathbf {s} _{k}\mathbf {s} _{k}^{T}}{\mathbf {y} _{k}^{T}\mathbf {s} _{k}}}.}$

This can be computed efficiently without temporary matrices, recognizing that ${\displaystyle B_{k}^{-1}}$ is symmetric, and that ${\displaystyle \mathbf {y} _{k}^{\mathrm {T} }B_{k}^{-1}\mathbf {y} _{k}}$ and ${\displaystyle \mathbf {s} _{k}^{\mathrm {T} }\mathbf {y} _{k}}$ are scalars, using an expansion such as

${\displaystyle B_{k+1}^{-1}=B_{k}^{-1}+{\frac {(\mathbf {s} _{k}^{\mathrm {T} }\mathbf {y} _{k}+\mathbf {y} _{k}^{\mathrm {T} }B_{k}^{-1}\mathbf {y} _{k})(\mathbf {s} _{k}\mathbf {s} _{k}^{\mathrm {T} })}{(\mathbf {s} _{k}^{\mathrm {T} }\mathbf {y} _{k})^{2}}}-{\frac {B_{k}^{-1}\mathbf {y} _{k}\mathbf {s} _{k}^{\mathrm {T} }+\mathbf {s} _{k}\mathbf {y} _{k}^{\mathrm {T} }B_{k}^{-1}}{\mathbf {s} _{k}^{\mathrm {T} }\mathbf {y} _{k}}}.}$

Therefore, in order to avoid any matrix inversion, the inverse of the Hessian can be approximated instead of the Hessian itself: ${\displaystyle H_{k}{\overset {\operatorname {def} }{=}}B_{k}^{-1}.}$[9]

From an initial guess ${\displaystyle \mathbf {x} _{0}}$ and an approximate inverted Hessian matrix ${\displaystyle H_{0}}$ the following steps are repeated as ${\displaystyle \mathbf {x} _{k}}$ converges to the solution:

1. Obtain a direction ${\displaystyle \mathbf {p} _{k}}$ by solving ${\displaystyle \mathbf {p} _{k}=-H_{k}\nabla f(\mathbf {x} _{k})}$.
2. Perform a one-dimensional optimization (line search) to find an acceptable stepsize ${\displaystyle \alpha _{k}}$ in the direction found in the first step. If an exact line search is performed, then ${\displaystyle \alpha _{k}=\arg \min f(\mathbf {x} _{k}+\alpha \mathbf {p} _{k})}$ . In practice, an inexact line search usually suffices, with an acceptable ${\displaystyle \alpha _{k}}$ satisfying Wolfe conditions.
3. Set ${\displaystyle \mathbf {s} _{k}=\alpha _{k}\mathbf {p} _{k}}$ and update ${\displaystyle \mathbf {x} _{k+1}=\mathbf {x} _{k}+\mathbf {s} _{k}}$.
4. ${\displaystyle \mathbf {y} _{k}={\nabla f(\mathbf {x} _{k+1})-\nabla f(\mathbf {x} _{k})}}$.
5. ${\displaystyle H_{k+1}=H_{k}+{\frac {(\mathbf {s} _{k}^{\mathrm {T} }\mathbf {y} _{k}+\mathbf {y} _{k}^{\mathrm {T} }H_{k}\mathbf {y} _{k})(\mathbf {s} _{k}\mathbf {s} _{k}^{\mathrm {T} })}{(\mathbf {s} _{k}^{\mathrm {T} }\mathbf {y} _{k})^{2}}}-{\frac {H_{k}\mathbf {y} _{k}\mathbf {s} _{k}^{\mathrm {T} }+\mathbf {s} _{k}\mathbf {y} _{k}^{\mathrm {T} }H_{k}}{\mathbf {s} _{k}^{\mathrm {T} }\mathbf {y} _{k}}}}$.

In statistical estimation problems (such as maximum likelihood or Bayesian inference), credible intervals or confidence intervals for the solution can be estimated from the inverse of the final Hessian matrix[citation needed]. However, these quantities are technically defined by the true Hessian matrix, and the BFGS approximation may not converge to the true Hessian matrix.[10]

## Notable implementations

Notable open source implementations are:

• ALGLIB implements BFGS and its limited-memory version in C++ and C#
• GNU Octave uses a form of BFGS in its fsolve function, with trust region extensions.
• The GSL implements BFGS as gsl_multimin_fdfminimizer_vector_bfgs2.[11]
• In R, the BFGS algorithm (and the L-BFGS-B version that allows box constraints) is implemented as an option of the base function optim().[12]
• In SciPy, the scipy.optimize.fmin_bfgs function implements BFGS.[13] It is also possible to run BFGS using any of the L-BFGS algorithms by setting the parameter L to a very large number.
• In Julia, the Optim.jl package implements BFGS and L-BFGS as a solver option to the optimize() function (among other options).[14]

Notable proprietary implementations include:

• The large scale nonlinear optimization software Artelys Knitro implements, among others, both BFGS and L-BFGS algorithms.
• In the MATLAB Optimization Toolbox, the fminunc function uses BFGS with cubic line search when the problem size is set to "medium scale."
• Mathematica includes BFGS.

## References

1. ^ Fletcher, Roger (1987), Practical Methods of Optimization (2nd ed.), New York: John Wiley & Sons, ISBN 978-0-471-91547-8
2. ^ Dennis, J. E. Jr.; Schnabel, Robert B. (1983), "Secant Methods for Unconstrained Minimization", Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Englewood Cliffs, NJ: Prentice-Hall, pp. 194–215, ISBN 0-13-627216-9
3. ^ Byrd, Richard H.; Lu, Peihuang; Nocedal, Jorge; Zhu, Ciyou (1995), "A Limited Memory Algorithm for Bound Constrained Optimization", SIAM Journal on Scientific Computing, 16 (5): 1190–1208, CiteSeerX 10.1.1.645.5814, doi:10.1137/0916069
4. ^ Broyden, C. G. (1970), "The convergence of a class of double-rank minimization algorithms", Journal of the Institute of Mathematics and Its Applications, 6: 76–90, doi:10.1093/imamat/6.1.76
5. ^ Fletcher, R. (1970), "A New Approach to Variable Metric Algorithms", Computer Journal, 13 (3): 317–322, doi:10.1093/comjnl/13.3.317
6. ^ Goldfarb, D. (1970), "A Family of Variable Metric Updates Derived by Variational Means", Mathematics of Computation, 24 (109): 23–26, doi:10.1090/S0025-5718-1970-0258249-6
7. ^ Shanno, David F. (July 1970), "Conditioning of quasi-Newton methods for function minimization", Mathematics of Computation, 24 (111): 647–656, doi:10.1090/S0025-5718-1970-0274029-X, MR 0274029
8. ^ Fletcher, Roger (1987), Practical methods of optimization (2nd ed.), New York: John Wiley & Sons, ISBN 978-0-471-91547-8
9. ^ Nocedal, Jorge; Wright, Stephen J. (2006), Numerical Optimization (2nd ed.), Berlin, New York: Springer-Verlag, ISBN 978-0-387-30303-1
10. ^ Ge, Ren-pu; Powell, M. J. D. (1983). "The Convergence of Variable Metric Matrices in Unconstrained Optimization". Mathematical Programming. 27 (2). 123. doi:10.1007/BF02591941. S2CID 8113073.
11. ^ "GNU Scientific Library — GSL 2.6 documentation". www.gnu.org. Retrieved 2020-11-22.
12. ^ "R: General-purpose Optimization". stat.ethz.ch. Retrieved 2020-11-22.
13. ^ "scipy.optimize.fmin_bfgs — SciPy v1.5.4 Reference Guide". docs.scipy.org. Retrieved 2020-11-22.
14. ^ "Optim.jl Configurable options". julianlsolvers.