#include <itkQuasiNewtonLBFGSOptimizer.h>

Detailed Description

ITK version of the lbfgs algorithm ...

This class is an ITK version of the netlib lbfgs_ function. It gives exactly the same results, if used in combination with the itk::MoreThuenteLineSearchOptimizer.

The optimizer solves the unconstrained minimization problem

$\min F(x), \quad x = ( x_1,x_2,\ldots,x_N ),$

using the limited memory BFGS method. The routine is especially effective on problems involving a large number of variables. In a typical iteration of this method an approximation $H_k$ to the inverse of the Hessian is obtained by applying $M$ BFGS updates to a diagonal matrix $H_0$ , using information from the previous $M$ steps. The user specifies the number $M$ (Memory), which determines the amount of storage required by the routine.

The algorithm is described in "On the limited memory BFGS method for large scale optimization", by D. Liu and J. Nocedal, Mathematical Programming B 45 (1989) 503-528.

The steplength is determined at each iteration by means of a line search routine. The itk::MoreThuenteLineSearchOptimizer works well.

Definition at line 58 of file itkQuasiNewtonLBFGSOptimizer.h.

Inheritance diagram for itk::QuasiNewtonLBFGSOptimizer:

[legend]

Public Types
using	ConstPointer = SmartPointer< const Self >

using	DiagonalMatrixType = Array< double >

using	LineSearchOptimizerPointer = LineSearchOptimizerType::Pointer

using	LineSearchOptimizerType = LineSearchOptimizer

using	Pointer = SmartPointer< Self >

using	RhoType = Array< double >

using	ScaledCostFunctionType = ScaledSingleValuedCostFunction

using	ScalesType = NonLinearOptimizer::ScalesType

using	Self = QuasiNewtonLBFGSOptimizer

enum	StopConditionType { MetricError , LineSearchError , MaximumNumberOfIterations , InvalidDiagonalMatrix , GradientMagnitudeTolerance , ZeroStep , Unknown }

using	SType = std::vector< ParametersType >

using	Superclass = ScaledSingleValuedNonLinearOptimizer

using	YType = std::vector< DerivativeType >

Public Types inherited from itk::ScaledSingleValuedNonLinearOptimizer
using	ConstPointer = SmartPointer< const Self >

using	Pointer = SmartPointer< Self >

using	ScaledCostFunctionPointer = ScaledCostFunctionType::Pointer

using	ScaledCostFunctionType = ScaledSingleValuedCostFunction

using	ScalesType = NonLinearOptimizer::ScalesType

using	Self = ScaledSingleValuedNonLinearOptimizer

using	Superclass = SingleValuedNonLinearOptimizer

Public Member Functions
virtual const char *	GetClassName () const

virtual const DerivativeType &	GetCurrentGradient ()

virtual unsigned long	GetCurrentIteration () const

virtual double	GetCurrentStepLength () const

virtual MeasureType	GetCurrentValue () const

virtual double	GetGradientMagnitudeTolerance () const

virtual bool	GetInLineSearch () const

virtual unsigned long	GetMaximumNumberOfIterations () const

virtual unsigned int	GetMemory () const

virtual const StopConditionType &	GetStopCondition ()

	ITK_DISALLOW_COPY_AND_MOVE (QuasiNewtonLBFGSOptimizer)

	itkGetModifiableObjectMacro (LineSearchOptimizer, LineSearchOptimizerType)

virtual void	ResumeOptimization ()

virtual void	SetGradientMagnitudeTolerance (double _arg)

virtual void	SetLineSearchOptimizer (LineSearchOptimizerType *_arg)

virtual void	SetMaximumNumberOfIterations (unsigned long _arg)

virtual void	SetMemory (unsigned int _arg)

void	StartOptimization () override

virtual void	StopOptimization ()

Public Member Functions inherited from itk::ScaledSingleValuedNonLinearOptimizer
virtual const char *	GetClassName () const

const ParametersType &	GetCurrentPosition () const override

virtual bool	GetMaximize () const

virtual const ScaledCostFunctionType *	GetScaledCostFunction ()

virtual const ParametersType &	GetScaledCurrentPosition ()

bool	GetUseScales () const

virtual void	InitializeScales ()

	ITK_DISALLOW_COPY_AND_MOVE (ScaledSingleValuedNonLinearOptimizer)

virtual void	MaximizeOff ()

virtual void	MaximizeOn ()

void	SetCostFunction (CostFunctionType *costFunction) override

virtual void	SetMaximize (bool _arg)

virtual void	SetUseScales (bool arg)

Static Public Member Functions
static Pointer	New ()

