BFGS

The Broyden-Fletcher-Goldfarb-Shanno update maintains a positive-definite inverse-Hessian approximation for fast, robust unconstrained optimization.

A self-correcting Hessian estimate

BFGS is the most widely used quasi-Newton method. It updates an approximation of the inverse Hessian directly, so each step needs only a matrix-vector product rather than solving a linear system. The update is rank-two, preserves symmetry and positive definiteness, and tends to correct earlier approximation errors as iterations proceed.

The update formula

With s = x_{k+1} - x_k and y = grad_{k+1} - grad_k, and rho = 1/(y dot s), the inverse Hessian estimate updates as H_{k+1} = (I - rho s y^T) H_k (I - rho y s^T) + rho s s^T. This satisfies the secant condition H_{k+1} y = s and keeps H positive definite whenever the curvature condition y dot s > 0 holds.

The full step

• Compute the search direction d = -H_k grad_k.
• Line search along d for a step satisfying the Wolfe conditions.
• Update x, then update H_k using the s and y from the step.

Why the curvature condition matters

Positive definiteness of H, which guarantees d is a descent direction, requires y dot s > 0. A line search satisfying the strong Wolfe conditions automatically ensures this, which is why BFGS is almost always paired with a proper line search rather than a fixed step.

Strengths and limits

BFGS converges superlinearly, needs no Hessian, and is remarkably robust across smooth problems. Its drawback is storing and updating a dense n-by-n matrix, costing O(n^2) memory. For problems with thousands or millions of variables, the limited-memory variant L-BFGS is used instead.

from scipy.optimize import minimize
res = minimize(rosen, x0, method='BFGS', jac=rosen_der)
print(res.x, res.nit)

BFGS is a dependable default for smooth, medium-dimensional engineering optimization where gradients are available.