Fletcher's implementation of the BFGS method. More...

#include <BFGSMinimizer.hpp>

Inheritance diagram for CDPL::Math::BFGSMinimizer< VA, VT, FVT >:

Public Types
enum	Status { SUCCESS = 0 , NO_PROGRESS = 1 , ITER_LIMIT_REACHED = 2 , GNORM_REACHED = 4 , DELTAF_REACHED = 8 }
	Status bitmask reported by minimize() and getStatus(). Multiple flags may be combined. More...

typedef VA	VariableArrayType
	The type of the variable array passed to the minimizer. More...

typedef VT	ValueType
	The scalar value type of VariableArrayType. More...

typedef FVT	FunctionValueType
	The scalar return type of the objective and gradient functions. More...

typedef std::function< FVT(const VA &, VA &)>	GradientFunction
	Type of the gradient function (computes the objective value and writes the gradient into the second argument). More...

typedef std::function< FVT(const VA &)>	ObjectiveFunction
	Type of the objective function. More...

Public Member Functions
	BFGSMinimizer (const ObjectiveFunction &func, const GradientFunction &grad_func)
	Constructs the `BFGSMinimizer` instance with the given objective and gradient functions. More...

ValueType	getGradientNorm () const
	Returns the L2 norm of the gradient at the end of the most recent iterate() call. More...

ValueType	getFunctionDelta () const
	Returns the magnitude of the function-value decrease produced by the most recent iterate() call. More...

ValueType	getFunctionValue () const
	Returns the function value at the end of the most recent iterate() call. More...

std::size_t	getNumIterations () const
	Returns the number of iterations performed by the most recent minimize() or iterate() loop. More...

Status	getStatus () const
	Returns the current status of the minimizer. More...

Status	minimize (VariableArrayType &x, VariableArrayType &g, std::size_t max_iter, const ValueType &g_norm, const ValueType &delta_f, bool do_setup=true)
	Runs the BFGS minimization loop on x. More...

ValueType	setup (const VariableArrayType &x, VariableArrayType &g, const ValueType &step_size=0.001, const ValueType &tol=0.15)
	Initializes the minimizer state for a subsequent iterate() / minimize() loop. More...

Status	iterate (ValueType &f, VariableArrayType &x, VariableArrayType &g)
	Performs a single BFGS iteration: line search along the current search direction, BFGS update of the inverse Hessian approximation, and selection of the new search direction. More...

Detailed Description

template<typename VA, typename VT = typename MinimizerVariableArrayTraits<VA>::ValueType, typename FVT = VT>
class CDPL::Math::BFGSMinimizer< VA, VT, FVT >

Fletcher's implementation of the BFGS method.

The implementation has been taken from the GNU Scientific Library.

See also: R. Fletcher, "Practical Method's of Optimization", Second Edition, ISBN 0471915475. Algorithms 2.6.2 and 2.6.4.

Member Typedef Documentation

◆ VariableArrayType

template<typename VA , typename VT = typename MinimizerVariableArrayTraits<VA>::ValueType, typename FVT = VT>

typedef VA CDPL::Math::BFGSMinimizer< VA, VT, FVT >::VariableArrayType

The type of the variable array passed to the minimizer.

◆ ValueType

template<typename VA , typename VT = typename MinimizerVariableArrayTraits<VA>::ValueType, typename FVT = VT>

typedef VT CDPL::Math::BFGSMinimizer< VA, VT, FVT >::ValueType

The scalar value type of VariableArrayType.

◆ FunctionValueType

template<typename VA , typename VT = typename MinimizerVariableArrayTraits<VA>::ValueType, typename FVT = VT>

typedef FVT CDPL::Math::BFGSMinimizer< VA, VT, FVT >::FunctionValueType

The scalar return type of the objective and gradient functions.

◆ GradientFunction

template<typename VA , typename VT = typename MinimizerVariableArrayTraits<VA>::ValueType, typename FVT = VT>

typedef std::function<FVT(const VA&, VA&)> CDPL::Math::BFGSMinimizer< VA, VT, FVT >::GradientFunction

Type of the gradient function (computes the objective value and writes the gradient into the second argument).

◆ ObjectiveFunction

template<typename VA , typename VT = typename MinimizerVariableArrayTraits<VA>::ValueType, typename FVT = VT>

typedef std::function<FVT(const VA&)> CDPL::Math::BFGSMinimizer< VA, VT, FVT >::ObjectiveFunction

Type of the objective function.

Member Enumeration Documentation

◆ Status

template<typename VA , typename VT = typename MinimizerVariableArrayTraits<VA>::ValueType, typename FVT = VT>

enum CDPL::Math::BFGSMinimizer::Status

Status bitmask reported by minimize() and getStatus(). Multiple flags may be combined.

Enumerator
SUCCESS	Iteration step completed successfully (no termination condition met yet).
NO_PROGRESS	No more progress towards the solution can be made.
ITER_LIMIT_REACHED	The maximum number of minimization iterations has been reached.
GNORM_REACHED	The configured gradient-norm threshold has been reached.
DELTAF_REACHED	The configured function-value delta between successive iterations has been reached.

Constructor & Destructor Documentation

◆ BFGSMinimizer()

template<typename VA , typename VT = typename MinimizerVariableArrayTraits<VA>::ValueType, typename FVT = VT>

CDPL::Math::BFGSMinimizer< VA, VT, FVT >::BFGSMinimizer	(	const ObjectiveFunction &	func,
		const GradientFunction &	grad_func
	)