Static Public Member Functions inherited from itk::ScaledSingleValuedNonLinearOptimizer
static Pointer	New ()

Protected Member Functions
virtual void	ComputeDiagonalMatrix (DiagonalMatrixType &diag_H0)

virtual void	ComputeSearchDirection (const DerivativeType &gradient, ParametersType &searchDir)

virtual void	LineSearch (const ParametersType searchDir, double &step, ParametersType &x, MeasureType &f, DerivativeType &g)

void	PrintSelf (std::ostream &os, Indent indent) const override

	QuasiNewtonLBFGSOptimizer ()

virtual void	SetInLineSearch (bool _arg)

virtual void	StoreCurrentPoint (const ParametersType &step, const DerivativeType &grad_dif)

virtual bool	TestConvergence (bool firstLineSearchDone)

	~QuasiNewtonLBFGSOptimizer () override=default

Protected Member Functions inherited from itk::ScaledSingleValuedNonLinearOptimizer
virtual void	GetScaledDerivative (const ParametersType &parameters, DerivativeType &derivative) const

virtual MeasureType	GetScaledValue (const ParametersType &parameters) const

virtual void	GetScaledValueAndDerivative (const ParametersType &parameters, MeasureType &value, DerivativeType &derivative) const

void	PrintSelf (std::ostream &os, Indent indent) const override

	ScaledSingleValuedNonLinearOptimizer ()

void	SetCurrentPosition (const ParametersType &param) override

virtual void	SetScaledCurrentPosition (const ParametersType &parameters)

	~ScaledSingleValuedNonLinearOptimizer () override=default

Protected Attributes
unsigned int	m_Bound { 0 }

DerivativeType	m_CurrentGradient

unsigned long	m_CurrentIteration { 0 }

double	m_CurrentStepLength { 0.0 }

MeasureType	m_CurrentValue { 0.0 }

bool	m_InLineSearch { false }

unsigned int	m_Point { 0 }

unsigned int	m_PreviousPoint { 0 }

RhoType	m_Rho

SType	m_S

bool	m_Stop { false }

StopConditionType	m_StopCondition { Unknown }

YType	m_Y

Protected Attributes inherited from itk::ScaledSingleValuedNonLinearOptimizer
ScaledCostFunctionPointer	m_ScaledCostFunction

ParametersType	m_ScaledCurrentPosition

Private Attributes
double	m_GradientMagnitudeTolerance { 1e-5 }

LineSearchOptimizerPointer	m_LineSearchOptimizer { nullptr }

unsigned long	m_MaximumNumberOfIterations { 100 }

unsigned int	m_Memory { 5 }

Member Typedef Documentation

◆ ConstPointer

using itk::QuasiNewtonLBFGSOptimizer::ConstPointer = SmartPointer<const Self>

Definition at line 66 of file itkQuasiNewtonLBFGSOptimizer.h.

◆ DiagonalMatrixType

using itk::QuasiNewtonLBFGSOptimizer::DiagonalMatrixType = Array<double>

Definition at line 81 of file itkQuasiNewtonLBFGSOptimizer.h.

◆ LineSearchOptimizerPointer

using itk::QuasiNewtonLBFGSOptimizer::LineSearchOptimizerPointer = LineSearchOptimizerType::Pointer

Definition at line 84 of file itkQuasiNewtonLBFGSOptimizer.h.

◆ LineSearchOptimizerType

using itk::QuasiNewtonLBFGSOptimizer::LineSearchOptimizerType = LineSearchOptimizer

Definition at line 82 of file itkQuasiNewtonLBFGSOptimizer.h.

◆ Pointer

using itk::QuasiNewtonLBFGSOptimizer::Pointer = SmartPointer<Self>

Definition at line 65 of file itkQuasiNewtonLBFGSOptimizer.h.

◆ RhoType

using itk::QuasiNewtonLBFGSOptimizer::RhoType = Array<double>

Definition at line 78 of file itkQuasiNewtonLBFGSOptimizer.h.

◆ ScaledCostFunctionType

using itk::ScaledSingleValuedNonLinearOptimizer::ScaledCostFunctionType = ScaledSingleValuedCostFunction

Definition at line 86 of file itkScaledSingleValuedNonLinearOptimizer.h.

◆ ScalesType

using itk::ScaledSingleValuedNonLinearOptimizer::ScalesType = NonLinearOptimizer::ScalesType

Definition at line 85 of file itkScaledSingleValuedNonLinearOptimizer.h.

◆ Self

using itk::QuasiNewtonLBFGSOptimizer::Self = QuasiNewtonLBFGSOptimizer

