BFGSFitter Class Reference

#include <BFGSFitter.h>

Inheritance diagram for BFGSFitter:

[legend]Collaboration diagram for BFGSFitter:

[legend]List of all members.

Detailed Description

The minimization algorithm used is a complementary quasi newton algorithm, with BFGS (Broyden-Fletcher-Goldfarb-Shanno) update and hence the name BFGSFitter.

The entire minimization algorithm relies heavily on the description given in Numerical Optimization by Jorge Nocedal, Stephen J. Wright Publisher: Springer Verlag; (August 27, 1999) ISBN: 0387987932). In the following description we will refer to this book a number of times.

Author:: Kaustuv <kaustuv@stanford.edu>

Definition at line 31 of file BFGSFitter.h.

Public Member Functions

BFGSFitter (const char *name)

The constructor taking name of fitter as argument.

virtual bool calcBestFit ()

Main driver routine for BFGS algorithm which has been used in computing the bets fit for the function.

virtual int calcCovariance (std::vector< std::vector< double > > &cov)

Calculates the covariance matrix.

virtual int calcDegreesOfFreedom () const

Returns the number of degrees of freedom in the fit.

Fitter * clone () const

Makes a copy of the receiving object.

void fillFreeParameters (std::vector< double > &) const

Fills the vector with the free parameters values.

double function (const std::vector< double > &x) const

The objective function.

StatedFCN * getFCN ()

Returns the objective function object.

virtual const std::vector<
int > & getFixedFlags () const

Returns a vector containing flags for which parameters are to be held fixed during objective function minimization.

std::vector< double > gradient (const std::vector< double > &x) const

The gradient of the objective function.

double gradp (const std::vector< double > &u, const std::vector< double > &p) const

Efficient computation of gradient of the objective function with a vector p.

const std::vector< double > & initIter () const

Returns the initial value of the iterate.

double interpolate (const std::vector< double > &x0, const std::vector< double > &p, double Alphaim, double Alphai) const

A cubic interpolation routine.

double iterParam (std::string name)

Given a string, this function returns the value of the associated iteration parameter.

const std::string & name () const

Returns the name of the fitter.

virtual bool needsDerivatives () const

Returns false as this fitter does not need the function to calculate its partial derivatives.

virtual double objectiveValue () const

Calculates the value of the objective function at the current set of parameters.

void setFCN (StatedFCN *fcn)

Sets the objective function object.

virtual void setFitCut (TupleCut *cut)

Sets the cut to limit range of fitting.

virtual void setFitRange (bool yes=true)

Sets use of a fitting range on or off.

virtual void setFixedFlags (const std::vector< int > &flags)

Sets the parameters that are to be held fixed during objective function minimization.

int setInitIter (const std::vector< double > &xinit)

Sets the initial value of the iterate, assuming it is given as a vector.

int setIterParam (std::string name, double value)

Given a string and a double, this function sets the value of the associated iteration parameter.

void setLimits (const std::string &name, double lower, double upper)

Sets the limits for the parameter of the model function with name name.

virtual void setLimits (unsigned int i, double lower, double upper)

Sets the limits for the parameter of the model function indexed by i.

void setStepSize (const std::string &name, double size)

Sets the minimization step size for model function parameter name.

virtual void setStepSize (unsigned int i, double size)

Sets the step size for parameter of the minimization.

double wolfeStep (const std::vector< double > &x0, const std::vector< double > &p) const

Computes a step satisfying the Wolfe conditions.

double zoom (const std::vector< double > &x0, const std::vector< double > &p, double phi0, double dphi0, double Alphalo, double Alphahi) const

A function which helps out Wolfe in deciding the step length.

Protected Attributes

StatedFCN * m_fcn

The objective function.

int m_max_iterations

The maximum number of iterations allowed in attempting the fit.

std::string m_name

The name of the fitter.

Private Attributes

double m_alpha1

First step length to try and this must be less than Alpha_max.

double m_alpha_max

Maximum step length to try, suggested value by Nocedal and Wright is alpha_max = 4.

double m_c1

c1,c2 - constants such that 0 < c1 < c2 < 1 and they ensure that strong Wolfe conditions hold true.

double m_c2

c1,c2 - constants such that 0 < c1 < c2 < 1 and they ensure that strong Wolfe conditions hold true.

double m_grad_cutoff

The gradient cut-off parameter.

std::map< std::string, double * > m_iter_params

Map of the various iteration parameters to their name.

std::vector< std::vector<
double > > m_M

The inverse of the quasi-hessian.

double m_proj_cutoff

The projection cut-off parameter.

double m_step_cutoff

The step cut-off parameter.

std::vector< double > m_xinit

The initial value to start the iteration from.

Constructor & Destructor Documentation

BFGSFitter::BFGSFitter ( const char * name )

The constructor taking name of fitter as argument.

Definition at line 57 of file BFGSFitter.cxx.
References m_alpha1, m_alpha_max, m_c1, m_c2, m_grad_cutoff, m_iter_params, m_proj_cutoff, and m_step_cutoff.
Referenced by clone().

Member Function Documentation

bool BFGSFitter::calcBestFit ( ) [virtual]

Main driver routine for BFGS algorithm which has been used in computing the bets fit for the function.

Implements Fitter.
Definition at line 89 of file BFGSFitter.cxx.
References std::abs(), hippodraw::Numeric::eye(), Fitter::fillFreeParameters(), function(), gradient(), hippodraw::Numeric::innerProduct(), Fitter::m_fcn, m_grad_cutoff, m_M, Fitter::m_max_iterations, m_proj_cutoff, m_step_cutoff, m_xinit, norm, hippodraw::Numeric::outerProduct(), setInitIter(), and wolfeStep().

int BFGSFitter::calcCovariance ( std::vector< std::vector< double > > & cov ) [virtual]

Calculates the covariance matrix.
Returns EXIT_SUCCESS if a minima of the log likelihood functions is found, returns EXIT_FAILURE in case algorithm converges on other stationary points (i.e. on saddle points).
Reimplemented from Fitter.
Definition at line 472 of file BFGSFitter.cxx.
References hippodraw::Numeric::cholFactor(), m_M, and m_xinit.

int Fitter::calcDegreesOfFreedom ( ) const [virtual, inherited]

Returns the number of degrees of freedom in the fit.

Definition at line 165 of file Fitter.cxx.
References Fitter::m_fcn.
Referenced by FunctionProjector::degreesOfFreedom(), and hippodraw::Python::export_Fitter().

Fitter * BFGSFitter::clone ( ) const [virtual]

Makes a copy of the receiving object.
Makes copy of receiving object by creating a new one with the only constructor.
Attention:
Objects created with this function may not be complete until the setFCN member function is called.

Implements Fitter.
Definition at line 77 of file BFGSFitter.cxx.
References BFGSFitter().

void Fitter::fillFreeParameters ( std::vector< double > & ) const [inherited]

Fills the vector with the free parameters values.

Definition at line 68 of file Fitter.cxx.
References Fitter::m_fcn.
Referenced by LMFitter::calcBestFit(), and calcBestFit().

double BFGSFitter::function ( const std::vector< double > & x ) const

The objective function.

Definition at line 319 of file BFGSFitter.cxx.
References Fitter::m_fcn, and Fitter::objectiveValue().
Referenced by calcBestFit(), interpolate(), wolfeStep(), and zoom().

StatedFCN * Fitter::getFCN ( ) [inherited]

Returns the objective function object.

Definition at line 54 of file Fitter.cxx.
References Fitter::m_fcn.
Referenced by hippodraw::Python::export_Fitter().

const vector< int > & Fitter::getFixedFlags ( ) const [virtual, inherited]

Returns a vector containing flags for which parameters are to be held fixed during objective function minimization.

Definition at line 82 of file Fitter.cxx.
References Fitter::m_fcn.
Referenced by MinuitMigrad::calcBestFit().

vector< double > BFGSFitter::gradient ( const std::vector< double > & x ) const

The gradient of the objective function.

Definition at line 351 of file BFGSFitter.cxx.
References Fitter::m_fcn, and Fitter::objectiveValue().
Referenced by calcBestFit().

double BFGSFitter::gradp ( const std::vector< double > & u,

const std::vector< double > & p

) const

Efficient computation of gradient of the objective function with a vector p.

Definition at line 404 of file BFGSFitter.cxx.
References Fitter::m_fcn, and Fitter::objectiveValue().
Referenced by interpolate(), wolfeStep(), and zoom().

const vector< double > & BFGSFitter::initIter ( ) const

Returns the initial value of the iterate.

Definition at line 453 of file BFGSFitter.cxx.
References m_xinit.

double BFGSFitter::interpolate ( const std::vector< double > & x0,

const std::vector< double > & p,

double Alphaim,

double Alphai

) const

A cubic interpolation routine.

Definition at line 287 of file BFGSFitter.cxx.
References std::abs(), function(), gradp(), std::sqrt(), and std::swap().
Referenced by zoom().

double BFGSFitter::iterParam ( std::string name )

Given a string, this function returns the value of the associated iteration parameter.
Names of the various iteration parameters have been chosen according to the following simple rule. m_foo_bar is called foo_bar.
Definition at line 494 of file BFGSFitter.cxx.
References m_iter_params, and Fitter::m_max_iterations.

const std::string & Fitter::name ( ) const [inherited]

Returns the name of the fitter.

Definition at line 61 of file Fitter.cxx.
References Fitter::m_name.
Referenced by hippodraw::Python::export_Fitter(), and MinuitMigrad::initialize().

bool BFGSFitter::needsDerivatives ( ) const [virtual]

Returns false as this fitter does not need the function to calculate its partial derivatives.

Implements Fitter.
Definition at line 84 of file BFGSFitter.cxx.

double Fitter::objectiveValue ( ) const [virtual, inherited]

Calculates the value of the objective function at the current set of parameters.

Definition at line 158 of file Fitter.cxx.
References Fitter::m_fcn.
Referenced by LMFitter::calcBestFit(), hippodraw::Python::export_Fitter(), function(), gradient(), gradp(), and FunctionProjector::objectiveValue().

void Fitter::setFCN ( StatedFCN * fcn ) [inherited]

Sets the objective function object.
Sets the objective function object to be used and takes possession of it. That is, will delete the current object, if there is one, and will delete the object in this object's destructor.
Definition at line 45 of file Fitter.cxx.
References Fitter::m_fcn.

void Fitter::setFitCut ( TupleCut * cut ) [virtual, inherited]

Sets the cut to limit range of fitting.

Definition at line 179 of file Fitter.cxx.
References Fitter::m_fcn.

void Fitter::setFitRange ( bool yes = true ) [virtual, inherited]

Sets use of a fitting range on or off.

Definition at line 186 of file Fitter.cxx.
References Fitter::m_fcn.

void Fitter::setFixedFlags ( const std::vector< int > & flags ) [virtual, inherited]

Sets the parameters that are to be held fixed during objective function minimization.

Definition at line 75 of file Fitter.cxx.
References Fitter::m_fcn.
Referenced by hippodraw::Python::export_Fitter().

int BFGSFitter::setInitIter ( const std::vector< double > & xinit )

Sets the initial value of the iterate, assuming it is given as a vector.

Definition at line 458 of file BFGSFitter.cxx.
References m_xinit.
Referenced by calcBestFit().

int BFGSFitter::setIterParam ( std::string name,

double value

)

Given a string and a double, this function sets the value of the associated iteration parameter.
Names of the various parameters have been chosen according to the following simple rule. m_foo_bar is called foo_bar.
Definition at line 514 of file BFGSFitter.cxx.
References m_iter_params, and Fitter::m_max_iterations.

