Limited-memory BFGS

Limited-memory BFGS (L-BFGS or LM-BFGS) is an <a href="/facts/Optimization_(mathematics)/oRn8Iv5I">optimization</a> <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> in the family of <a href="/facts/Quasi-Newton_method/1YX1vMRa">quasi-Newton methods</a> that approximates the <a href="/facts/Broyden%E2%80%93Fletcher%E2%80%93Goldfarb%E2%80%93Shanno_algorithm/aA6KXo6h">Broyden–Fletcher–Goldfarb–Shanno algorithm</a> (BFGS) using a limited amount of <a href="/facts/Computer_memory/hQKVQ51J">computer memory</a>. It is a popular algorithm for parameter estimation in <a href="/facts/Machine_learning/e0w0XJTu">machine learning</a>. The algorithm's target problem is to minimize 
 
 
 
 f
 (
 
 x
 
 )
 
 
 {\displaystyle f(\mathbf {x} )}
 
 over unconstrained values of the real-vector 
 
 
 
 
 x
 
 
 
 {\displaystyle \mathbf {x} }
 
 where 
 
 
 
 f
 
 
 {\displaystyle f}
 
 is a differentiable scalar function.
Like the original BFGS, L-BFGS uses an estimate of the inverse <a href="/facts/Hessian_matrix/RguMNr3m">Hessian matrix</a> to steer its search through variable space, but where BFGS stores a dense 
 
 
 
 n
 ×
 n
 
 
 {\displaystyle n\times n}
 
 approximation to the inverse Hessian (n being the number of variables in the problem), L-BFGS stores only a few vectors that represent the approximation implicitly. Due to its resulting linear memory requirement, the L-BFGS method is particularly well suited for optimization problems with many variables. Instead of the inverse Hessian Hk, L-BFGS maintains a history of the past m updates of the position x and gradient ∇f(x), where generally the history size m can be small (often 
 
 
 
 m
 <
 10
 
 
 {\displaystyle m<10}
 
). These updates are used to implicitly do operations requiring the Hk-vector product.

Limited-memory BFGS open-in-new

Limited-memory BFGS