Definition at line 63 of file itkQuasiNewtonLBFGSOptimizer.h.

◆ SType

using itk::QuasiNewtonLBFGSOptimizer::SType = std::vector<ParametersType>

Definition at line 79 of file itkQuasiNewtonLBFGSOptimizer.h.

◆ Superclass

using itk::QuasiNewtonLBFGSOptimizer::Superclass = ScaledSingleValuedNonLinearOptimizer

Definition at line 64 of file itkQuasiNewtonLBFGSOptimizer.h.

◆ YType

using itk::QuasiNewtonLBFGSOptimizer::YType = std::vector<DerivativeType>

Definition at line 80 of file itkQuasiNewtonLBFGSOptimizer.h.

Member Enumeration Documentation

◆ StopConditionType

enum itk::QuasiNewtonLBFGSOptimizer::StopConditionType

Enumerator
MetricError
LineSearchError
MaximumNumberOfIterations
InvalidDiagonalMatrix
GradientMagnitudeTolerance
ZeroStep
Unknown

Definition at line 86 of file itkQuasiNewtonLBFGSOptimizer.h.

Constructor & Destructor Documentation

◆ QuasiNewtonLBFGSOptimizer()

itk::QuasiNewtonLBFGSOptimizer::QuasiNewtonLBFGSOptimizer ( )

protected

◆ ~QuasiNewtonLBFGSOptimizer()

itk::QuasiNewtonLBFGSOptimizer::~QuasiNewtonLBFGSOptimizer ( )

overrideprotecteddefault

Member Function Documentation

◆ ComputeDiagonalMatrix()

virtual void itk::QuasiNewtonLBFGSOptimizer::ComputeDiagonalMatrix ( DiagonalMatrixType & diag_H0 )

protectedvirtual

Compute H0

Override this method if not satisfied with the default choice.

◆ ComputeSearchDirection()

virtual void itk::QuasiNewtonLBFGSOptimizer::ComputeSearchDirection	(	const DerivativeType &	gradient,
		ParametersType &	searchDir
	)

protectedvirtual

Compute -Hg

COMPUTE -H*G USING THE FORMULA GIVEN IN: Nocedal, J. 1980, "Updating quasi-Newton matrices with limited storage", Mathematics of Computation, Vol.24, No.151, pp. 773-782.

◆ GetClassName()

virtual const char * itk::QuasiNewtonLBFGSOptimizer::GetClassName ( ) const

virtual

Reimplemented from itk::ScaledSingleValuedNonLinearOptimizer.

Reimplemented in elastix::QuasiNewtonLBFGS< TElastix >.

◆ GetCurrentGradient()

virtual const DerivativeType & itk::QuasiNewtonLBFGSOptimizer::GetCurrentGradient ( )

virtual

◆ GetCurrentIteration()

virtual unsigned long itk::QuasiNewtonLBFGSOptimizer::GetCurrentIteration ( ) const

virtual

Get information about optimization process:

◆ GetCurrentStepLength()

virtual double itk::QuasiNewtonLBFGSOptimizer::GetCurrentStepLength ( ) const

virtual

◆ GetCurrentValue()

virtual MeasureType itk::QuasiNewtonLBFGSOptimizer::GetCurrentValue ( ) const

virtual

◆ GetGradientMagnitudeTolerance()

virtual double itk::QuasiNewtonLBFGSOptimizer::GetGradientMagnitudeTolerance ( ) const

virtual

Setting: the mininum gradient magnitude.

The optimizer stops when: ||CurrentGradient|| < GradientMagnitudeTolerance * max(1, ||CurrentPosition||)

◆ GetInLineSearch()

virtual bool itk::QuasiNewtonLBFGSOptimizer::GetInLineSearch ( ) const

virtual

◆ GetMaximumNumberOfIterations()

virtual unsigned long itk::QuasiNewtonLBFGSOptimizer::GetMaximumNumberOfIterations ( ) const

virtual

Setting: the maximum number of iterations

◆ GetMemory()

virtual unsigned int itk::QuasiNewtonLBFGSOptimizer::GetMemory ( ) const

virtual

◆ GetStopCondition()

virtual const StopConditionType & itk::QuasiNewtonLBFGSOptimizer::GetStopCondition ( )

virtual

◆ ITK_DISALLOW_COPY_AND_MOVE()

itk::QuasiNewtonLBFGSOptimizer::ITK_DISALLOW_COPY_AND_MOVE ( QuasiNewtonLBFGSOptimizer )

◆ itkGetModifiableObjectMacro()

