A readable implementation of L-BFGS method in modern C++
L-BFGS is a pretty simple algorithm. Nowadays, one can find an explanation of it in pretty much any textbook on numerical optimisation (e.g. I used this book by J.Nocedal and S.Wright as a reference). Like most iterative optimisation algorithms it amounts to
- figuring out the direction in which to step, and
- calculating the step size
repeating these steps until convergence is reached. The tricky part is calculation of the step size. Line search algorithms are usually used for this. There are two line search algorithms which I am aware of which are considered state-of-the-art: More-Thuente and Hager-Zhang.
I decided to look for an implementation of More-Thuente line search algorithm first since it has been around since 1994. However, to my surprise, there appears to only be one implementation. All other implementations (e.g. rconjgrad, Trilinos, LineSearches.jl, liblbfgs, CppNumericalSolvers) use the exact same code except for the translation from MatLab to their language of choice.
It is also quite difficult to see how the code corresponds to the original
paper. So I decided to write an implementation which it simple enough so that
it could be understood by anyone who knows a bit of C++17 and has read the
paper.
The preferred way to use this library is CMake + git submodules.