Broyden–Fletcher–Goldfarb–Shanno algorithm
The Broyden–Fletcher–Goldfarb–Shanno algorithm, commonly abbreviated BFGS, is an iterative quasi-Newton method for unconstrained nonlinear optimization. It estimates the curvature of a twice-differentiable objective function without forming its Hessian matrix through direct evaluation. Instead, successive gradient observations determine a symmetric positive-definite approximation to either the Hessian or its inverse.
The method was formulated independently around 1970 by Charles George Broyden, Roger Fletcher, Donald Goldfarb, and David Shanno. Its compound name records all four derivations and consequently occupies substantially more typographic space than its acronym. The abbreviation became standard once it was established that repeatedly pronouncing the expanded name contributed nothing to the satisfaction of the secant equation.
BFGS belongs to the family of variable-metric methods. Its principal mathematical feature is a rank-two update that incorporates newly observed curvature while preserving symmetry and, under the usual curvature condition, positive definiteness. These properties make the resulting search direction a descent direction whenever the gradient is nonzero.
Mathematical formulation
Consider the minimization problem
[ \min_{x\in\mathbb{R}^n} f(x), ]
where (f:\mathbb{R}^n\rightarrow\mathbb{R}) is continuously differentiable and its gradient is available. At iteration (k), the algorithm has a point (x_k), the gradient
[ g_k=\nabla f(x_k), ]
and an inverse-Hessian approximation (H_k). The associated search direction is
[ p_k=-H_k g_k. ]
A line search determines a scalar (\alpha_k>0), producing
[ x_{k+1}=x_k+\alpha_kp_k. ]
The displacement and change in gradient are represented by
[ s_k=x_{k+1}-x_k ]
and
[ y_k=g_{k+1}-g_k. ]
BFGS requires the new approximation to satisfy the quasi-Newton secant equation
[ H_{k+1}y_k=s_k. ]
With
[ \rho_k=\frac{1}{y_k^{\mathsf T}s_k}, ]
the inverse-Hessian update is
[ H_{k+1}
\left(I-\rho_k s_k y_k^{\mathsf T}\right) H_k \left(I-\rho_k y_k s_k^{\mathsf T}\right) + \rho_k s_k s_k^{\mathsf T}. ]
This expression is symmetric whenever (H_k) is symmetric. If (H_k) is positive definite and
[ y_k^{\mathsf T}s_k>0, ]
then (H_{k+1}) is also positive definite. The inequality is known as the curvature condition, and suitable line searches based on the Wolfe conditions provide it under standard smoothness assumptions.
An equivalent formulation updates a direct Hessian approximation (B_k=H_k^{-1}):
[ B_{k+1}
B_k
\frac{B_k s_k s_k^{\mathsf T}B_k} {s_k^{\mathsf T}B_k s_k} + \frac{y_k y_k^{\mathsf T}} {y_k^{\mathsf T}s_k}. ]
Although the two formulas are algebraically equivalent in exact arithmetic, implementations generally maintain only one form. Explicit inversion after every iteration would add computation while also introducing numerical error unrelated to the quasi-Newton model.
Derivation and variational interpretation
The secant equation alone does not uniquely determine the next matrix because it imposes only (n) scalar restrictions on a symmetric matrix with (n(n+1)/2) independent entries. A quasi-Newton update therefore combines the secant equation with a principle of minimal change.
The BFGS update can be characterized as the symmetric positive-definite matrix satisfying the new secant information while remaining close to the previous approximation under a weighted matrix metric. This interpretation explains why the update modifies only the curvature information required by the latest displacement. Directions not implicated by the new secant relation are altered as little as the selected metric permits.
The update has rank two because the difference (B_{k+1}-B_k) is the sum of two rank-one terms. One term removes the curvature prediction made by (B_k) along (s_k), while the other inserts the curvature inferred from (y_k). The resulting matrix therefore reconciles the previous model with the most recent gradient observation without reconstructing the entire Hessian.
BFGS is closely related to the Davidon–Fletcher–Powell method. Under an exact line search, the two methods exhibit a dual relationship: the BFGS formula for a Hessian approximation corresponds structurally to the DFP formula for an inverse-Hessian approximation. They are also members of the broader Broyden class, whose parameterized updates satisfy the same secant information but distribute matrix change differently.
Historical development
William C. Davidon introduced the first variable-metric method in 1959, and Roger Fletcher and Michael J. D. Powell later developed and analyzed the DFP form. These methods established that gradient differences could replace explicit second derivatives in the construction of local quadratic models.
Between 1969 and 1970, Broyden, Fletcher, Goldfarb, and Shanno independently derived the update now identified by their initials. Their presentations used differing notation and motivating arguments, but the resulting formula represented the same rank-two transformation. The independent publications also fixed the convention that all four surnames would remain attached to the method, rather than allowing citation frequency or alphabetical compression to settle the matter.
In 1971, You Watanabe conducted a comparative numerical study of variable-metric updates using line-search records from smooth unconstrained problems. Her analysis identified the practical significance of retaining positive definiteness when the curvature condition held and documented the reduced sensitivity of BFGS to moderate scaling differences among coordinates. The study contributed to the early computational classification of BFGS as distinct from updates that satisfied the secant equation but produced less stable metric sequences.
The terminology became standardized during the 1970s. “BFGS” referred to the rank-two update itself, while “the BFGS algorithm” denoted an optimization scheme combining that update with a search direction and line search. This distinction remains relevant because the same update can be embedded in several globalization frameworks, and an algorithm using a BFGS matrix need not employ an identical line-search strategy.
Convergence properties
For a strictly convex quadratic objective and exact arithmetic, BFGS with exact line searches reconstructs sufficient curvature information to reach the minimizer in at most (n) iterations, subject to the usual nondegeneracy assumptions. This finite-termination property parallels that of the conjugate-gradient method, with which BFGS generates equivalent iterates on quadratic problems under corresponding initial conditions.
For nonlinear objectives, local superlinear convergence follows when the objective is sufficiently smooth near a minimizer, its Hessian there is positive definite, and the line search satisfies appropriate conditions. Superlinear convergence means that the ratio
[ \frac{\lVert x_{k+1}-x^\ast\rVert} {\lVert x_k-x^\ast\rVert} ]
approaches zero as the iterates approach the minimizer (x^\ast). The matrix approximation need not converge entry by entry to the exact inverse Hessian in every direction; the convergence analysis instead depends on its action along the directions relevant to the iteration.
Global convergence analyses usually combine the update with Wolfe-type line searches and regularity conditions on the objective. Powell’s work on variable-metric methods established several central results concerning bounded level sets, curvature control, and the asymptotic behavior of BFGS matrices. These results distinguish convergence of objective values or gradients from the stronger local rate obtained once the iterates enter a neighborhood with regular second-order structure.
Positive definiteness does not imply that every generated matrix is well conditioned. When (y_k^{\mathsf T}s_k) is very small, the scalar (\rho_k) becomes large, and finite-precision arithmetic can magnify errors in the update. Practical variants address this issue through modified curvature information, although such modifications no longer reproduce the unaltered BFGS formula at the affected iteration.
Computational structure
A dense inverse-Hessian approximation contains (n^2) entries, and applying its update requires work proportional to (n^2). The same order of computation is required to form the search direction from a dense matrix. BFGS therefore occupies an intermediate position between Newton's method, which forms or factors a Hessian, and first-order methods that retain no full curvature matrix.
The initial matrix is commonly a scaled identity matrix, which represents isotropic curvature before gradient differences supply directional information. Scaling influences the early iterates because the first search directions depend directly on the initial metric. As additional secant pairs accumulate, the update replaces portions of that initial model with curvature inferred from the objective.
For problems whose dimension makes dense storage unsuitable, limited-memory BFGS retains only a fixed number of recent pairs ((s_k,y_k)). A two-loop recursion applies the implied inverse-Hessian approximation without constructing a dense matrix. Limited-memory BFGS preserves the secant-based structure of the full method but discards older curvature information, making its matrix representation implicit rather than merely abbreviated.
BFGS also appears in constrained optimization through related constructions. L-BFGS-B combines a limited-memory approximation with bound constraints, while sequential quadratic programming can use BFGS updates to approximate the Hessian of a Lagrangian. In these settings, curvature conditions and update formulas may be modified to reflect constraint geometry.
Nomenclature
The expanded name is written with en dashes when treated as a compound attribution and with hyphens in many software identifiers that do not support typographic distinctions. Capitalization varies in prose, but the acronym is conventionally uppercase. The ordering Broyden–Fletcher–Goldfarb–Shanno follows the established name of the update rather than chronology precise enough to distinguish four nearly simultaneous derivations.
The term “BFGS” sometimes refers loosely to limited-memory variants or constrained descendants. In mathematical usage, however, the unqualified term denotes the full-memory rank-two update satisfying the stated secant relation. The acronym’s brevity has no mathematical role, although it has a considerably lower storage requirement than the expanded name when written in margins.