go home Home | Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Data Structures | File List | Namespace Members | Data Fields | Globals | Related Pages
Public Types | Public Member Functions | Static Public Member Functions | Protected Member Functions | Protected Attributes | Private Member Functions | Private Attributes
itk::MoreThuenteLineSearchOptimizer Class Reference

#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:
Inheritance graph
[legend]

Public Types

typedef SmartPointer< const SelfConstPointer
 
typedef Superclass::CostFunctionType CostFunctionType
 
typedef Superclass::DerivativeType DerivativeType
 
typedef Superclass::MeasureType MeasureType
 
typedef Superclass::ParametersType ParametersType
 
typedef SmartPointer< SelfPointer
 
typedef MoreThuenteLineSearchOptimizer Self
 
enum  StopConditionType {
  StrongWolfeConditionsSatisfied, MetricError, MaximumNumberOfIterations, StepTooSmall,
  StepTooLarge, IntervalTooSmall, RoundingError, AscentSearchDirection,
  Unknown
}
 
typedef LineSearchOptimizer Superclass
 
- Public Types inherited from itk::LineSearchOptimizer
typedef SmartPointer< const SelfConstPointer
 
typedef Superclass::CostFunctionType CostFunctionType
 
typedef Superclass::DerivativeType DerivativeType
 
typedef Superclass::MeasureType MeasureType
 
typedef Superclass::ParametersType ParametersType
 
typedef SmartPointer< SelfPointer
 
typedef LineSearchOptimizer Self
 
typedef SingleValuedNonLinearOptimizer Superclass
 

Public Member Functions

virtual const char * GetClassName () const
 
virtual void GetCurrentDerivative (DerivativeType &derivative) const
 
virtual double GetCurrentDirectionalDerivative (void) const
 
virtual unsigned long GetCurrentIteration () const
 
virtual MeasureType GetCurrentValue (void) const
 
virtual void GetCurrentValueAndDerivative (MeasureType &value, DerivativeType &derivative) const
 
virtual bool GetCurvatureConditionSatisfied () const
 
virtual double GetGradientTolerance () const
 
virtual double GetIntervalTolerance () const
 
virtual unsigned long GetMaximumNumberOfIterations () const
 
virtual const StopConditionTypeGetStopCondition ()
 
virtual bool GetSufficientDecreaseConditionSatisfied () const
 
virtual double GetValueTolerance () const
 
virtual void SetGradientTolerance (double _arg)
 
virtual void SetInitialDerivative (const DerivativeType &derivative)
 
virtual void SetInitialValue (MeasureType value)
 
virtual void SetIntervalTolerance (double _arg)
 
virtual void SetMaximumNumberOfIterations (unsigned long _arg)
 
virtual void SetValueTolerance (double _arg)
 
virtual void StartOptimization (void)
 
virtual void StopOptimization (void)
 
- Public Member Functions inherited from itk::LineSearchOptimizer
virtual double GetCurrentStepLength () const
 
virtual double GetInitialStepLengthEstimate () const
 
virtual const ParametersTypeGetLineSearchDirection ()
 
virtual double GetMaximumStepLength () const
 
virtual double GetMinimumStepLength () const
 
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 (void)
 
virtual void ComputeCurrentValueAndDerivative (void)
 
virtual void ComputeNewStepAndInterval (void)
 
virtual void ForceSufficientDecreaseInIntervalWidth (void)
 
virtual void GetInitialValueAndDerivative (void)
 
virtual void InitializeLineSearch (void)
 
 MoreThuenteLineSearchOptimizer ()
 
virtual void PrepareForUnusualTermination (void)
 
void PrintSelf (std::ostream &os, Indent indent) const
 
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 (void)
 
virtual ~MoreThuenteLineSearchOptimizer ()
 
- Protected Member Functions inherited from itk::LineSearchOptimizer
double DirectionalDerivative (const DerivativeType &derivative) const
 
 LineSearchOptimizer ()
 
void PrintSelf (std::ostream &os, Indent indent) const
 
virtual void SetCurrentStepLength (double step)
 
virtual ~LineSearchOptimizer ()
 

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 Member Functions

 MoreThuenteLineSearchOptimizer (const Self &)
 
void operator= (const Self &)
 

Private Attributes

double m_GradientTolerance
 
double m_IntervalTolerance
 
unsigned long m_MaximumNumberOfIterations
 
double m_ValueTolerance
 

Member Typedef Documentation

Definition at line 78 of file itkMoreThuenteLineSearchOptimizer.h.

typedef Superclass::CostFunctionType itk::MoreThuenteLineSearchOptimizer::CostFunctionType

Definition at line 86 of file itkMoreThuenteLineSearchOptimizer.h.

Definition at line 85 of file itkMoreThuenteLineSearchOptimizer.h.

Definition at line 81 of file itkMoreThuenteLineSearchOptimizer.h.

typedef Superclass::ParametersType itk::MoreThuenteLineSearchOptimizer::ParametersType

Definition at line 84 of file itkMoreThuenteLineSearchOptimizer.h.

Definition at line 77 of file itkMoreThuenteLineSearchOptimizer.h.

Definition at line 75 of file itkMoreThuenteLineSearchOptimizer.h.

Definition at line 76 of file itkMoreThuenteLineSearchOptimizer.h.

Member Enumeration Documentation

Enumerator
StrongWolfeConditionsSatisfied 
MetricError 
MaximumNumberOfIterations 
StepTooSmall 
StepTooLarge 
IntervalTooSmall 
RoundingError 
AscentSearchDirection 
Unknown 

Definition at line 88 of file itkMoreThuenteLineSearchOptimizer.h.

Constructor & Destructor Documentation

itk::MoreThuenteLineSearchOptimizer::MoreThuenteLineSearchOptimizer ( )
protected
virtual itk::MoreThuenteLineSearchOptimizer::~MoreThuenteLineSearchOptimizer ( )
inlineprotectedvirtual

Definition at line 172 of file itkMoreThuenteLineSearchOptimizer.h.

itk::MoreThuenteLineSearchOptimizer::MoreThuenteLineSearchOptimizer ( const Self )
private

Member Function Documentation

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

Force a step to be within the bounds MinimumStepLength and MaximumStepLength

virtual int itk::MoreThuenteLineSearchOptimizer::CheckSettings ( void  )
protectedvirtual

Check the input settings for errors.

virtual void itk::MoreThuenteLineSearchOptimizer::ComputeCurrentValueAndDerivative ( void  )
protectedvirtual

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

virtual void itk::MoreThuenteLineSearchOptimizer::ComputeNewStepAndInterval ( void  )
protectedvirtual

Update the interval of uncertainty and compute the new step

virtual void itk::MoreThuenteLineSearchOptimizer::ForceSufficientDecreaseInIntervalWidth ( void  )
protectedvirtual

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

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

Reimplemented from itk::LineSearchOptimizer.

virtual void itk::MoreThuenteLineSearchOptimizer::GetCurrentDerivative ( DerivativeType derivative) const
virtual
virtual double itk::MoreThuenteLineSearchOptimizer::GetCurrentDirectionalDerivative ( void  ) const
virtual
virtual unsigned long itk::MoreThuenteLineSearchOptimizer::GetCurrentIteration ( ) const
virtual

Progress information: about the state of convergence

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

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

Implements itk::LineSearchOptimizer.

virtual bool itk::MoreThuenteLineSearchOptimizer::GetCurvatureConditionSatisfied ( ) const
virtual
virtual double itk::MoreThuenteLineSearchOptimizer::GetGradientTolerance ( ) const
virtual
virtual void itk::MoreThuenteLineSearchOptimizer::GetInitialValueAndDerivative ( void  )
protectedvirtual

Load the initial value and derivative into m_f and m_g.

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

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

virtual const StopConditionType& itk::MoreThuenteLineSearchOptimizer::GetStopCondition ( )
virtual
virtual bool itk::MoreThuenteLineSearchOptimizer::GetSufficientDecreaseConditionSatisfied ( ) const
virtual
virtual double itk::MoreThuenteLineSearchOptimizer::GetValueTolerance ( ) const
virtual
virtual void itk::MoreThuenteLineSearchOptimizer::InitializeLineSearch ( void  )
protectedvirtual

Initialize the interval of uncertainty etc.

static Pointer itk::MoreThuenteLineSearchOptimizer::New ( )
static
void itk::MoreThuenteLineSearchOptimizer::operator= ( const Self )
private
virtual void itk::MoreThuenteLineSearchOptimizer::PrepareForUnusualTermination ( void  )
protectedvirtual

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

void itk::MoreThuenteLineSearchOptimizer::PrintSelf ( std::ostream &  os,
Indent  indent 
) const
protected
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.

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.

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

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

Reimplemented from itk::LineSearchOptimizer.

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

Reimplemented from itk::LineSearchOptimizer.

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.

virtual void itk::MoreThuenteLineSearchOptimizer::SetMaximumNumberOfIterations ( unsigned long  _arg)
virtual
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.

virtual void itk::MoreThuenteLineSearchOptimizer::StartOptimization ( void  )
virtual
virtual void itk::MoreThuenteLineSearchOptimizer::StopOptimization ( void  )
virtual
virtual void itk::MoreThuenteLineSearchOptimizer::TestConvergence ( bool stop)
protectedvirtual

Check for convergence

virtual void itk::MoreThuenteLineSearchOptimizer::UpdateIntervalMinimumAndMaximum ( void  )
protectedvirtual

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

Field Documentation

bool itk::MoreThuenteLineSearchOptimizer::m_brackt
protected

Definition at line 247 of file itkMoreThuenteLineSearchOptimizer.h.

unsigned long itk::MoreThuenteLineSearchOptimizer::m_CurrentIteration
protected

Definition at line 176 of file itkMoreThuenteLineSearchOptimizer.h.