inline

Constructs the BFGSMinimizer instance with the given objective and gradient functions.

Parameters

func	The objective function.
grad_func	The gradient function (also computes the objective value).

Member Function Documentation

◆ getGradientNorm()

template<typename VA , typename VT = typename MinimizerVariableArrayTraits<VA>::ValueType, typename FVT = VT>

ValueType CDPL::Math::BFGSMinimizer< VA, VT, FVT >::getGradientNorm ( ) const

inline

Returns the L2 norm of the gradient at the end of the most recent iterate() call.

Returns: The gradient norm.

◆ getFunctionDelta()

template<typename VA , typename VT = typename MinimizerVariableArrayTraits<VA>::ValueType, typename FVT = VT>

ValueType CDPL::Math::BFGSMinimizer< VA, VT, FVT >::getFunctionDelta ( ) const

inline

Returns the magnitude of the function-value decrease produced by the most recent iterate() call.

Returns: The function-value delta (positive when the function decreased).

◆ getFunctionValue()

template<typename VA , typename VT = typename MinimizerVariableArrayTraits<VA>::ValueType, typename FVT = VT>

ValueType CDPL::Math::BFGSMinimizer< VA, VT, FVT >::getFunctionValue ( ) const

inline

Returns the function value at the end of the most recent iterate() call.

Returns: The function value.

◆ getNumIterations()

template<typename VA , typename VT = typename MinimizerVariableArrayTraits<VA>::ValueType, typename FVT = VT>

std::size_t CDPL::Math::BFGSMinimizer< VA, VT, FVT >::getNumIterations ( ) const

inline

Returns the number of iterations performed by the most recent minimize() or iterate() loop.

Returns: The iteration count.

◆ getStatus()

template<typename VA , typename VT = typename MinimizerVariableArrayTraits<VA>::ValueType, typename FVT = VT>

Status CDPL::Math::BFGSMinimizer< VA, VT, FVT >::getStatus ( ) const

inline

Returns the current status of the minimizer.

Returns: The Status bitmask.

◆ minimize()

template<typename VA , typename VT = typename MinimizerVariableArrayTraits<VA>::ValueType, typename FVT = VT>

Status CDPL::Math::BFGSMinimizer< VA, VT, FVT >::minimize	(	VariableArrayType &	x,
		VariableArrayType &	g,
		std::size_t	max_iter,
		const ValueType &	g_norm,
		const ValueType &	delta_f,
		bool	do_setup = `true`
	)

inline

Runs the BFGS minimization loop on x.

Parameters

x	The variable vector to be minimized (modified in place).
g	The gradient vector (modified in place).
max_iter	The maximum number of iterations (0 means unlimited).
g_norm	The gradient-norm threshold below which the minimization is stopped (negative values disable this stop condition).
delta_f	The function-value-delta threshold below which the minimization is stopped (negative values disable this stop condition).
do_setup	If `true`, setup() is invoked at the start to initialize the minimizer.

Returns: The terminal Status bitmask of the minimization.

◆ setup()

template<typename VA , typename VT = typename MinimizerVariableArrayTraits<VA>::ValueType, typename FVT = VT>

ValueType CDPL::Math::BFGSMinimizer< VA, VT, FVT >::setup	(	const VariableArrayType &	x,
		VariableArrayType &	g,
		const ValueType &	step_size = `0.001`,
		const ValueType &	tol = `0.15`
	)

inline

Initializes the minimizer state for a subsequent iterate() / minimize() loop.

Parameters

x	The starting variable vector.
g	The gradient vector (filled with the gradient at x).
step_size	The initial step-size guess.
tol	The line-search tolerance.

Returns: The objective-function value at x.

◆ iterate()

template<typename VA , typename VT = typename MinimizerVariableArrayTraits<VA>::ValueType, typename FVT = VT>

Status CDPL::Math::BFGSMinimizer< VA, VT, FVT >::iterate	(	ValueType &	f,
		VariableArrayType &	x,
		VariableArrayType &	g
	)

inline

Performs a single BFGS iteration: line search along the current search direction, BFGS update of the inverse Hessian approximation, and selection of the new search direction.

Parameters

f	The current function value (updated in place).
x	The current variable vector (updated in place).
g	The current gradient vector (updated in place).

Returns: Status::SUCCESS if the iteration produced a step, otherwise the bitmask of stop conditions met.

The documentation for this class was generated from the following file:

BFGSMinimizer.hpp

Public Types

Public Member Functions

Detailed Description

template<typename VA, typename VT = typename MinimizerVariableArrayTraits<VA>::ValueType, typename FVT = VT> class CDPL::Math::BFGSMinimizer< VA, VT, FVT >

Member Typedef Documentation

◆ VariableArrayType

◆ ValueType

◆ FunctionValueType

◆ GradientFunction

◆ ObjectiveFunction

Member Enumeration Documentation

◆ Status

Constructor & Destructor Documentation

◆ BFGSMinimizer()

Member Function Documentation

◆ getGradientNorm()

◆ getFunctionDelta()

◆ getFunctionValue()

◆ getNumIterations()

◆ getStatus()

◆ minimize()

◆ setup()

◆ iterate()

template<typename VA, typename VT = typename MinimizerVariableArrayTraits<VA>::ValueType, typename FVT = VT>
class CDPL::Math::BFGSMinimizer< VA, VT, FVT >