HOME

TheInfoList



OR:

In numerical optimization, the Broyden–Fletcher–Goldfarb–Shanno (BFGS) algorithm is an
iterative method In computational mathematics, an iterative method is a mathematical procedure that uses an initial value to generate a sequence of improving approximate solutions for a class of problems, in which the ''n''-th approximation is derived from the pre ...
for solving unconstrained
nonlinear optimization In mathematics, nonlinear programming (NLP) is the process of solving an optimization problem where some of the constraints or the objective function are nonlinear. An optimization problem is one of calculation of the extrema (maxima, minima or st ...
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 In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations ...
is only \mathcal(n^), compared to \mathcal(n^) in Newton's method. Also in common use is
L-BFGS Limited-memory BFGS (L-BFGS or LM-BFGS) is an optimization algorithm in the family of quasi-Newton methods that approximates the Broyden–Fletcher–Goldfarb–Shanno algorithm (BFGS) using a limited amount of computer memory. It is a popular algo ...
, 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 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 for the optimal value \mathbf_0 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, 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 The Symmetric Rank 1 (SR1) method is a quasi-Newton method to update the second derivative (Hessian) based on the derivatives (gradients) calculated at two points. It is a generalization to the secant method for a multidimensional problem. This upda ...
method, which does not guarantee the
positive definiteness In mathematics, positive definiteness is a property of any object to which a bilinear form or a sesquilinear form may be naturally associated, which is positive-definite. See, in particular: * Positive-definite bilinear form * Positive-definite fu ...
. 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

From an initial guess \mathbf_0 and an approximate Hessian matrix B_0 the following steps are repeated as \mathbf_k converges to the solution: # Obtain a direction \mathbf_k by solving B_k \mathbf_k = -\nabla f(\mathbf_k). # Perform a one-dimensional optimization ( line search) to find an acceptable stepsize \alpha_k in the direction found in the first step. If an exact line search is performed, then \alpha_k=\arg \min f(\mathbf_k+\alpha\mathbf_k) . In practice, an inexact line search usually suffices, with an acceptable \alpha_k satisfying Wolfe conditions. # Set \mathbf_k = \alpha_k \mathbf_k and update \mathbf_ = \mathbf_k + \mathbf_k. # \mathbf_k = . # B_ = B_k + \frac - \frac. f(\mathbf) denotes the objective function to be minimized. Convergence can be checked by observing the norm of the gradient, , , \nabla f(\mathbf_k), , . If B_0 is initialized with B_0 = I, 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. The first step of the algorithm is carried out using the inverse of the matrix B_k, which can be obtained efficiently by applying the Sherman–Morrison formula to the step 5 of the algorithm, giving : B_^ = \left(I - \frac \right) B_^ \left(I - \frac \right) + \frac. This can be computed efficiently without temporary matrices, recognizing that B_k^ is symmetric, and that \mathbf_k^ B_k^ \mathbf_k and \mathbf_k^ \mathbf_k are scalars, using an expansion such as : B_^ = B_k^ + \frac - \frac. Therefore, in order to avoid any matrix inversion, the inverse of the Hessian can be approximated instead of the Hessian itself: H_k \overset B_k^. From an initial guess \mathbf_0 and an approximate inverted Hessian matrix H_0 the following steps are repeated as \mathbf_k converges to the solution: # Obtain a direction \mathbf_k by solving \mathbf_k = -H_k \nabla f(\mathbf_k). # Perform a one-dimensional optimization ( line search) to find an acceptable stepsize \alpha_k in the direction found in the first step. If an exact line search is performed, then \alpha_k=\arg \min f(\mathbf_k+\alpha\mathbf_k) . In practice, an inexact line search usually suffices, with an acceptable \alpha_k satisfying Wolfe conditions. # Set \mathbf_k = \alpha_k \mathbf_k and update \mathbf_ = \mathbf_k + \mathbf_k. # \mathbf_k = . # H_ = H_k + \frac - \frac. In statistical estimation problems (such as
maximum likelihood In statistics, maximum likelihood estimation (MLE) is a method of estimating the parameters of an assumed probability distribution, given some observed data. This is achieved by maximizing a likelihood function so that, under the assumed statis ...
or Bayesian inference), credible intervals or confidence intervals for the solution can be estimated from the
inverse Inverse or invert may refer to: Science and mathematics * Inverse (logic), a type of conditional sentence which is an immediate inference made from another conditional sentence * Additive inverse (negation), the inverse of a number that, when a ...
of the final Hessian matrix . However, these quantities are technically defined by the true Hessian matrix, and the BFGS approximation may not converge to the true Hessian matrix.


Notable implementations

Notable open source implementations are: *
ALGLIB ALGLIB is a cross-platform open source numerical analysis and data processing library. It can be used from several programming languages (C++, C#, VB.NET, Python, Delphi). ALGLIB started in 1999 and has a long history of steady development wi ...
implements BFGS and its limited-memory version in C++ and C# *
GNU Octave GNU Octave is a high-level programming language primarily intended for scientific computing and numerical computation. Octave helps in solving linear and nonlinear problems numerically, and for performing other numerical experiments using a lan ...
uses a form of BFGS in its fsolve function, with
trust region In mathematical optimization, a trust region is the subset of the region of the objective function that is approximated using a model function (often a quadratic). If an adequate model of the objective function is found within the trust region, the ...
extensions. * The GSL implements BFGS as gsl_multimin_fdfminimizer_vector_bfgs2. * 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(). * In SciPy, the scipy.optimize.fmin_bfgs function implements BFGS. It is also possible to run BFGS using any of the
L-BFGS Limited-memory BFGS (L-BFGS or LM-BFGS) is an optimization algorithm in the family of quasi-Newton methods that approximates the Broyden–Fletcher–Goldfarb–Shanno algorithm (BFGS) using a limited amount of computer memory. It is a popular algo ...
algorithms by setting the parameter L to a very large number. * In
Julia Julia is usually a feminine given name. It is a Latinate feminine form of the name Julio and Julius. (For further details on etymology, see the Wiktionary entry "Julius".) The given name ''Julia'' had been in use throughout Late Antiquity (e. ...
, th
Optim.jl
package implements BFGS and L-BFGS as a solver option to the optimize() function (among other options). Notable proprietary implementations include: * The large scale nonlinear optimization software
Artelys Knitro Artelys Knitro is a commercial software package for solving large scale nonlinear mathematical optimization problems. KNITRO – (the original solver name) short for "Nonlinear Interior point Trust Region Optimization" (the "K" is silent) – w ...
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.


See also

* BHHH algorithm *
Davidon–Fletcher–Powell formula The Davidon–Fletcher–Powell formula (or DFP; named after William C. Davidon, Roger Fletcher, and Michael J. D. Powell) finds the solution to the secant equation that is closest to the current estimate and satisfies the curvature condition. It ...
* Gradient descent *
L-BFGS Limited-memory BFGS (L-BFGS or LM-BFGS) is an optimization algorithm in the family of quasi-Newton methods that approximates the Broyden–Fletcher–Goldfarb–Shanno algorithm (BFGS) using a limited amount of computer memory. It is a popular algo ...
* Levenberg–Marquardt algorithm *
Nelder–Mead method The Nelder–Mead method (also downhill simplex method, amoeba method, or polytope method) is a numerical method used to find the minimum or maximum of an objective function in a multidimensional space. It is a direct search method (based on ...
*
Pattern search (optimization) Pattern search (also known as direct search, derivative-free search, or black-box search) is a family of numerical optimization methods that does not require a gradient. As a result, it can be used on functions that are not continuous or different ...
*
Quasi-Newton methods Quasi-Newton methods are methods used to either find zeroes or local maxima and minima of functions, as an alternative to Newton's method. They can be used if the Jacobian or Hessian is unavailable or is too expensive to compute at every iteration. ...
*
Symmetric rank-one The Symmetric Rank 1 (SR1) method is a quasi-Newton method to update the second derivative (Hessian) based on the derivatives (gradients) calculated at two points. It is a generalization to the secant method for a multidimensional problem. This upda ...


References


Further reading

* * * * * {{DEFAULTSORT:Broyden-Fletcher-Goldfarb-Shanno algorithm Optimization algorithms and methods