BFGS

The Broyden-Fletcher-Goldfarb-Shanno algorithm, commonly known as BFGS, is an iterative method for unconstrained optimization. It belongs to the family of quasi-Newton methods, which build successive approximations to the inverse Hessian of the objective function to generate search directions. Starting from an initial positive definite inverse Hessian H0 (often the identity), each iteration computes the gradient at the current point and uses it to determine a direction in which to move.

At iteration k, the gradient is g_k and a search direction is p_k = -H_k g_k. A step x_{k+1} = x_k + alpha_k p_k is taken with a line search to ensure sufficient decrease and curvature; alpha_k is chosen to satisfy standard conditions such as Wolfe or strong Wolfe, which helps maintain stability and positive definiteness.

After the step, the gradient change y_k = g_{k+1} - g_k and the step change s_k = x_{k+1} - x_k are formed. The inverse Hessian is updated by the BFGS formula:

H_{k+1} = H_k + (y_k y_k^T)/(y_k^T s_k) - (H_k s_k s_k^T H_k)/(s_k^T H_k s_k).

Equivalently, the Hessian B_k is updated as:

B_{k+1} = B_k - (B_k s_k s_k^T B_k)/(s_k^T B_k s_k) + (y_k y_k^T)/(y_k^T s_k).

If the curvature condition y_k^T s_k > 0 is preserved (often via line search), BFGS maintains a symmetric positive definite approximation, ensuring well-defined, descent directions and typically superlinear convergence on well-behaved functions.

Compared with full Newton methods, BFGS avoids explicit Hessian computations and is robust and efficient in practice. A dense implementation costs about O(n^2) per iteration, with memory O(n^2). For large problems, the limited-memory variant L-BFGS stores a fixed number of vector pairs to achieve O(n) memory. BFGS is widely implemented in scientific libraries. It was developed independently by Broyden, Fletcher, Goldfarb, and Shanno in the 1970s.