Restricted-memory BFGS (L-BFGS or LM-BFGS) is an optimization algorithm in the collection of quasi-Newton methods that approximates the Broyden-Fletcher-Goldfarb-Shanno algorithm (BFGS) using a restricted quantity of pc memory. It is a popular algorithm for parameter estimation in machine studying. Hessian (n being the variety of variables in the problem), L-BFGS stores only some vectors that characterize the approximation implicitly. Due to its ensuing linear memory requirement, MemoryWave Official the L-BFGS methodology is particularly properly suited to optimization problems with many variables. The 2-loop recursion formula is broadly utilized by unconstrained optimizers attributable to its efficiency in multiplying by the inverse Hessian. Nonetheless, it does not permit for the express formation of both the direct or inverse Hessian and is incompatible with non-field constraints. An alternate strategy is the compact illustration, which entails a low-rank representation for the direct and/or inverse Hessian. This represents the Hessian as a sum of a diagonal matrix and a low-rank update. Such a representation enables the use of L-BFGS in constrained settings, for example, as part of the SQP method.

Since BFGS (and therefore L-BFGS) is designed to reduce easy features without constraints, the L-BFGS algorithm should be modified to handle capabilities that embody non-differentiable elements or constraints. A popular class of modifications are called energetic-set methods, based mostly on the idea of the energetic set. The thought is that when restricted to a small neighborhood of the current iterate, the operate and constraints might be simplified. The L-BFGS-B algorithm extends L-BFGS to handle easy box constraints (aka certain constraints) on variables; that is, constraints of the kind li ≤ xi ≤ ui the place li and ui are per-variable fixed lower and upper bounds, respectively (for every xi, either or both bounds may be omitted). The method works by figuring out fastened and free variables at each step (utilizing a simple gradient methodology), after which utilizing the L-BFGS method on the free variables solely to get higher accuracy, and then repeating the method. The strategy is an active-set kind methodology: at every iterate, it estimates the sign of each component of the variable, and restricts the following step to have the identical sign.

L-BFGS. After an L-BFGS step, the strategy permits some variables to change sign, and repeats the method. Schraudolph et al. current an internet approximation to each BFGS and L-BFGS. Just like stochastic gradient descent, this can be utilized to reduce the computational complexity by evaluating the error perform and gradient on a randomly drawn subset of the general dataset in each iteration. BFGS (O-BFGS) is just not necessarily convergent. R's optim common-purpose optimizer routine uses the L-BFGS-B technique. SciPy's optimization module's minimize method additionally contains an option to make use of L-BFGS-B. A reference implementation in Fortran 77 (and with a Fortran ninety interface). This version, in addition to older variations, has been transformed to many different languages. Liu, D. C.; Nocedal, J. (1989). "On the Limited Memory Methodology for big Scale Optimization". Malouf, Robert (2002). "A comparison of algorithms for max entropy parameter estimation". Proceedings of the Sixth Convention on Natural Language Learning (CoNLL-2002).

Andrew, MemoryWave Official Galen; Gao, Jianfeng (2007). "Scalable coaching of L₁-regularized log-linear models". Proceedings of the twenty fourth Worldwide Conference on Machine Studying. Matthies, H.; Strang, G. (1979). "The answer of non linear finite component equations". Worldwide Journal for Numerical Methods in Engineering. 14 (11): 1613-1626. Bibcode:1979IJNME..14.1613M. Nocedal, J. (1980). "Updating Quasi-Newton Matrices with Restricted Storage". Byrd, R. H.; Nocedal, J.; Schnabel, R. B. (1994). "Representations of Quasi-Newton Matrices and their use in Limited Memory Methods". Mathematical Programming. Sixty three (4): 129-156. doi:10.1007/BF01582063. Byrd, R. H.; Lu, P.; Nocedal, J.; Zhu, C. (1995). "A Limited Memory Algorithm for Bound Constrained Optimization". SIAM J. Sci. Comput. Zhu, C.; Byrd, Richard H.; Lu, Peihuang; Nocedal, Jorge (1997). "L-BFGS-B: Algorithm 778: L-BFGS-B, FORTRAN routines for big scale certain constrained optimization". ACM Transactions on Mathematical Software. Schraudolph, N.; Yu, J.; Günter, S. (2007). A stochastic quasi-Newton method for on-line convex optimization. Mokhtari, A.; Ribeiro, A. (2015). "Global convergence of online limited memory BFGS" (PDF). Journal of Machine Learning Analysis. Mokhtari, A.; Ribeiro, A. (2014). "RES: Regularized Stochastic BFGS Algorithm". IEEE Transactions on Sign Processing. 62 (23): 6089-6104. arXiv:1401.7625. Morales, J. L.; Nocedal, J. (2011). "Remark on "algorithm 778: L-BFGS-B: Fortran subroutines for large-scale bound constrained optimization"". ACM Transactions on Mathematical Software program. Liu, D. C.; Nocedal, J. (1989). "On the Restricted Memory Wave Technique for giant Scale Optimization". Haghighi, Aria (2 Dec 2014). "Numerical Optimization: Understanding L-BFGS". Pytlak, Radoslaw (2009). "Restricted Memory Quasi-Newton Algorithms". Conjugate Gradient Algorithms in Nonconvex Optimization.