void Fitter::setLimits ( const std::string & name,

double lower,

double upper

) [inherited]

Sets the limits for the parameter of the model function with name name.

Definition at line 123 of file Fitter.cxx.
References Fitter::getParameterIndex(), and Fitter::setLimits().

void Fitter::setLimits ( unsigned int i,

double lower,

double upper

) [virtual, inherited]

Sets the limits for the parameter of the model function indexed by i.

Reimplemented in MinuitMigrad.
Definition at line 89 of file Fitter.cxx.
References Fitter::m_name.
Referenced by hippodraw::Python::export_Fitter(), and Fitter::setLimits().

void Fitter::setStepSize ( const std::string & name,

double size

) [inherited]

Sets the minimization step size for model function parameter name.

Definition at line 151 of file Fitter.cxx.
References Fitter::getParameterIndex(), and Fitter::setStepSize().

void Fitter::setStepSize ( unsigned int i,

double size

) [virtual, inherited]

Sets the step size for parameter of the minimization.
This base class implementation throws FitterException. Derived classes that suport setting step size should override this member function.
Reimplemented in MinuitMigrad.
Definition at line 141 of file Fitter.cxx.
References Fitter::m_name.
Referenced by hippodraw::Python::export_Fitter(), and Fitter::setStepSize().

double BFGSFitter::wolfeStep ( const std::vector< double > & x0,

const std::vector< double > & p

) const

Computes a step satisfying the Wolfe conditions.
Based on Algorithm 3.2 (Line Search Algorithm) on pp. 58--60 of "Numerical Optimization" by Jorge Nocedal and Stephen J. Wright
Definition at line 171 of file BFGSFitter.cxx.
References std::abs(), function(), gradp(), m_alpha1, m_alpha_max, m_c1, m_c2, std::min(), std::sqrt(), and zoom().
Referenced by calcBestFit().

double BFGSFitter::zoom ( const std::vector< double > & x0,

const std::vector< double > & p,

double phi0,

double dphi0,

double Alphalo,

double Alphahi

) const

A function which helps out Wolfe in deciding the step length.
Based on Algorithm 3.3 (zoom) on pg. 60 of "Numerical Optimization" by Jorge Nocedal and Stephen J. Wright
Definition at line 234 of file BFGSFitter.cxx.
References std::abs(), function(), gradp(), interpolate(), m_c1, and m_c2.
Referenced by wolfeStep().

Member Data Documentation

double BFGSFitter::m_alpha1 [private]

