LBFGS-Lite

A header-only L-BFGS unconstrained optimizer.

0. About

LBFGS-Lite is a C++ header-only library for unconstrained optimization. Many engineering considerations are added for improved robustness compared to the original version by Nocedal.

1. How to use

All explanations are detailed by the comments in "lbfgs.hpp". See "lbfgs_example.cpp" for the calling procedure. You may need to install Eigen via "sudo apt install libeigen3-dev" because we use Eigen for better performance since ver. 2.1. If you need a pure C-style lib without any external dependence, please refer to ver. 0.9.

2. Features

• Only one header file "lbfgs.hpp" is all you need.

• The library implements Limited-Memory Broyden-Fletcher-Goldfarb-Shanno Method (L-BFGS).

• A highly robust line search proposed by Lewis and Overton has been employed since ver. 2.1.

• Both smooth (C2) and nonsmooth (C0 but piecewise C2) functions are supported.

• Cautious update by Li and Fukushima is employed for global convergence in nonconvex cases.

• Externally provided maximum step size is convenient to functions defined on bounded sets.

3. Why this lib

• Our lib is well-organized and concise (about 800 lines).

• Many other libs use Nocedal's zoom line search, More-Thuente line search, or Hager-Zhang line search. The truth is, interpolation-based schemes bring many tunable parameters and make more or less assumptions on the function smoothness. Engineering practice tells us that these assumptions can fail due to bad numerical conditions and ill-shaped functions. Admittedly, they slightly reduce the iteration number in some cases, but also easily-crashed.

• Some other libs provide user-specified options for Armijo and weak/strong Wolfe condition without considering positive definiteness (PD) of the approximated Hessian. This is misleading because if only Armijo condition is satisfied, the PD property is not guaranteed and the solver is unstable or easily-crashed. We make the weak Wolfe condition mandatory here, which suffices for PD property.

• We use Lewis-Overton line search as the only scheme since ver. 2.1 from which nonsmooth functions are supported. Other schemes either assume high orders of continuity, or enforce the strong Wolfe condition can never be fulfilled by nonsmooth functions. Moreover, Lewis-Overton line search are widely adopted in many graphics applications involving optimization on scene, shape, or mesh, showing its practical robustness.

• According to our practice, the function/gradient evaluation numbers are comparable with interpolation-based schemes. Sometimes it even requires fewer function calls. If you insist an interpolation-one for smooth well-shaped cost function, we also propose our ver. 0.9 where a More-Thuente line search is kept.

• Other schemes' global convergence on non-convex functions are not guaranteed theoretically. We avoid the potential problems by employing the cautious update scheme in our lib without additional computation overhead.

6. Licence

LBFGS-Lite is modified from the C version by Okazaki, which is further based on the original Fortran version by Nocedal. Thus it is distributed under the term of the MIT license according to previous ones by Okazaki and by Nocedal. Please refer to LICENSE file in the distribution.

7. Maintaince

If any bug, please contact Zhepei Wang ([email protected]).