#include <itkMoreThuenteLineSearchOptimizer.h>

Detailed Description

ITK version of the MoreThuente line search algorithm.

This class is an ITK version of the netlib function mcsrch_. It gives exactly the same results.

The purpose of this optimizer is to find a step which satisfies a sufficient decrease condition and a curvature condition.

At each stage the subroutine updates an interval of uncertainty with endpoints stx and sty. The interval of uncertainty is initially chosen so that it contains a minimizer of the modified function

$f(x+stp*s) - f(x) - ValueTolerance*stp*(gradf(x)'s).$

If a step is obtained for which the modified function has a nonpositive function value and nonnegative derivative, then the interval of uncertainty is chosen so that it contains a minimizer of $f(x+stp*s)$ .

The algorithm is designed to find a step which satisfies the sufficient decrease condition

$f(x+stp*s) <= f(x) + ValueTolerance*stp*(gradf(x)'s),$

and the curvature condition

$\| gradf(x+stp*s)'s) \| <= GradientTolerance * \| gradf(x)'s \|.$

(together also called the Strong Wolfe Conditions)

if the ValueTolerance is less than the GradientTolerance and if, for example, the function is bounded below, then there is always a step which satisfies both conditions. If no step can be found which satisfies both conditions, then the algorithm usually stops when rounding errors prevent further progress. In this case stp only satisfies the sufficient decrease condition.

Definition at line 71 of file itkMoreThuenteLineSearchOptimizer.h.

Inheritance diagram for itk::MoreThuenteLineSearchOptimizer:

[legend]

Public Types
using	ConstPointer = SmartPointer<const Self>

using	Pointer = SmartPointer<Self>

using	Self = MoreThuenteLineSearchOptimizer

enum	StopConditionType { StrongWolfeConditionsSatisfied , MetricError , MaximumNumberOfIterations , StepTooSmall , StepTooLarge , IntervalTooSmall , RoundingError , AscentSearchDirection , Unknown }

using	Superclass = LineSearchOptimizer

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

using	Pointer = SmartPointer<Self>

using	Self = LineSearchOptimizer

using	Superclass = SingleValuedNonLinearOptimizer

Public Member Functions
virtual const char *	GetClassName () const

void	GetCurrentDerivative (DerivativeType &derivative) const override

virtual double	GetCurrentDirectionalDerivative () const

virtual unsigned long	GetCurrentIteration () const

MeasureType	GetCurrentValue () const override

void	GetCurrentValueAndDerivative (MeasureType &value, DerivativeType &derivative) const override

virtual bool	GetCurvatureConditionSatisfied () const

virtual double	GetGradientTolerance () const

virtual double	GetIntervalTolerance () const

virtual unsigned long	GetMaximumNumberOfIterations () const

virtual const StopConditionType &	GetStopCondition ()

virtual bool	GetSufficientDecreaseConditionSatisfied () const

virtual double	GetValueTolerance () const

	ITK_DISALLOW_COPY_AND_MOVE (MoreThuenteLineSearchOptimizer)

virtual void	SetGradientTolerance (double _arg)

void	SetInitialDerivative (const DerivativeType &derivative) override

void	SetInitialValue (MeasureType value) override

virtual void	SetIntervalTolerance (double _arg)

virtual void	SetMaximumNumberOfIterations (unsigned long _arg)

virtual void	SetValueTolerance (double _arg)

void	StartOptimization () override

virtual void	StopOptimization ()

Public Member Functions inherited from itk::LineSearchOptimizer
virtual double	GetCurrentStepLength () const

virtual double	GetInitialStepLengthEstimate () const

virtual const ParametersType &	GetLineSearchDirection ()

virtual double	GetMaximumStepLength () const

virtual double	GetMinimumStepLength () const

	ITK_DISALLOW_COPY_AND_MOVE (LineSearchOptimizer)

virtual void	SetInitialStepLengthEstimate (double _arg)

virtual void	SetLineSearchDirection (const ParametersType &arg)

virtual void	SetMaximumStepLength (double _arg)

virtual void	SetMinimumStepLength (double _arg)

Static Public Member Functions
static Pointer	New ()

Protected Member Functions
void	BoundStep (double &step) const

virtual int	CheckSettings ()

virtual void	ComputeCurrentValueAndDerivative ()

virtual void	ComputeNewStepAndInterval ()

virtual void	ForceSufficientDecreaseInIntervalWidth ()

virtual void	GetInitialValueAndDerivative ()

void	InitializeLineSearch ()

	MoreThuenteLineSearchOptimizer ()

virtual void	PrepareForUnusualTermination ()

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

virtual int	SafeGuardedStep (double &stx, double &fx, double &dx, double &sty, double &fy, double &dy, double &stp, const double fp, const double dp, bool &brackt, const double stpmin, const double stpmax) const

virtual void	TestConvergence (bool &stop)

virtual void	UpdateIntervalMinimumAndMaximum ()

	~MoreThuenteLineSearchOptimizer () override=default

Protected Member Functions inherited from itk::LineSearchOptimizer
double	DirectionalDerivative (const DerivativeType &derivative) const

	LineSearchOptimizer ()

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

virtual void	SetCurrentStepLength (double step)

	~LineSearchOptimizer () override=default

Protected Attributes
bool	m_brackt {}

unsigned long	m_CurrentIteration {}

bool	m_CurvatureConditionSatisfied {}

double	m_dg {}

double	m_dginit {}

double	m_dgtest {}

double	m_dgx {}

double	m_dgy {}

MeasureType	m_f {}

MeasureType	m_finit {}

MeasureType	m_fx {}

MeasureType	m_fy {}

DerivativeType	m_g {}

bool	m_InitialDerivativeProvided {}

bool	m_InitialValueProvided {}

bool	m_SafeGuardedStepFailed {}

bool	m_stage1 {}

double	m_step {}

double	m_stepmax {}

double	m_stepmin {}

double	m_stepx {}

double	m_stepy {}

bool	m_Stop {}

StopConditionType	m_StopCondition {}

bool	m_SufficientDecreaseConditionSatisfied {}

double	m_width {}

double	m_width1 {}

Protected Attributes inherited from itk::LineSearchOptimizer
double	m_CurrentStepLength {}

Private Attributes
double	m_GradientTolerance {}

double	m_IntervalTolerance {}

unsigned long	m_MaximumNumberOfIterations {}

double	m_ValueTolerance {}

Member Typedef Documentation

◆ ConstPointer

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

Definition at line 79 of file itkMoreThuenteLineSearchOptimizer.h.

◆ Pointer

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

Definition at line 78 of file itkMoreThuenteLineSearchOptimizer.h.

◆ Self

using itk::MoreThuenteLineSearchOptimizer::Self = MoreThuenteLineSearchOptimizer

Definition at line 76 of file itkMoreThuenteLineSearchOptimizer.h.

◆ Superclass

using itk::MoreThuenteLineSearchOptimizer::Superclass = LineSearchOptimizer

Definition at line 77 of file itkMoreThuenteLineSearchOptimizer.h.

Member Enumeration Documentation

◆ StopConditionType

enum itk::MoreThuenteLineSearchOptimizer::StopConditionType

Enumerator
StrongWolfeConditionsSatisfied
MetricError
MaximumNumberOfIterations
StepTooSmall
StepTooLarge
IntervalTooSmall
RoundingError
AscentSearchDirection
Unknown

Definition at line 89 of file itkMoreThuenteLineSearchOptimizer.h.

Constructor & Destructor Documentation

◆ MoreThuenteLineSearchOptimizer()

itk::MoreThuenteLineSearchOptimizer::MoreThuenteLineSearchOptimizer ( )

protected

◆ ~MoreThuenteLineSearchOptimizer()

itk::MoreThuenteLineSearchOptimizer::~MoreThuenteLineSearchOptimizer ( )

overrideprotecteddefault

Member Function Documentation

◆ BoundStep()

void itk::MoreThuenteLineSearchOptimizer::BoundStep ( double & step ) const

protected

Force a step to be within the bounds MinimumStepLength and MaximumStepLength

◆ CheckSettings()

virtual int itk::MoreThuenteLineSearchOptimizer::CheckSettings ( )

protectedvirtual

Check the input settings for errors.

◆ ComputeCurrentValueAndDerivative()

virtual void itk::MoreThuenteLineSearchOptimizer::ComputeCurrentValueAndDerivative ( )

protectedvirtual

Ask the cost function to compute m_f and m_g at the current position.

◆ ComputeNewStepAndInterval()

virtual void itk::MoreThuenteLineSearchOptimizer::ComputeNewStepAndInterval ( )

protectedvirtual

Update the interval of uncertainty and compute the new step

◆ ForceSufficientDecreaseInIntervalWidth()

virtual void itk::MoreThuenteLineSearchOptimizer::ForceSufficientDecreaseInIntervalWidth ( )

protectedvirtual

Force a sufficient decrease in the size of the interval of uncertainty

◆ GetClassName()

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

virtual

Reimplemented from itk::LineSearchOptimizer.

◆ GetCurrentDerivative()

void itk::MoreThuenteLineSearchOptimizer::GetCurrentDerivative ( DerivativeType & derivative ) const

overridevirtual

Implements itk::LineSearchOptimizer.

◆ GetCurrentDirectionalDerivative()

virtual double itk::MoreThuenteLineSearchOptimizer::GetCurrentDirectionalDerivative ( ) const

virtual

◆ GetCurrentIteration()

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

virtual

Progress information: about the state of convergence

◆ GetCurrentValue()

MeasureType itk::MoreThuenteLineSearchOptimizer::GetCurrentValue ( ) const

overridevirtual

Implements itk::LineSearchOptimizer.

◆ GetCurrentValueAndDerivative()

void itk::MoreThuenteLineSearchOptimizer::GetCurrentValueAndDerivative	(	MeasureType &	value,
		DerivativeType &	derivative ) const

overridevirtual

Progress information: value, derivative, and directional derivative at the current position.

Implements itk::LineSearchOptimizer.

◆ GetCurvatureConditionSatisfied()

virtual bool itk::MoreThuenteLineSearchOptimizer::GetCurvatureConditionSatisfied ( ) const

virtual

◆ GetGradientTolerance()

virtual double itk::MoreThuenteLineSearchOptimizer::GetGradientTolerance ( ) const

virtual

◆ GetInitialValueAndDerivative()

virtual void itk::MoreThuenteLineSearchOptimizer::GetInitialValueAndDerivative ( )

protectedvirtual

Load the initial value and derivative into m_f and m_g.

◆ GetIntervalTolerance()

virtual double itk::MoreThuenteLineSearchOptimizer::GetIntervalTolerance ( ) const

virtual

◆ GetMaximumNumberOfIterations()

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

virtual

Setting: the maximum number of iterations. 20 by default.

◆ GetStopCondition()

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

virtual

◆ GetSufficientDecreaseConditionSatisfied()

virtual bool itk::MoreThuenteLineSearchOptimizer::GetSufficientDecreaseConditionSatisfied ( ) const

virtual

◆ GetValueTolerance()

virtual double itk::MoreThuenteLineSearchOptimizer::GetValueTolerance ( ) const

virtual

◆ InitializeLineSearch()

void itk::MoreThuenteLineSearchOptimizer::InitializeLineSearch ( )

protected

Initialize the interval of uncertainty etc.

◆ ITK_DISALLOW_COPY_AND_MOVE()

itk::MoreThuenteLineSearchOptimizer::ITK_DISALLOW_COPY_AND_MOVE ( MoreThuenteLineSearchOptimizer )

◆ New()

static Pointer itk::MoreThuenteLineSearchOptimizer::New ( )

static

◆ PrepareForUnusualTermination()

virtual void itk::MoreThuenteLineSearchOptimizer::PrepareForUnusualTermination ( )

protectedvirtual

Set m_step to the best step until now, if unusual termination is expected

◆ PrintSelf()

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

overrideprotected

◆ SafeGuardedStep()

virtual int itk::MoreThuenteLineSearchOptimizer::SafeGuardedStep	(	double &	stx,
		double &	fx,
		double &	dx,
		double &	sty,
		double &	fy,
		double &	dy,
		double &	stp,
		const double	fp,
		const double	dp,
		bool &	brackt,
		const double	stpmin,
		const double	stpmax ) const

protectedvirtual

Advance a step along the line search direction and update the interval of uncertainty.

◆ SetGradientTolerance()

virtual void itk::MoreThuenteLineSearchOptimizer::SetGradientTolerance ( double _arg )

virtual

Setting: the gradient tolerance. By default set to 0.9.

The line search tries to find a StepLength that satisfies the curvature condition: ABS(dF/ds(X + StepLength * s) <= GradientTolerance * ABS(dF/ds(X)

The lower this value, the more accurate the line search. It must be larger than the ValueTolerance.

◆ SetInitialDerivative()

void itk::MoreThuenteLineSearchOptimizer::SetInitialDerivative ( const DerivativeType & derivative )

overridevirtual

If initial derivative and/or value are given we can save some computation time!

Reimplemented from itk::LineSearchOptimizer.

◆ SetInitialValue()

void itk::MoreThuenteLineSearchOptimizer::SetInitialValue ( MeasureType value )

overridevirtual

Reimplemented from itk::LineSearchOptimizer.

◆ SetIntervalTolerance()

virtual void itk::MoreThuenteLineSearchOptimizer::SetIntervalTolerance ( double _arg )

virtual

Setting: the interval tolerance. By default set to the the machine precision.

If value and gradient tolerance can not be satisfied both, the algorithm stops when rounding errors prevent further progress: when the interval of uncertainty is smaller than the interval tolerance.

◆ SetMaximumNumberOfIterations()

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

virtual

◆ SetValueTolerance()

virtual void itk::MoreThuenteLineSearchOptimizer::SetValueTolerance ( double _arg )

virtual

Setting: the value tolerance. By default set to 1e-4.

The line search tries to find a StepLength that satisfies the sufficient decrease condition: F(X + StepLength * s) <= F(X) + ValueTolerance * StepLength * dF/ds(X) where s is the search direction

It must be larger than 0.0, and smaller than the GradientTolerance.

◆ StartOptimization()

void itk::MoreThuenteLineSearchOptimizer::StartOptimization ( )

override

◆ StopOptimization()

virtual void itk::MoreThuenteLineSearchOptimizer::StopOptimization ( )

virtual

◆ TestConvergence()

virtual void itk::MoreThuenteLineSearchOptimizer::TestConvergence ( bool & stop )

protectedvirtual

Check for convergence

◆ UpdateIntervalMinimumAndMaximum()

virtual void itk::MoreThuenteLineSearchOptimizer::UpdateIntervalMinimumAndMaximum ( )

protectedvirtual

Set the minimum and maximum steps to correspond to the the present interval of uncertainty.

Field Documentation

◆ m_brackt

bool itk::MoreThuenteLineSearchOptimizer::m_brackt {}

protected

Definition at line 272 of file itkMoreThuenteLineSearchOptimizer.h.

◆ m_CurrentIteration

unsigned long itk::MoreThuenteLineSearchOptimizer::m_CurrentIteration {}

protected

Definition at line 184 of file itkMoreThuenteLineSearchOptimizer.h.

◆ m_CurvatureConditionSatisfied

bool itk::MoreThuenteLineSearchOptimizer::m_CurvatureConditionSatisfied {}

protected

Definition at line 190 of file itkMoreThuenteLineSearchOptimizer.h.

◆ m_dg

double itk::MoreThuenteLineSearchOptimizer::m_dg {}

protected

Definition at line 263 of file itkMoreThuenteLineSearchOptimizer.h.

◆ m_dginit

double itk::MoreThuenteLineSearchOptimizer::m_dginit {}

protected

Definition at line 264 of file itkMoreThuenteLineSearchOptimizer.h.

◆ m_dgtest

double itk::MoreThuenteLineSearchOptimizer::m_dgtest {}

protected

Definition at line 267 of file itkMoreThuenteLineSearchOptimizer.h.

◆ m_dgx

double itk::MoreThuenteLineSearchOptimizer::m_dgx {}

protected

Definition at line 265 of file itkMoreThuenteLineSearchOptimizer.h.

◆ m_dgy

double itk::MoreThuenteLineSearchOptimizer::m_dgy {}

protected

Definition at line 266 of file itkMoreThuenteLineSearchOptimizer.h.

◆ m_f

MeasureType itk::MoreThuenteLineSearchOptimizer::m_f {}

protected

Definition at line 257 of file itkMoreThuenteLineSearchOptimizer.h.

◆ m_finit

MeasureType itk::MoreThuenteLineSearchOptimizer::m_finit {}

protected

Definition at line 260 of file itkMoreThuenteLineSearchOptimizer.h.

◆ m_fx

MeasureType itk::MoreThuenteLineSearchOptimizer::m_fx {}

protected

Definition at line 258 of file itkMoreThuenteLineSearchOptimizer.h.

◆ m_fy

MeasureType itk::MoreThuenteLineSearchOptimizer::m_fy {}

protected

Definition at line 259 of file itkMoreThuenteLineSearchOptimizer.h.

◆ m_g

DerivativeType itk::MoreThuenteLineSearchOptimizer::m_g {}

protected

Definition at line 262 of file itkMoreThuenteLineSearchOptimizer.h.

◆ m_GradientTolerance

double itk::MoreThuenteLineSearchOptimizer::m_GradientTolerance {}

private

Definition at line 279 of file itkMoreThuenteLineSearchOptimizer.h.

◆ m_InitialDerivativeProvided

bool itk::MoreThuenteLineSearchOptimizer::m_InitialDerivativeProvided {}

protected

Definition at line 185 of file itkMoreThuenteLineSearchOptimizer.h.

◆ m_InitialValueProvided

bool itk::MoreThuenteLineSearchOptimizer::m_InitialValueProvided {}

protected

Definition at line 186 of file itkMoreThuenteLineSearchOptimizer.h.

◆ m_IntervalTolerance

double itk::MoreThuenteLineSearchOptimizer::m_IntervalTolerance {}

private

Definition at line 280 of file itkMoreThuenteLineSearchOptimizer.h.

◆ m_MaximumNumberOfIterations

unsigned long itk::MoreThuenteLineSearchOptimizer::m_MaximumNumberOfIterations {}

private

Definition at line 277 of file itkMoreThuenteLineSearchOptimizer.h.

◆ m_SafeGuardedStepFailed

bool itk::MoreThuenteLineSearchOptimizer::m_SafeGuardedStepFailed {}

protected

Definition at line 274 of file itkMoreThuenteLineSearchOptimizer.h.

◆ m_stage1

bool itk::MoreThuenteLineSearchOptimizer::m_stage1 {}

protected

Definition at line 273 of file itkMoreThuenteLineSearchOptimizer.h.

◆ m_step

double itk::MoreThuenteLineSearchOptimizer::m_step {}

protected

Definition at line 251 of file itkMoreThuenteLineSearchOptimizer.h.

◆ m_stepmax

double itk::MoreThuenteLineSearchOptimizer::m_stepmax {}

protected

Definition at line 255 of file itkMoreThuenteLineSearchOptimizer.h.

◆ m_stepmin

double itk::MoreThuenteLineSearchOptimizer::m_stepmin {}

protected

Definition at line 254 of file itkMoreThuenteLineSearchOptimizer.h.

◆ m_stepx

double itk::MoreThuenteLineSearchOptimizer::m_stepx {}

protected

Definition at line 252 of file itkMoreThuenteLineSearchOptimizer.h.

◆ m_stepy

double itk::MoreThuenteLineSearchOptimizer::m_stepy {}

protected

Definition at line 253 of file itkMoreThuenteLineSearchOptimizer.h.

◆ m_Stop

bool itk::MoreThuenteLineSearchOptimizer::m_Stop {}

protected

Definition at line 188 of file itkMoreThuenteLineSearchOptimizer.h.

◆ m_StopCondition

StopConditionType itk::MoreThuenteLineSearchOptimizer::m_StopCondition {}

protected

Definition at line 187 of file itkMoreThuenteLineSearchOptimizer.h.

◆ m_SufficientDecreaseConditionSatisfied

bool itk::MoreThuenteLineSearchOptimizer::m_SufficientDecreaseConditionSatisfied {}

protected

Definition at line 189 of file itkMoreThuenteLineSearchOptimizer.h.

◆ m_ValueTolerance

double itk::MoreThuenteLineSearchOptimizer::m_ValueTolerance {}

private

Definition at line 278 of file itkMoreThuenteLineSearchOptimizer.h.

◆ m_width

double itk::MoreThuenteLineSearchOptimizer::m_width {}

protected

Definition at line 269 of file itkMoreThuenteLineSearchOptimizer.h.

◆ m_width1

double itk::MoreThuenteLineSearchOptimizer::m_width1 {}

protected

Definition at line 270 of file itkMoreThuenteLineSearchOptimizer.h.

Detailed Description

Public Types

Public Member Functions

Static Public Member Functions

Protected Member Functions

Protected Attributes

Private Attributes

Member Typedef Documentation

◆ ConstPointer

◆ Pointer

◆ Self

◆ Superclass

Member Enumeration Documentation

◆ StopConditionType

Constructor & Destructor Documentation

◆ MoreThuenteLineSearchOptimizer()

◆ ~MoreThuenteLineSearchOptimizer()

Member Function Documentation

◆ BoundStep()

◆ CheckSettings()

◆ ComputeCurrentValueAndDerivative()

◆ ComputeNewStepAndInterval()

◆ ForceSufficientDecreaseInIntervalWidth()

◆ GetClassName()

◆ GetCurrentDerivative()

◆ GetCurrentDirectionalDerivative()

◆ GetCurrentIteration()

◆ GetCurrentValue()

◆ GetCurrentValueAndDerivative()

◆ GetCurvatureConditionSatisfied()

◆ GetGradientTolerance()

◆ GetInitialValueAndDerivative()

◆ GetIntervalTolerance()

◆ GetMaximumNumberOfIterations()

◆ GetStopCondition()

◆ GetSufficientDecreaseConditionSatisfied()

◆ GetValueTolerance()

◆ InitializeLineSearch()

◆ ITK_DISALLOW_COPY_AND_MOVE()

◆ New()

◆ PrepareForUnusualTermination()

◆ PrintSelf()

◆ SafeGuardedStep()

◆ SetGradientTolerance()

◆ SetInitialDerivative()

◆ SetInitialValue()

◆ SetIntervalTolerance()

◆ SetMaximumNumberOfIterations()

◆ SetValueTolerance()

◆ StartOptimization()

◆ StopOptimization()

◆ TestConvergence()

◆ UpdateIntervalMinimumAndMaximum()

Field Documentation

◆ m_brackt

◆ m_CurrentIteration

◆ m_CurvatureConditionSatisfied

◆ m_dg

◆ m_dginit

◆ m_dgtest

◆ m_dgx

◆ m_dgy

◆ m_f

◆ m_finit

◆ m_fx

◆ m_fy

◆ m_g

◆ m_GradientTolerance

◆ m_InitialDerivativeProvided

◆ m_InitialValueProvided

◆ m_IntervalTolerance

◆ m_MaximumNumberOfIterations

◆ m_SafeGuardedStepFailed

◆ m_stage1

◆ m_step

◆ m_stepmax

◆ m_stepmin

◆ m_stepx

◆ m_stepy

◆ m_Stop