First step length to try and this must be less than Alpha_max.
(typically Alpha1 = 1 for Newton's method and relatives)
Definition at line 83 of file BFGSFitter.h.
Referenced by BFGSFitter(), and wolfeStep().

double BFGSFitter::m_alpha_max [private]

Maximum step length to try, suggested value by Nocedal and Wright is alpha_max = 4.

Definition at line 79 of file BFGSFitter.h.
Referenced by BFGSFitter(), and wolfeStep().

double BFGSFitter::m_c1 [private]

c1,c2 - constants such that 0 < c1 < c2 < 1 and they ensure that strong Wolfe conditions hold true.
Strong Wolfe conditions:
f(x_k + Alpha_k * p_k) <= f(x_k) + c1 * Alpha_k * grad f(x_k)'*p_k (1) |grad f(x_k + Alpha_k * p_k)'*p_k| >= c2 * grad f(x_k)' * p_k (2)
The lower the c2 value, the closer you are asking the algorithm to get to an actual local minimum. The lower the c1 value, the sole demand being made is that the direction be a direction of descent.
Nocedal and Wright suggest use of following: c1 = 1e-4; c2 = 0.9;
Definition at line 75 of file BFGSFitter.h.
Referenced by BFGSFitter(), wolfeStep(), and zoom().

double BFGSFitter::m_c2 [private]

c1,c2 - constants such that 0 < c1 < c2 < 1 and they ensure that strong Wolfe conditions hold true.
Strong Wolfe conditions:
f(x_k + Alpha_k * p_k) <= f(x_k) + c1 * Alpha_k * grad f(x_k)'*p_k (1) |grad f(x_k + Alpha_k * p_k)'*p_k| >= c2 * grad f(x_k)' * p_k (2)
The lower the c2 value, the closer you are asking the algorithm to get to an actual local minimum. The lower the c1 value, the sole demand being made is that the direction be a direction of descent.
Nocedal and Wright suggest use of following: c1 = 1e-4; c2 = 0.9;
Definition at line 75 of file BFGSFitter.h.
Referenced by BFGSFitter(), wolfeStep(), and zoom().

StatedFCN* Fitter::m_fcn [protected, inherited]

The objective function.

Definition at line 55 of file Fitter.h.
Referenced by LMFitter::calcAlpha(), MinuitMigrad::calcBestFit(), LMFitter::calcBestFit(), calcBestFit(), Fitter::calcDegreesOfFreedom(), MinuitMigrad::checkIndex(), Fitter::fillFreeParameters(), Fitter::Fitter(), function(), Fitter::getFCN(), Fitter::getFixedFlags(), Fitter::getParameterIndex(), gradient(), gradp(), MinuitMigrad::initialize(), Fitter::objectiveValue(), Fitter::setFCN(), Fitter::setFitCut(), Fitter::setFitRange(), Fitter::setFixedFlags(), and Fitter::~Fitter().

double BFGSFitter::m_grad_cutoff [private]

The gradient cut-off parameter.
If two successive iterations change the the norm of the gradient of Likelihood function less than this quantity, then iteration is terminated
Definition at line 48 of file BFGSFitter.h.
Referenced by BFGSFitter(), and calcBestFit().

std::map< std::string, double * > BFGSFitter::m_iter_params [private]

Map of the various iteration parameters to their name.

Definition at line 86 of file BFGSFitter.h.
Referenced by BFGSFitter(), iterParam(), and setIterParam().

std::vector< std::vector< double > > BFGSFitter::m_M [private]

The inverse of the quasi-hessian.

Definition at line 40 of file BFGSFitter.h.
Referenced by calcBestFit(), and calcCovariance().

int Fitter::m_max_iterations [protected, inherited]

The maximum number of iterations allowed in attempting the fit.

Definition at line 58 of file Fitter.h.
Referenced by LMFitter::calcBestFit(), calcBestFit(), LMFitter::iterParam(), iterParam(), LMFitter::setIterParam(), and setIterParam().

std::string Fitter::m_name [protected, inherited]

The name of the fitter.

Definition at line 47 of file Fitter.h.
Referenced by MinuitMigrad::checkIndex(), Fitter::name(), Fitter::setLimits(), and Fitter::setStepSize().

double BFGSFitter::m_proj_cutoff [private]

The projection cut-off parameter.
If the projection of step on the gradient is less than this quantity, then iteration is terminated
Definition at line 57 of file BFGSFitter.h.
Referenced by BFGSFitter(), and calcBestFit().

double BFGSFitter::m_step_cutoff [private]

The step cut-off parameter.
If the two successive iterations result in the norm of difference of iterates less than this quantity, then iteration is terminated
Definition at line 53 of file BFGSFitter.h.
Referenced by BFGSFitter(), and calcBestFit().

std::vector< double > BFGSFitter::m_xinit [private]

The initial value to start the iteration from.

Definition at line 43 of file BFGSFitter.h.
Referenced by calcBestFit(), calcCovariance(), initIter(), and setInitIter().

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

Generated for HippoDraw-1.14.8.5 by

1.4.3


Public Member Functions
	BFGSFitter (const char *name)
	The constructor taking name of fitter as argument.
virtual bool	calcBestFit ()
	Main driver routine for BFGS algorithm which has been used in computing the bets fit for the function.
virtual int	calcCovariance (std::vector< std::vector< double > > &cov)
	Calculates the covariance matrix.
virtual int	calcDegreesOfFreedom () const
	Returns the number of degrees of freedom in the fit.
Fitter *	clone () const
	Makes a copy of the receiving object.
void	fillFreeParameters (std::vector< double > &) const
	Fills the vector with the free parameters values.
double	function (const std::vector< double > &x) const
	The objective function.
StatedFCN *	getFCN ()
	Returns the objective function object.
virtual const std::vector< int > &	getFixedFlags () const
	Returns a vector containing flags for which parameters are to be held fixed during objective function minimization.
std::vector< double >	gradient (const std::vector< double > &x) const
	The gradient of the objective function.
double	gradp (const std::vector< double > &u, const std::vector< double > &p) const
	Efficient computation of gradient of the objective function with a vector p.
const std::vector< double > &	initIter () const
	Returns the initial value of the iterate.
double	interpolate (const std::vector< double > &x0, const std::vector< double > &p, double Alphaim, double Alphai) const
	A cubic interpolation routine.
double	iterParam (std::string name)
	Given a string, this function returns the value of the associated iteration parameter.
const std::string &	name () const
	Returns the name of the fitter.
virtual bool	needsDerivatives () const
	Returns `false` as this fitter does not need the function to calculate its partial derivatives.
virtual double	objectiveValue () const
	Calculates the value of the objective function at the current set of parameters.
void	setFCN (StatedFCN *fcn)
	Sets the objective function object.
virtual void	setFitCut (TupleCut *cut)
	Sets the cut to limit range of fitting.
virtual void	setFitRange (bool yes=true)
	Sets use of a fitting range on or off.
virtual void	setFixedFlags (const std::vector< int > &flags)
	Sets the parameters that are to be held fixed during objective function minimization.
int	setInitIter (const std::vector< double > &xinit)
	Sets the initial value of the iterate, assuming it is given as a vector.
int	setIterParam (std::string name, double value)
	Given a string and a double, this function sets the value of the associated iteration parameter.
void	setLimits (const std::string &name, double lower, double upper)
	Sets the limits for the parameter of the model function with name name.
virtual void	setLimits (unsigned int i, double lower, double upper)
	Sets the limits for the parameter of the model function indexed by i.
void	setStepSize (const std::string &name, double size)
	Sets the minimization step size for model function parameter name.
virtual void	setStepSize (unsigned int i, double size)
	Sets the step size for parameter of the minimization.
double	wolfeStep (const std::vector< double > &x0, const std::vector< double > &p) const
	Computes a step satisfying the Wolfe conditions.
double	zoom (const std::vector< double > &x0, const std::vector< double > &p, double phi0, double dphi0, double Alphalo, double Alphahi) const
	A function which helps out Wolfe in deciding the step length.
Protected Attributes
StatedFCN *	m_fcn
	The objective function.
int	m_max_iterations
	The maximum number of iterations allowed in attempting the fit.
std::string	m_name
	The name of the fitter.
Private Attributes
double	m_alpha1
	First step length to try and this must be less than Alpha_max.
double	m_alpha_max
	Maximum step length to try, suggested value by Nocedal and Wright is alpha_max = 4.
double	m_c1
	c1,c2 - constants such that 0 < c1 < c2 < 1 and they ensure that strong Wolfe conditions hold true.
double	m_c2
	c1,c2 - constants such that 0 < c1 < c2 < 1 and they ensure that strong Wolfe conditions hold true.
double	m_grad_cutoff
	The gradient cut-off parameter.
std::map< std::string, double * >	m_iter_params
	Map of the various iteration parameters to their name.
std::vector< std::vector< double > >	m_M
	The inverse of the quasi-hessian.
double	m_proj_cutoff
	The projection cut-off parameter.
double	m_step_cutoff
	The step cut-off parameter.
std::vector< double >	m_xinit
	The initial value to start the iteration from.