Stepsize Class Reference

#include <Stepsize.h>

Inheritance diagram for Stepsize:

Public Member Functions
Constructor
	Stepsize (SubGrad *slvr, istream *iStrm=0)
Other initializations
virtual void	SetSTPLog (std::ostream *outs=0, const char lvl=0)
virtual void	Format (void)
Stepsize computation
virtual void	NewStep (void)=0
virtual bool	NeedsdkM1Gk (void)
Reading the solution
virtual HpNum	GetStepsize (bool StepIsIncr=false)
virtual HpNum	GetLev (void)
virtual HpNum	GetBeta (void)
Adding / removing / changing data
virtual void	SetMaxBeta (const HpNum alpha)
Destructor

Protected Member Functions
virtual bool	UpdateTargetLevel (void)
Protected methods to read from Subgrad
These methods are used to provide access to the information stored into the SubGrad object. Stepsize is a "friend" of SubGrad and therefore it can read its protected data structures, but classes derived from Stepsize are not friend of SubGrad and cannot. This is why these methods are defined in the base class (and implemented in SubGrad.C).
HpNum	GetCoeffDefl (void)
FiOracle *	GetOracle (void)
HpNum	GetGiNorm (void)
HpNum	GetDNorm (void)
HpNum	GetdGk (void)
HpNum	GetdkM1Gk (void)
Index	GetNItIcr (void)
HpNum	ReadFkVal (void)
HpNum	ReadFiBar (void)

Protected Attributes
SubGrad *	Solver
	(pointer to) the SubGrad solver
std::ostream *	STPLog
	the output stream object
char	STPLLvl
	the "level of verbosity"
HpNum	FiLev
	the target level \( f^{lev}_i \)
HpNum	Beta
	beta factor \( \beta_i \)
HpNum	MaxBeta
	maximum value for beta factor
HpNum	LpsFct
	scaling factor

Detailed Description

The class Stepsize provides an interface for the stepsize rule, to be used in the SubGrad solver [see SubGrad.h].

The main functions of the class are NewStep() and GetStepsize(). While NewStep() sets up a new step, the value \(\nu_i\) is passed to the SubGrad solver by means of a call to GetStepsize().

The user must extend the class to one or more stepsize rules following this interface.

Constructor & Destructor Documentation

Stepsize()

Stepsize ( SubGrad * slvr, istream * iStrm = 0 )

inline

Constructor of the class. The parameter ‘iStrm’, if provided, is taken as a pointer to a istream from which the algorithmic parameters for the stepsize formula are sequentially read in the following order. Each must be placed at the beginning of a separate line, max 255 characters long, with all the rest of the line up to the first newline character '
' (apart from a separating whitespace) being available for comments. Any line whose first character is '#' and any blank line is ignored. If 0 is passed, the file ends before reaching a given parameter, or some parameter is in the wrong format, each non-specified parameter is given a default value, shown in [] below.

Only a few parameters are deemed to be general enough to be put in the basic Stepsize class; however, the same stream can be used for passing the (possibly many more) algorithmic parameters to the derived classes. Since the constructor of Stepsize is executed before the ones of the derived classes, the specific parameters for the derived classes have just to be found in the stream after those of the base class.

HpNum LpsFct [1] a general scaling factor (for instance, it is the Lipschitz factor in the target value SR)

Member Function Documentation

Format()

virtual void Format ( void )

inlinevirtual

The method initializes the stepsize rule.

Reimplemented in ColorTV, FumeroTV, Polyak, and PrimalDual.

GetBeta()

virtual HpNum GetBeta ( void )

inlinevirtual

This function must be called after NewStep() [see above].

The default implementation returns the scalar \( \beta_i \) for a target value stepsize rule [see below]. It should throw exception for other forms of the stepsize rule.

Reimplemented in PrimalDual.

GetCoeffDefl()

HpNum GetCoeffDefl ( void )

protected

Returns the deflection coefficient \(\alpha_i\).

GetdGk()

HpNum GetdGk ( void )

protected

Returns the scalar product \( g_i^{\top} d_i\).

GetdkM1Gk()

HpNum GetdkM1Gk ( void )

protected

