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

ITK version of the MoreThuente line search algorithm. More...

#include <itkMoreThuenteLineSearchOptimizer.h>

Inheritance diagram for itk::MoreThuenteLineSearchOptimizer:
Inheritance graph
[legend]
Collaboration diagram for itk::MoreThuenteLineSearchOptimizer:
Collaboration 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 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)

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

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

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 67 of file itkMoreThuenteLineSearchOptimizer.h.


Member Typedef Documentation

Reimplemented from itk::LineSearchOptimizer.

Definition at line 73 of file itkMoreThuenteLineSearchOptimizer.h.

Reimplemented from itk::LineSearchOptimizer.

Definition at line 81 of file itkMoreThuenteLineSearchOptimizer.h.

Reimplemented from itk::LineSearchOptimizer.

Definition at line 80 of file itkMoreThuenteLineSearchOptimizer.h.

Reimplemented from itk::LineSearchOptimizer.

Definition at line 76 of file itkMoreThuenteLineSearchOptimizer.h.

Reimplemented from itk::LineSearchOptimizer.

Definition at line 79 of file itkMoreThuenteLineSearchOptimizer.h.

Reimplemented from itk::LineSearchOptimizer.

Definition at line 72 of file itkMoreThuenteLineSearchOptimizer.h.

Reimplemented from itk::LineSearchOptimizer.

Definition at line 70 of file itkMoreThuenteLineSearchOptimizer.h.

Reimplemented from itk::LineSearchOptimizer.

Definition at line 71 of file itkMoreThuenteLineSearchOptimizer.h.


Member Enumeration Documentation

Enumerator:
StrongWolfeConditionsSatisfied 
MetricError 
MaximumNumberOfIterations 
StepTooSmall 
StepTooLarge 
IntervalTooSmall 
RoundingError 
AscentSearchDirection 
Unknown 

Definition at line 83 of file itkMoreThuenteLineSearchOptimizer.h.


Constructor & Destructor Documentation

itk::MoreThuenteLineSearchOptimizer::MoreThuenteLineSearchOptimizer ( ) [protected]
virtual itk::MoreThuenteLineSearchOptimizer::~MoreThuenteLineSearchOptimizer ( ) [inline, protected, virtual]

Definition at line 160 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  ) [protected, virtual]

Check the input settings for errors.

virtual void itk::MoreThuenteLineSearchOptimizer::ComputeCurrentValueAndDerivative ( void  ) [protected, virtual]

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

virtual void itk::MoreThuenteLineSearchOptimizer::ComputeNewStepAndInterval ( void  ) [protected, virtual]

Update the interval of uncertainty and compute the new step

virtual void itk::MoreThuenteLineSearchOptimizer::ForceSufficientDecreaseInIntervalWidth ( void  ) [protected, virtual]

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  ) [protected, virtual]

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  ) [protected, virtual]

Initialize the interval of uncertainty etc.

static Pointer itk::MoreThuenteLineSearchOptimizer::New ( ) [static]
void itk::MoreThuenteLineSearchOptimizer::operator= ( const Self ) [private]

Reimplemented from itk::LineSearchOptimizer.

virtual void itk::MoreThuenteLineSearchOptimizer::PrepareForUnusualTermination ( void  ) [protected, virtual]

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]

Reimplemented from itk::LineSearchOptimizer.

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 [protected, virtual]

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) [protected, virtual]

Check for convergence

virtual void itk::MoreThuenteLineSearchOptimizer::UpdateIntervalMinimumAndMaximum ( void  ) [protected, virtual]

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


Field Documentation

Definition at line 235 of file itkMoreThuenteLineSearchOptimizer.h.

Definition at line 164 of file itkMoreThuenteLineSearchOptimizer.h.

Definition at line 170 of file itkMoreThuenteLineSearchOptimizer.h.

Definition at line 226 of file itkMoreThuenteLineSearchOptimizer.h.

Definition at line 227 of file itkMoreThuenteLineSearchOptimizer.h.

Definition at line 230 of file itkMoreThuenteLineSearchOptimizer.h.

Definition at line 228 of file itkMoreThuenteLineSearchOptimizer.h.

Definition at line 229 of file itkMoreThuenteLineSearchOptimizer.h.

Definition at line 220 of file itkMoreThuenteLineSearchOptimizer.h.

Definition at line 223 of file itkMoreThuenteLineSearchOptimizer.h.

Definition at line 221 of file itkMoreThuenteLineSearchOptimizer.h.

Definition at line 222 of file itkMoreThuenteLineSearchOptimizer.h.

Definition at line 225 of file itkMoreThuenteLineSearchOptimizer.h.

Definition at line 245 of file itkMoreThuenteLineSearchOptimizer.h.

Definition at line 165 of file itkMoreThuenteLineSearchOptimizer.h.

Definition at line 166 of file itkMoreThuenteLineSearchOptimizer.h.

Definition at line 246 of file itkMoreThuenteLineSearchOptimizer.h.

Definition at line 243 of file itkMoreThuenteLineSearchOptimizer.h.

Definition at line 237 of file itkMoreThuenteLineSearchOptimizer.h.

Definition at line 236 of file itkMoreThuenteLineSearchOptimizer.h.

Definition at line 214 of file itkMoreThuenteLineSearchOptimizer.h.

Definition at line 218 of file itkMoreThuenteLineSearchOptimizer.h.

Definition at line 217 of file itkMoreThuenteLineSearchOptimizer.h.

Definition at line 215 of file itkMoreThuenteLineSearchOptimizer.h.

Definition at line 216 of file itkMoreThuenteLineSearchOptimizer.h.

Definition at line 168 of file itkMoreThuenteLineSearchOptimizer.h.

Definition at line 167 of file itkMoreThuenteLineSearchOptimizer.h.

Definition at line 169 of file itkMoreThuenteLineSearchOptimizer.h.

Definition at line 244 of file itkMoreThuenteLineSearchOptimizer.h.

Definition at line 232 of file itkMoreThuenteLineSearchOptimizer.h.

Definition at line 233 of file itkMoreThuenteLineSearchOptimizer.h.



Generated on 24-10-2011 for elastix by doxygen 1.7.4 elastix logo