Accord.NET (logo) BroydenFletcherGoldfarbShanno Class Accord.NET Framework
Online Show table of contents (goes to the online documentation index).
Limited-memory Broyden–Fletcher–Goldfarb–Shanno (L-BFGS) optimization method.
Inheritance Hierarchy

Online System Object
  Accord.Math.Optimization BroydenFletcherGoldfarbShanno

Namespace: Accord.Math.Optimization
Assembly: Accord.Math (in Accord.Math.dll) Version: 2.10.0.0 (2.10.0.4632)
Syntax

public class BroydenFletcherGoldfarbShanno : IGradientOptimizationMethod, 
	IOptimizationMethod
Remarks

The L-BFGS algorithm is a member of the broad family of quasi-Newton optimization methods. L-BFGS stands for 'Limited memory BFGS'. Indeed, L-BFGS uses a limited memory variation of the Broyden–Fletcher–Goldfarb–Shanno (BFGS) update to approximate the inverse Hessian matrix (denoted by Hk). Unlike the original BFGS method which stores a dense approximation, L-BFGS stores only a few vectors that represent the approximation implicitly. Due to its moderate memory requirement, L-BFGS method is particularly well suited for optimization problems with a large number of variables.

L-BFGS never explicitly forms or stores Hk. Instead, it maintains a history of the past m updates of the position x and gradient g, where generally the history mcan be short, often less than 10. These updates are used to implicitly do operations requiring the Hk-vector product.

The framework implementation of this method is based on the original FORTRAN source code by Jorge Nocedal (see references below). The original FORTRAN source code of LBFGS (for unconstrained problems) is available at http://www.netlib.org/opt/lbfgs_um.shar and had been made available under the public domain.

References:

Examples

The following example shows the basic usage of the L-BFGS solver to find the minimum of a function specifying its function and gradient.

// Suppose we would like to find the minimum of the function 
//  
//   f(x,y)  =  -exp{-(x-1)²} - exp{-(y-2)²/2} 
//  

// First we need write down the function either as a named 
// method, an anonymous method or as a lambda function:

Func<double[], double> f = (x) =>
    -Math.Exp(-Math.Pow(x[0] - 1, 2)) - Math.Exp(-0.5 * Math.Pow(x[1] - 2, 2));

// Now, we need to write its gradient, which is just the 
// vector of first partial derivatives del_f / del_x, as: 
//  
//   g(x,y)  =  { del f / del x, del f / del y } 
// 

Func<double[], double[]> g = (x) => new double[] 
{
    // df/dx = {-2 e^(-    (x-1)^2) (x-1)} 
    2 * Math.Exp(-Math.Pow(x[0] - 1, 2)) * (x[0] - 1),

    // df/dy = {-  e^(-1/2 (y-2)^2) (y-2)}
    Math.Exp(-0.5 * Math.Pow(x[1] - 2, 2)) * (x[1] - 2)
};

// Finally, we can create the L-BFGS solver, passing the functions as arguments 
var lbfgs = new BroydenFletcherGoldfarbShanno(numberOfVariables: 2, function: f, gradient: g);

// And then minimize the function: 
double minValue = lbfgs.Minimize();
double[] solution = lbfgs.Solution;

// The resultant minimum value should be -2, and the solution 
// vector should be { 1.0, 2.0 }. The answer can be checked on 
// Wolfram Alpha by clicking the following the link: 

// http://www.wolframalpha.com/input/?i=maximize+%28exp%28-%28x-1%29%C2%B2%29+%2B+exp%28-%28y-2%29%C2%B2%2F2%29%29
See Also