Does BFGS find the global minimum?

Not generally. Global conclusions require additional problem assumptions and a relevant guarantee.

Is the Hessian ever computed?

Standard BFGS does not require the exact Hessian; it maintains an approximation or its inverse.

Is fewer iterations always faster?

No. Line searches, gradients and objective evaluations have costs that must be counted.

AI Glossary / Mathematics and optimization / Advanced

Broyden - Fletcher - Goldfarb - Shanno algorithm

Definition

The Broyden - Fletcher - Goldfarb - Shanno algorithm, usually called BFGS, is a quasi-Newton method for minimizing smooth functions. It learns an approximation to curvature from successive positions and gradients, then uses that approximation to choose search directions. Standard BFGS targets unconstrained optimization and does not require explicitly computing the full Hessian of second derivatives.

What it means

A gradient indicates a direction of local increase. Curvature describes how that gradient changes as the variables move. Knowing something about curvature can help an optimizer avoid taking equally scaled steps in directions with very different sensitivities.

Newton's method uses the actual Hessian. BFGS instead updates an approximation using information already gathered during the search. It therefore sits between a simple gradient method and a method that repeatedly forms and factors an exact Hessian. This is a computational tradeoff, not a promise that BFGS always needs fewer evaluations.

How it works

Start with a position x and a symmetric positive-definite curvature approximation B, often a scaled identity matrix. Solve Bp=−g, where g is the current gradient, to obtain a direction. A line search chooses how far to move along p.

After the accepted move, record s=new position−old position and y=new gradient−old gradient. The Hessian-form update is B_new=B+(yyᵀ)/(yᵀs)−(BssᵀB)/(sᵀBs). It satisfies the secant condition B_new s=y, matching the observed gradient change along the latest displacement.

Positive definiteness is preserved when the existing matrix is positive definite and yᵀs is positive. Suitable Wolfe line searches help establish this curvature condition. Implementations may damp, skip or restart updates when numerical or curvature conditions are unsuitable. An equivalent inverse-Hessian update can avoid solving a fresh dense system from scratch.

Three practical examples

1. Statistical fitting: minimize a differentiable negative log-likelihood for a moderate-sized model using reliable gradients.

2. Calibration: adjust continuous parameters of a smooth simulator so that predicted measurements match observations, while accounting for the expense of each simulation.

3. Machine learning: optimize a smooth, moderate-dimensional training objective when deterministic or sufficiently consistent gradient information is available. Very large models may call for a limited-memory alternative or a different optimizer.

Think of it this way

Think of walking down an unfamiliar hillside while remembering how the slope changed after previous steps. Those changes help you estimate which directions steepen quickly and which remain gentle.

The analogy is limited: BFGS updates a precise mathematical matrix, not a mental map of the whole landscape. Its local information cannot reveal every distant valley, and unreliable slope measurements can lead it astray.

Worked example

Consider the original one-dimensional objective f(x)=(x−3)². Its gradient is g(x)=2(x−3). Start at x₀=0 with curvature approximation B₀=1, so g₀=−6 and the search direction is p₀=6.

Suppose the line search accepts step length 0.25. Then x₁=1.5, f drops from 9 to 2.25, and g₁=−3. The displacement is s=1.5 and gradient change is y=3. Their product is 4.5, satisfying the positive-curvature requirement.

In one dimension the update simplifies to B₁=y/s=2: explicitly, 1+9/4.5−2.25/2.25=2. The next direction is −g₁/B₁=1.5. A full step reaches x₂=3, where both objective and gradient are zero.

For this quadratic the learned scalar curvature equals the true second derivative. That exact recovery is a special feature of the example, not a guarantee that a multidimensional BFGS matrix becomes the complete true Hessian. The accepted first step is stipulated for illustration; the arithmetic is hand-checked rather than a software execution trace.

Illustrative case study

Fictional case: an equipment supplier calibrates a smooth response model with twelve continuous parameters. Each objective evaluation runs a deterministic simulation. The team chooses BFGS because it can provide gradients but forming all second derivatives is inconvenient.

An initial run stops after very small parameter changes, yet the gradient remains substantial. Investigation reveals badly mismatched parameter scales. The analysts rescale variables, verify gradients against small perturbations and inspect the termination reason on the next run. They report the achieved fit and evaluation count, without treating the optimizer's name as evidence that the model is correct.

Common misconceptions and mistakes

Do not call BFGS derivative-free. It uses gradients, whether supplied analytically, through automatic differentiation or approximated numerically.

Do not confuse positive-definite approximate curvature with proof that the original objective is convex. A nonconvex objective can still contain multiple local minima and stationary points.

Do not reuse a noisy gradient difference uncritically. Dividing by a tiny or inappropriate curvature product can destabilise an update. Also distinguish full BFGS from L-BFGS and bound-constrained L-BFGS-B: their storage and constraint handling differ.

Business use

The business decision concerns evaluation cost, memory, derivative quality and the kind of answer required. Full BFGS stores a dense matrix, so memory grows quadratically with the number of variables. This can be practical for smaller calibration problems and unsuitable for enormous parameter vectors.

Ask for gradient checks, variable scaling, stopping criteria and the exact termination status. For nonconvex tasks, compare multiple starting points when justified. Constraints must be handled by an appropriate formulation or constrained solver; clipping an unconstrained step does not automatically preserve the standard algorithm's reasoning.

Check your understanding

In the example, what information changes the curvature approximation from 1 to 2?

Answer: Moving by s=1.5 changes the gradient by y=3. The scalar secant relation requires B₁×1.5=3, giving B₁=2.

Related terms

Hessian
Gradient
Line search
quasi-Newton method
Wolfe conditions
secant equation
L-BFGS
numerical conditioning

Learn next

compare gradient descent and BFGS on a two-dimensional quadratic with unequal directional curvature. Then examine how limited-memory BFGS stores recent displacement and gradient-change pairs instead of a full dense matrix.

Sources

Sources: TU Darmstadt's NumaWWW implementation explanation, including the update, secant relation and safeguards, was read: https://numawww.mathematik.tu-darmstadt.de/numerik_en/unres_en/bfgstext.html . Gilbert's primary lecture notes, indexed update formulas consulted; opened PDF had no extractable text: https://www.ecmwf.int/sites/default/files/elibrary/1991/9590-numerical-methods-large-scale-minimization.pdf . The article describes the general method rather than promising one implementation's performance. Example and case are original.

Previous: Brownout (software engineering) Next: Brunner-Munzel test