bool itk::MoreThuenteLineSearchOptimizer::m_CurvatureConditionSatisfied
protected

Definition at line 182 of file itkMoreThuenteLineSearchOptimizer.h.

double itk::MoreThuenteLineSearchOptimizer::m_dg
protected

Definition at line 238 of file itkMoreThuenteLineSearchOptimizer.h.

double itk::MoreThuenteLineSearchOptimizer::m_dginit
protected

Definition at line 239 of file itkMoreThuenteLineSearchOptimizer.h.

double itk::MoreThuenteLineSearchOptimizer::m_dgtest
protected

Definition at line 242 of file itkMoreThuenteLineSearchOptimizer.h.

double itk::MoreThuenteLineSearchOptimizer::m_dgx
protected

Definition at line 240 of file itkMoreThuenteLineSearchOptimizer.h.

double itk::MoreThuenteLineSearchOptimizer::m_dgy
protected

Definition at line 241 of file itkMoreThuenteLineSearchOptimizer.h.

MeasureType itk::MoreThuenteLineSearchOptimizer::m_f
protected

Definition at line 232 of file itkMoreThuenteLineSearchOptimizer.h.

MeasureType itk::MoreThuenteLineSearchOptimizer::m_finit
protected

Definition at line 235 of file itkMoreThuenteLineSearchOptimizer.h.

MeasureType itk::MoreThuenteLineSearchOptimizer::m_fx
protected

Definition at line 233 of file itkMoreThuenteLineSearchOptimizer.h.

MeasureType itk::MoreThuenteLineSearchOptimizer::m_fy
protected

Definition at line 234 of file itkMoreThuenteLineSearchOptimizer.h.

DerivativeType itk::MoreThuenteLineSearchOptimizer::m_g
protected

Definition at line 237 of file itkMoreThuenteLineSearchOptimizer.h.

double itk::MoreThuenteLineSearchOptimizer::m_GradientTolerance
private

Definition at line 258 of file itkMoreThuenteLineSearchOptimizer.h.

bool itk::MoreThuenteLineSearchOptimizer::m_InitialDerivativeProvided
protected

Definition at line 177 of file itkMoreThuenteLineSearchOptimizer.h.

bool itk::MoreThuenteLineSearchOptimizer::m_InitialValueProvided
protected

Definition at line 178 of file itkMoreThuenteLineSearchOptimizer.h.

double itk::MoreThuenteLineSearchOptimizer::m_IntervalTolerance
private

Definition at line 259 of file itkMoreThuenteLineSearchOptimizer.h.

unsigned long itk::MoreThuenteLineSearchOptimizer::m_MaximumNumberOfIterations
private

Definition at line 256 of file itkMoreThuenteLineSearchOptimizer.h.

bool itk::MoreThuenteLineSearchOptimizer::m_SafeGuardedStepFailed
protected

Definition at line 249 of file itkMoreThuenteLineSearchOptimizer.h.

bool itk::MoreThuenteLineSearchOptimizer::m_stage1
protected

Definition at line 248 of file itkMoreThuenteLineSearchOptimizer.h.

double itk::MoreThuenteLineSearchOptimizer::m_step
protected

Definition at line 226 of file itkMoreThuenteLineSearchOptimizer.h.

double itk::MoreThuenteLineSearchOptimizer::m_stepmax
protected

Definition at line 230 of file itkMoreThuenteLineSearchOptimizer.h.

double itk::MoreThuenteLineSearchOptimizer::m_stepmin
protected

Definition at line 229 of file itkMoreThuenteLineSearchOptimizer.h.

double itk::MoreThuenteLineSearchOptimizer::m_stepx
protected

Definition at line 227 of file itkMoreThuenteLineSearchOptimizer.h.

double itk::MoreThuenteLineSearchOptimizer::m_stepy
protected

Definition at line 228 of file itkMoreThuenteLineSearchOptimizer.h.

bool itk::MoreThuenteLineSearchOptimizer::m_Stop
protected

Definition at line 180 of file itkMoreThuenteLineSearchOptimizer.h.

StopConditionType itk::MoreThuenteLineSearchOptimizer::m_StopCondition
protected

Definition at line 179 of file itkMoreThuenteLineSearchOptimizer.h.

bool itk::MoreThuenteLineSearchOptimizer::m_SufficientDecreaseConditionSatisfied
protected

Definition at line 181 of file itkMoreThuenteLineSearchOptimizer.h.

double itk::MoreThuenteLineSearchOptimizer::m_ValueTolerance
private

Definition at line 257 of file itkMoreThuenteLineSearchOptimizer.h.

double itk::MoreThuenteLineSearchOptimizer::m_width
protected

Definition at line 244 of file itkMoreThuenteLineSearchOptimizer.h.

double itk::MoreThuenteLineSearchOptimizer::m_width1
protected

Definition at line 245 of file itkMoreThuenteLineSearchOptimizer.h.



Generated on 04-09-2015 for elastix by doxygen 1.8.9.1 elastix logo