// Limited-memory BFGS (L-BFGS) algorithm implementation as described by Nocedal.
// L-BFGS is an unconstrained quasi-Newton optimization method that uses a limited memory variation
// of the Broyden–Fletcher–Goldfarb–Shanno (BFGS) update to approximate the inverse Hessian matrix.
// The implementation is robust as it uses a simple line-search technique (backtracking in one
// direction only) and still works even if the L-BFGS algorithm returns a non descent direction (as
// it will then restart the optimization starting from the current solution).
// Its robustness enables it to minimize non-smooth functions, such as the hinge loss.
//
// Copyright (c) 2012 Idiap Research Institute, http://www.idiap.ch/
// Written by Charles Dubout
//
// This file is part of LBFGS.
//
// LBFGS is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License version 3 as
// published by the Free Software Foundation.
//
// LBFGS is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with LBFGS. If not, see .
#ifndef LBFGS_H
#define LBFGS_H
/// Limited-memory BFGS (L-BFGS) algorithm implementation as described by Nocedal.
/// L-BFGS is an unconstrained quasi-Newton optimization method that uses a limited memory variation
/// of the Broyden–Fletcher–Goldfarb–Shanno (BFGS) update to approximate the inverse Hessian matrix.
/// The implementation is robust as it uses a simple line-search technique (backtracking in one
/// direction only) and still works even if the L-BFGS algorithm returns a non descent direction (as
/// it will then restart the optimization starting from the current solution).
/// Its robustness enables it to minimize non-smooth functions, such as the hinge loss.
class LBFGS
{
public:
/// Callback interface to provide objective function and gradient evaluations.
class IFunction
{
public:
/// Destructor.
virtual ~IFunction();
/// Returns The number of variables.
virtual int dim() const = 0;
/// Provides objective function and gradient evaluations.
/// @param[in] x Current solution.
/// @param[out] g The gradient vector which must be computed for the current solution.
/// @returns The value of the objective function for the current solution.
virtual double operator()(const double * x, double * g = 0) const = 0;
/// Provides information about the current iteration.
/// @param[in] x The current solution.
/// @param[in] g The gradient vector of the current solution.
/// @param[in] n The number of variables.
/// @param[in] fx The current value of the objective function.
/// @param[in] xnorm The Euclidean norm of the current solution.
/// @param[in] gnorm The Euclidean norm of the gradient vector.
/// @param[in] step The line-search step used for this iteration.
/// @param[in] t The iteration count.
/// @param[in] ls The number of evaluations called for this iteration.
virtual void progress(const double * x, const double * g, int n, double fx, double xnorm,
double gnorm, double step, int t, int ls) const;
};
public:
/// Constructor.
/// @param[in] function Callback function to provide objective function and gradient
/// evaluations.
/// @param[in] epsilon Accuracy to which the solution is to be found.
/// @param[in] maxIterations Maximum number of iterations allowed.
/// @param[in] int maxLineSearches Maximum number of line-searches per iteration allowed.
/// @param[in] maxHistory Maximum history length of previous solutions and gradients.
LBFGS(const IFunction * function = 0, double epsilon = 1e-6, int maxIterations = 400,
int maxLineSearches = 20, int maxHistory = 10);
/// Starts the L-BFGS optimization process.
/// @param[in,out] x Initial solution on entry. Receives the optimization result on exit.
/// @returns The final value of the objective function.
double operator()(double * x) const;
private:
// Constructor parameters
const IFunction * function_;
double epsilon_;
int maxIterations_;
int maxLineSearches_;
int maxHistory_;
};
#endif // LBFGS_H