itk::QuasiNewtonLBFGSOptimizer::itkGetModifiableObjectMacro	(	LineSearchOptimizer	,
		LineSearchOptimizerType
	)

◆ LineSearch()

virtual void itk::QuasiNewtonLBFGSOptimizer::LineSearch	(	const ParametersType	searchDir,
		double &	step,
		ParametersType &	x,
		MeasureType &	f,
		DerivativeType &	g
	)

protectedvirtual

Perform a line search along the search direction. On calling, x, f, and g should contain the current position, the cost function value at this position, and the derivative. On return the step, x (new position), f (value at x), and g (derivative at x) are updated.

◆ New()

static Pointer itk::QuasiNewtonLBFGSOptimizer::New ( )

static

◆ PrintSelf()

void itk::QuasiNewtonLBFGSOptimizer::PrintSelf	(	std::ostream &	os,
		Indent	indent
	)		const

inlineoverrideprotected

Definition at line 142 of file itkQuasiNewtonLBFGSOptimizer.h.

◆ ResumeOptimization()

virtual void itk::QuasiNewtonLBFGSOptimizer::ResumeOptimization ( )

virtual

◆ SetGradientMagnitudeTolerance()

virtual void itk::QuasiNewtonLBFGSOptimizer::SetGradientMagnitudeTolerance ( double _arg )

virtual

◆ SetInLineSearch()

virtual void itk::QuasiNewtonLBFGSOptimizer::SetInLineSearch ( bool _arg )

protectedvirtual

◆ SetLineSearchOptimizer()

virtual void itk::QuasiNewtonLBFGSOptimizer::SetLineSearchOptimizer ( LineSearchOptimizerType * _arg )

virtual

Setting: the line search optimizer

◆ SetMaximumNumberOfIterations()

virtual void itk::QuasiNewtonLBFGSOptimizer::SetMaximumNumberOfIterations ( unsigned long _arg )

virtual

◆ SetMemory()

virtual void itk::QuasiNewtonLBFGSOptimizer::SetMemory ( unsigned int _arg )

virtual

Setting: the memory. The number of iterations that are used to estimate the Hessian. 5 by default. 0 results in (normalised) gradient descent search directions

◆ StartOptimization()

void itk::QuasiNewtonLBFGSOptimizer::StartOptimization ( )

override

◆ StopOptimization()

virtual void itk::QuasiNewtonLBFGSOptimizer::StopOptimization ( )

virtual

◆ StoreCurrentPoint()

virtual void itk::QuasiNewtonLBFGSOptimizer::StoreCurrentPoint	(	const ParametersType &	step,
		const DerivativeType &	grad_dif
	)

protectedvirtual

Store s = x_k - x_k-1 and y = g_k - g_k-1 in m_S and m_Y, and store 1/(ys) in m_Rho.

◆ TestConvergence()

virtual bool itk::QuasiNewtonLBFGSOptimizer::TestConvergence ( bool firstLineSearchDone )

protectedvirtual

Check if convergence has occurred; The firstLineSearchDone bool allows the implementation of TestConvergence to decide to skip a few convergence checks when no line search has performed yet (so, before the actual optimisation begins)

Reimplemented in elastix::QuasiNewtonLBFGS< TElastix >.

Field Documentation

◆ m_Bound

unsigned int itk::QuasiNewtonLBFGSOptimizer::m_Bound { 0 }

protected

Definition at line 161 of file itkQuasiNewtonLBFGSOptimizer.h.

◆ m_CurrentGradient

DerivativeType itk::QuasiNewtonLBFGSOptimizer::m_CurrentGradient

protected

Definition at line 145 of file itkQuasiNewtonLBFGSOptimizer.h.

◆ m_CurrentIteration

unsigned long itk::QuasiNewtonLBFGSOptimizer::m_CurrentIteration { 0 }

protected

Definition at line 147 of file itkQuasiNewtonLBFGSOptimizer.h.

◆ m_CurrentStepLength

double itk::QuasiNewtonLBFGSOptimizer::m_CurrentStepLength { 0.0 }

protected

Definition at line 150 of file itkQuasiNewtonLBFGSOptimizer.h.

◆ m_CurrentValue

MeasureType itk::QuasiNewtonLBFGSOptimizer::m_CurrentValue { 0.0 }

protected

Definition at line 146 of file itkQuasiNewtonLBFGSOptimizer.h.

◆ m_GradientMagnitudeTolerance

double itk::QuasiNewtonLBFGSOptimizer::m_GradientMagnitudeTolerance { 1e-5 }

private

Definition at line 202 of file itkQuasiNewtonLBFGSOptimizer.h.

◆ m_InLineSearch

