BFGS Algorithm

In numerical optimization, the Broyden-Fletcher-Goldfarb-Shanno, or BFGS, algorithm is an iterative method for solving unconstrained nonlinear optimization problems. Like the related Davidon-Fletcher-Powell method, it determines the descent direction by preconditioning the gradient with curvature information, gradually improving an approximation to the Hessian matrix of the loss function using only gradient evaluations, obtained through a generalized secant method. Because its curvature-matrix updates do not require matrix inversion, its computational complexity is only O(n squared), compared to O(n cubed) for Newton's method; a limited-memory version called L-BFGS is particularly suited to problems with very large numbers of variables. The algorithm is named after Charles George Broyden, Roger Fletcher, Donald Goldfarb and David Shanno, and is an instance of a more general algorithm by John Greenstadt.