Click or drag to resize
Accord.NET (logo)

BroydenFletcherGoldfarbShanno Class

Limited-memory Broyden–Fletcher–Goldfarb–Shanno (L-BFGS) optimization method.
Inheritance Hierarchy
SystemObject
  Accord.Math.OptimizationBaseOptimizationMethod
    Accord.Math.OptimizationBaseGradientOptimizationMethod
      Accord.Math.OptimizationBroydenFletcherGoldfarbShanno

Namespace:  Accord.Math.Optimization
Assembly:  Accord.Math (in Accord.Math.dll) Version: 3.5.0
Syntax
public class BroydenFletcherGoldfarbShanno : BaseGradientOptimizationMethod, 
	IGradientOptimizationMethod, IOptimizationMethod, IOptimizationMethod<double[], double>, 
	IGradientOptimizationMethod<double[], double>, IFunctionOptimizationMethod<double[], double>, 
	IOptimizationMethod<BroydenFletcherGoldfarbShannoStatus>, IOptimizationMethod<double[], double, BroydenFletcherGoldfarbShannoStatus>
Request Example View Source

The BroydenFletcherGoldfarbShanno type exposes the following members.

Constructors
Properties
  NameDescription
Public propertyCorrections
The number of corrections to approximate the inverse Hessian matrix. Default is 6. Values less than 3 are not recommended. Large values will result in excessive computing time.
Public propertyDelta
Delta for convergence test.
Public propertyEpsilon
Epsilon for convergence test.
Public propertyFunction
Gets or sets the function to be optimized.
(Inherited from BaseOptimizationMethod.)
Public propertyFunctionTolerance
The machine precision for floating-point values.
Public propertyGradient
Gets or sets a function returning the gradient vector of the function to be optimized for a given value of its free parameters.
(Inherited from BaseGradientOptimizationMethod.)
Public propertyGradientTolerance
A parameter to control the accuracy of the line search routine.
Public propertyLineSearch
The line search algorithm.
Public propertyMaxIterations
The maximum number of iterations.
Public propertyMaxLineSearch
The maximum number of trials for the line search.
Public propertyMaxStep
The maximum step of the line search.
Public propertyMinStep
The minimum step of the line search routine.
Public propertyNumberOfVariables
Gets the number of variables (free parameters) in the optimization problem.
(Inherited from BaseOptimizationMethod.)
Public propertyOrthantwiseC
Coefficient for the L1 norm of variables.
Public propertyOrthantwiseEnd
End index for computing L1 norm of the variables.
Public propertyOrthantwiseStart
Start index for computing L1 norm of the variables.
Public propertyParameterTolerance
A parameter to control the accuracy of the line search routine. The default value is 1e-4. This parameter should be greater than zero and smaller than 0.5.
Public propertyPast
Distance for delta-based convergence test.
Public propertySolution
Gets the current solution found, the values of the parameters which optimizes the function.
(Inherited from BaseOptimizationMethod.)
Public propertyStatus
Public propertyToken
Gets or sets a cancellation token that can be used to stop the learning algorithm while it is running.
(Inherited from BaseOptimizationMethod.)
Public propertyValue
Gets the output of the function at the current Solution.
(Inherited from BaseOptimizationMethod.)
Public propertyWolfe
A coefficient for the Wolfe condition.
Top
Methods
  NameDescription
Public methodEquals
Determines whether the specified object is equal to the current object.
(Inherited from Object.)
Protected methodFinalize
Allows an object to try to free resources and perform other cleanup operations before it is reclaimed by garbage collection.
(Inherited from Object.)
Public methodGetHashCode
Serves as the default hash function.
(Inherited from Object.)
Public methodGetType
Gets the Type of the current instance.
(Inherited from Object.)
Public methodMaximize
Finds the maximum value of a function. The solution vector will be made available at the Solution property.
(Inherited from BaseGradientOptimizationMethod.)
Public methodMaximize(Double)
Finds the maximum value of a function. The solution vector will be made available at the Solution property.
(Inherited from BaseOptimizationMethod.)
Protected methodMemberwiseClone
Creates a shallow copy of the current Object.
(Inherited from Object.)
Public methodMinimize
Finds the minimum value of a function. The solution vector will be made available at the Solution property.
(Inherited from BaseGradientOptimizationMethod.)
Public methodMinimize(Double)
Finds the minimum value of a function. The solution vector will be made available at the Solution property.
(Inherited from BaseOptimizationMethod.)
Protected methodOnNumberOfVariablesChanged
Called when the NumberOfVariables property has changed.
(Overrides BaseOptimizationMethodOnNumberOfVariablesChanged(Int32).)
Protected methodOptimize
Implements the actual optimization algorithm. This method should try to minimize the objective function.
(Overrides BaseOptimizationMethodOptimize.)
Public methodToString
Returns a string that represents the current object.
(Inherited from Object.)
Top
Events
  NameDescription
Public eventProgress
Occurs when progress is made during the optimization.
Top
Extension Methods
  NameDescription
Public Extension MethodHasMethod
Checks whether an object implements a method with the given name.
(Defined by ExtensionMethods.)
Public Extension MethodIsEqual
Compares two objects for equality, performing an elementwise comparison if the elements are vectors or matrices.
(Defined by Matrix.)
Public Extension MethodToTOverloaded.
Converts an object into another type, irrespective of whether the conversion can be done at compile time or not. This can be used to convert generic types to numeric types during runtime.
(Defined by ExtensionMethods.)
Public Extension MethodToTOverloaded.
Converts an object into another type, irrespective of whether the conversion can be done at compile time or not. This can be used to convert generic types to numeric types during runtime.
(Defined by Matrix.)
Top
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 L-BFGS (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:
bool success = lbfgs.Minimize();
double minValue = lbfgs.Value;
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