Returns the scalar product \( g_i^{\top} d_{i-1}\).

GetDNorm()

HpNum GetDNorm ( void )

protected

Returns the norm of the direction \( d_i \).

GetGiNorm()

HpNum GetGiNorm ( void )

protected

Returns the norm of the subgradient \( g_i \).

GetLev()

virtual HpNum GetLev ( void )

inlinevirtual

This function must be called after NewStep() [see above].

The default implementation returns the level \( f^{lev}_i \) for a target value stepsize rule [see below]. It should throw exception for other forms of the stepsize rule.

Reimplemented in PrimalDual.

GetNItIcr()

Index GetNItIcr ( void )

protected

Returns NItIncr, the parameter for incremental iterations [see SubGrad.h].

GetOracle()

FiOracle * GetOracle ( void )

protected

Returns the pointer to FiOracle. Thus, stepsize can ask directly the FiOracle object for the function information.

GetStepsize()

virtual HpNum GetStepsize ( bool StepIsIncr = false )

inlinevirtual

This function must be called after NewStep() [see above ] and returns the step value. StepIsIncr controls the stepsize formula in the incremental version.

The base class provides the step value for target stepsize rules, by exploiting \( beta_k \) and \( f^{lev}_k \) computed by NewStep(). While for non-incremental step (StepIsIncr = false) for \( k = 1, 2 , \ldots \) the formula is

\[ \nu_k = \beta_k * ( f_k - f^{lev}_k ) / \| d_k \|^2\,, \]

for incremental step (StepIsIncr = true) for \( k = p(\Pi+1) , \ldots , (p+1)(\Pi+1) - 1 , p = 0, 1 , 2 \ldots \) the stepsize rule is

\[ \nu_k = \beta_k \frac{ f_{ p(\Pi + 1 ) } - f^{lev}_{ p( \Pi + 1 ) } } { \chi( \Pi + 1 ) C^2 } \]

where \( \chi \) is the LpsFct factor and \( C \) is the Lipschitz constant.

Note that GetStepsize() only returns the value, the actual step computation being done by NewStep().

Reimplemented in PrimalDual.

NeedsdkM1Gk()

virtual bool NeedsdkM1Gk ( void )

inlinevirtual

Returns true if the stepsize requires the scalar product \( d_{i-1}^{\top} g_i\). The default implementation don't require this value.

Reimplemented in ColorTV.

NewStep()

virtual void NewStep ( void )

pure virtual

This method must be called before GetStepsize() [see below]. This is indeed the core of every derived class, producing a new step.

If the derived class implements a target value stepsize rule, the method must compute both the scalar \( \beta_i \) and the level \( f^{lev}_i \).

Typically, the previous step will be unavailable after the call to NewStep() [see GetStepsize()].

Implemented in ColorTV, FumeroTV, Polyak, and PrimalDual.

ReadFiBar()

HpNum ReadFiBar ( void )

protected

Returns FiBar [ see SubGrad.h ].

ReadFkVal()

HpNum ReadFkVal ( void )

protected

Returns FiLambda [ see SubGrad.h ].

SetMaxBeta()

virtual void SetMaxBeta ( const HpNum alpha )

inlinevirtual

Changes the maximum value of \( \beta_i \) for a target value stepsize rule.

Typically, the method implements the safe rule of the stepsize-restricted approach. Passing the deflection coefficient \( \alpha_i \) does exactly this job.

Reimplemented in PrimalDual.

SetSTPLog()

virtual void SetSTPLog ( std::ostream * outs = 0, const char lvl = 0 )

inlinevirtual

The class outputs "log" information onto the ostream pointed by outs. lvl controls the "level of verbosity" of the code: lvl == 0 means that nothing at all is printed, and values larger than 0 mean increasing amounts of information, the specific effect of each value being derived- class-dependent. outs == 0 implies lvl == 0.

UpdateTargetLevel()

virtual bool UpdateTargetLevel ( void )

inlineprotectedvirtual

It tries to provide a new target level \( f^{lev}_i \). It true is returned, the level has been changed. By default, it returns false.

Reimplemented in ColorTV, FumeroTV, and Polyak.

---

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

• SubGrad/Stepsize.h