RVLUmin::BacktrackingLineSearchAlg< Scalar > Class Template Reference

Factory class for BacktrackingLineSearchAlgBase implementation of backtracking line search. More...

#include <lnsrchBT.hh>

Inheritance diagram for RVLUmin::BacktrackingLineSearchAlg< Scalar >:

List of all members.

Public Member Functions
	BacktrackingLineSearchAlg (int _maxsteps=10, bool _DispFlag=false, Scalar firststep=1.0, Scalar minsteptol=numeric_limits< Scalar >::epsilon(), Scalar _eta1=0.01, Scalar _eta2=0.5, Scalar _gamma1=0.5, Scalar _gamma2=1.8, Scalar _fudge=0.9, ostream &_str=cout)
	Constructor arguments:.
	BacktrackingLineSearchAlg (BacktrackingLineSearchAlg< Scalar > const &bt)
	copy constructor
	~BacktrackingLineSearchAlg ()
Protected Member Functions
virtual LineSearchAlgBase< Scalar > *	build (FunctionalEvaluation< Scalar > &fx, Vector< Scalar > const &dx, Scalar firststep)

---

Detailed Description

template<typename Scalar>
class RVLUmin::BacktrackingLineSearchAlg< Scalar >

Factory class for BacktrackingLineSearchAlgBase implementation of backtracking line search.

Subclasses RVLUmin::LineSearchAlg abstract factory: build method accepts RVL::FunctionalEvaluation (function evaluated at current estimate of solution), RVL::Vector (step), both mutable references, and first step Scalar, and returns pointer to dynamically allocated BacktrackingLineSearchAlgBase object.

Data members (initialized in constructor) define a backtracking line search:

• firststep = initial step, stored by base class (RVLUmin::LineSearchAlg) and updated to last successful step with each run of line search
• minsteptol = minimum permitted step, stored by base class (RVLUmin::LineSearchAlg) and used to sanity-test step. Typical value = 0.01
• eta1 = lower G-A parameter: if actual reduction in objective is less than eta1 * (linear prediction of reduction), then no update, step *= gamma1 ("backtracking"); else, step is (provisionally) accepted, pending internal doubling test (next bullet). Typical value = 0.01
• eta2 = upper G-A parameter: if actual reduction in objective is greater than eta2 * (linear prediction of reduction) AND this occurs on first line search step, then (a) step *= gamma2, (b) update recomputed, until either max line search iterates reached or eta2 test fails. At end of this "internal doubling" loop, step is accepted if eta1 test passes, else previous internal doubling update is accepted. Typical value = 0.9
• gamma1 = step decrease factor. Typical value = 0.5
• gamma2 = step increase factor. Typical value = 1.8
• DispFlag = verbosity flag. Typical value = true
• fudge = max fraction of max step to permit. Typical value = 0.9
• maxsteps = max number of line search steps. Typical value = 10
• str = verbose output stream

Constraints on parameters:

• 0 < eta1 < eta2 < 1
• 0 < gamma1 < 1 < gamma2
• gamma1*gamma2<1 (to prevent cycling)
• 0 < firststep < numeric_limits<Scalar>::max()

Typical values: eta1=0.01, eta2=0.5, gamma1=0.5, gamma2=1.8, firststep=1.0, fudge=0.9, maxsteps=10.

The problematic choice is firststep - it depends on scales in the problem which are opaque from the point of view of this algorithm. In principle, the algorithm can recover from a bad choice of scale by either backtracking or internal doubling, but in practice this process can consume an indordinate number of function evaluations. The initial value of firststep should reflect whatever is known about the probable distance between the initial estimate of the solution and the actual optimizer.

Definition at line 422 of file lnsrchBT.hh.

---

Constructor & Destructor Documentation

template<typename Scalar>

RVLUmin::BacktrackingLineSearchAlg< Scalar >::BacktrackingLineSearchAlg	(	int	_maxsteps = 10,
		bool	_DispFlag = false,
		Scalar	firststep = 1.0,
		Scalar	minsteptol = numeric_limits<Scalar>::epsilon(),
		Scalar	_eta1 = 0.01,
		Scalar	_eta2 = 0.5,
		Scalar	_gamma1 = 0.5,
		Scalar	_gamma2 = 1.8,
		Scalar	_fudge = 0.9,
		ostream &	_str = cout
	)

Constructor arguments:.

Parameters:

	firststep	initial step, stored by RVLUmin::LineSearchAlg base class
	minsteptol	minimum permitted step, stored by RVLUmin::LineSearchAlg base class
	_eta1	lower G-A parameter > 0
	_eta2	upper G-A parameter > eta1
	_gamma1	trust region reduction factor < 1
	_gamma2	trust region expansion factor > 1, gamma1*gamma2 < 1
	_DispFlag	verbosity flag
	_fudge	fraction of max step to permit
	_maxsteps	max number of line search steps
	_str	verbose output unit

Definition at line 463 of file lnsrchBT.hh.

template<typename Scalar>

RVLUmin::BacktrackingLineSearchAlg< Scalar >::BacktrackingLineSearchAlg

(

BacktrackingLineSearchAlg< Scalar > const &

bt

)

copy constructor

Definition at line 484 of file lnsrchBT.hh.

template<typename Scalar>

RVLUmin::BacktrackingLineSearchAlg< Scalar >::~BacktrackingLineSearchAlg

(

)

Definition at line 495 of file lnsrchBT.hh.

---

Member Function Documentation

template<typename Scalar>

virtual LineSearchAlgBase<Scalar>* RVLUmin::BacktrackingLineSearchAlg< Scalar >::build	(	FunctionalEvaluation< Scalar > &	fx,
		Vector< Scalar > const &	dx,
		Scalar	firststep
	)			[protected, virtual]

Implements RVLUmin::LineSearchAlg< Scalar >.

Definition at line 438 of file lnsrchBT.hh.

---

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

• lnsrchBT.hh

---