bool itk::QuasiNewtonLBFGSOptimizer::m_InLineSearch { false }

protected

Is true when the LineSearchOptimizer has been started.

Definition at line 153 of file itkQuasiNewtonLBFGSOptimizer.h.

◆ m_LineSearchOptimizer

LineSearchOptimizerPointer itk::QuasiNewtonLBFGSOptimizer::m_LineSearchOptimizer { nullptr }

private

Definition at line 203 of file itkQuasiNewtonLBFGSOptimizer.h.

◆ m_MaximumNumberOfIterations

unsigned long itk::QuasiNewtonLBFGSOptimizer::m_MaximumNumberOfIterations { 100 }

private

Definition at line 201 of file itkQuasiNewtonLBFGSOptimizer.h.

◆ m_Memory

unsigned int itk::QuasiNewtonLBFGSOptimizer::m_Memory { 5 }

private

Definition at line 204 of file itkQuasiNewtonLBFGSOptimizer.h.

◆ m_Point

unsigned int itk::QuasiNewtonLBFGSOptimizer::m_Point { 0 }

protected

Definition at line 159 of file itkQuasiNewtonLBFGSOptimizer.h.

◆ m_PreviousPoint

unsigned int itk::QuasiNewtonLBFGSOptimizer::m_PreviousPoint { 0 }

protected

Definition at line 160 of file itkQuasiNewtonLBFGSOptimizer.h.

◆ m_Rho

RhoType itk::QuasiNewtonLBFGSOptimizer::m_Rho

protected

Definition at line 155 of file itkQuasiNewtonLBFGSOptimizer.h.

◆ m_S

SType itk::QuasiNewtonLBFGSOptimizer::m_S

protected

Definition at line 156 of file itkQuasiNewtonLBFGSOptimizer.h.

◆ m_Stop

bool itk::QuasiNewtonLBFGSOptimizer::m_Stop { false }

protected

Definition at line 149 of file itkQuasiNewtonLBFGSOptimizer.h.

◆ m_StopCondition

StopConditionType itk::QuasiNewtonLBFGSOptimizer::m_StopCondition { Unknown }

protected

Definition at line 148 of file itkQuasiNewtonLBFGSOptimizer.h.

◆ m_Y

YType itk::QuasiNewtonLBFGSOptimizer::m_Y

protected

Definition at line 157 of file itkQuasiNewtonLBFGSOptimizer.h.

Detailed Description

Public Types

Public Member Functions

Static Public Member Functions

Protected Member Functions

Protected Attributes

Private Attributes

Member Typedef Documentation

◆ ConstPointer

◆ DiagonalMatrixType

◆ LineSearchOptimizerPointer

◆ LineSearchOptimizerType

◆ Pointer

◆ RhoType

◆ ScaledCostFunctionType

◆ ScalesType

◆ Self

◆ SType

◆ Superclass

◆ YType

Member Enumeration Documentation

◆ StopConditionType

Constructor & Destructor Documentation

◆ QuasiNewtonLBFGSOptimizer()

◆ ~QuasiNewtonLBFGSOptimizer()

Member Function Documentation

◆ ComputeDiagonalMatrix()

◆ ComputeSearchDirection()

◆ GetClassName()

◆ GetCurrentGradient()

◆ GetCurrentIteration()

◆ GetCurrentStepLength()

◆ GetCurrentValue()

◆ GetGradientMagnitudeTolerance()

◆ GetInLineSearch()

◆ GetMaximumNumberOfIterations()

◆ GetMemory()

◆ GetStopCondition()

◆ ITK_DISALLOW_COPY_AND_MOVE()

◆ itkGetModifiableObjectMacro()

◆ LineSearch()

◆ New()

◆ PrintSelf()

◆ ResumeOptimization()

◆ SetGradientMagnitudeTolerance()

◆ SetInLineSearch()

◆ SetLineSearchOptimizer()

◆ SetMaximumNumberOfIterations()

◆ SetMemory()

◆ StartOptimization()

◆ StopOptimization()

◆ StoreCurrentPoint()

◆ TestConvergence()

Field Documentation

◆ m_Bound

◆ m_CurrentGradient

◆ m_CurrentIteration

◆ m_CurrentStepLength

◆ m_CurrentValue

◆ m_GradientMagnitudeTolerance

◆ m_InLineSearch

◆ m_LineSearchOptimizer

◆ m_MaximumNumberOfIterations

◆ m_Memory

◆ m_Point

◆ m_PreviousPoint

◆ m_Rho

◆ m_S

◆ m_Stop

◆ m_StopCondition

◆ m_Y