The limited-memory Broyden-Fletcher-Goldfarb-Shanno (LBFGS) algorithm [Byrd2015] follows the algorithmic framework of an iterative solver with the algorithm-specific transformation T and set of intrinsic parameters S t defined for the memory parameter m, frequency of curvature estimates calculation L, and step-length sequence α t > 0, algorithm-specific vector U and power d of Lebesgue space defined as follows:
For the LBFGS algorithm, the set of intrinsic parameters S t includes the following:
- Correction pairs (s j , y j )
- Correction index k in the buffer that stores correction pairs
- Index of last iteration t of the main loop from the previous run
- Average value of arguments for the previous L iterations
- Average value of arguments for the last L iterations
Below is the definition and update flow of the intrinsic parameters (s i , y i ). The index is set and remains zero for the first 2L-1 iterations of the main loop. Starting with iteration 2L, the algorithm executes the following steps for each of L iterations of the main loop:
at the point for the objective function using Hessians of its terms
The set S k of intrinsic parameters is updated once per L iterations of the major loop and remains unchanged between iterations with the numbers that are multiples of L
A cyclic buffer stores correction pairs. The algorithm fills the buffer with pairs one-by-one. Once the buffer is full, it returns to the beginning and overwrites the previous correction pairs.
Hessian Update Algorithm
This algorithm computes the approximation of the inverse Hessian matrix from the set of correction pairs [Byrd2015]).
For a given set of correction pairs (s j , y j ), j = k - min (k, m) +1, ..., k: