PrimalDual Class Reference

#include <PrimalDual.h>

Inheritance diagram for PrimalDual:

Public Member Functions
	PrimalDual (SubGrad *slvr, istream *iStrm=0)
void	SetVOLLog (ostream *outs=0, const char lvl=0)
void	Format (void)
void	NewDEF (void)
void	NewStep (void)
HpNum	GetDFLCoeff (void)
HpNum	GetStepsize (bool StepIsIncr=false)
HpNum	GetLev (void)
HpNum	GetBeta (void)
void	SetMaxBeta (const HpNum alpha)
Public Member Functions inherited from Deflection
	Deflection (SubGrad *slvr)
virtual void	SetVOLLog (std::ostream *outs=0, const char lvl=0)
virtual bool	DoSS (void)
virtual HpNum	Delta (void)
Public Member Functions inherited from Stepsize
	Stepsize (SubGrad *slvr, istream *iStrm=0)
virtual void	SetSTPLog (std::ostream *outs=0, const char lvl=0)
virtual bool	NeedsdkM1Gk (void)

Private Member Functions
void	UpdateGamma (void)

Private Attributes
HpNum	delta
HpNum	Tmpdelta
HpNum	vk
HpNum	StepSize
HpNum	gamma
HpNum	beta1
bool	average
HpNum	LipCnst

Additional Inherited Members
Protected Member Functions inherited from Deflection
FiOracle *	GetOracle (void)
HpNum	GetStepsize (void)
HpNum	GetGiNorm (void)
HpNum	GetDNorm (void)
HpNum	GetdGk (void)
HpNum	GetSigma (void)
HpNum	GetEpsilon (void)
HpNum	ReadFVal (void)
Protected Member Functions inherited from Stepsize
virtual bool	UpdateTargetLevel (void)
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 inherited from Deflection
SubGrad *	Solver
	(pointer to) the SubGrad solver
std::ostream *	VOLLog
	the output stream object
char	VOLLLvl
	the "level of verbosity"
Protected Attributes inherited from Stepsize
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

Definition of the class PrimalDual. This class implements two variants of the Primal-Dual subgradient method (PDSM): simple and weighted averages, under a unified SM scheme. The method has a fixed stability center, and the direction \( d_i \) can be regarded as the average of all the previous weighted subgradients, i.e.:

\[ d_i = ( \sum_{k=1}^i \upsilon_k g_k) / \Delta_i \quad,\quad \Delta_i = \sum_{k=1}^i \upsilon_k \]

It is worth mentioning that the subgradient weights \(\upsilon_k \) can be non-vanishing as \(k\rightarrow \infty\). The stepsize rule (SR) and the deflection rule (DR), respectively, are:

\[ \alpha_i = \upsilon_i / \Delta_i \quad,\quad \nu_i = \Delta_i / \omega_i \]

where \(\omega_i\) is chosen in a suitable way.

Constructor & Destructor Documentation

PrimalDual()

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

inline

Constructor of the class, which derives from both Deflection and Stepsize. Since the constructor of PrimalDual is executed after the one of Stepsize, the following parameters specific for PrimalDual have to be found in the stream after those of the base class Stepsize [see the comments to the constructor of Stepsize]:

1. bool average [true] if true simple averages are used, otherwise weighted averages are used

For this class, the general parameter LpsFct -defined in Stepsize.h- represents the gamma factor F used to set \(\omega_i\).

Member Function Documentation

Format()

void Format ( void )

inlinevirtual

The method initializes the DR. It does nothing for the base class.

Reimplemented from Deflection.

GetBeta()

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 from Stepsize.

GetDFLCoeff()

HpNum GetDFLCoeff ( void )

inlinevirtual

Returns the deflection coefficient. This function must be called after NewDEF() [see above].

Implements Deflection.

GetLev()

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 from Stepsize.

GetStepsize()

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 from Stepsize.

NewDEF()

void NewDEF ( void )

inlinevirtual

The variant requires thats DR must be computed before SR. Hence, the call to NewDEF comes before the one to NewStep.

Implements Deflection.

NewStep()

void NewStep ( void )

inlinevirtual

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()].

Implements Stepsize.

SetMaxBeta()

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 from Stepsize.

---

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

• SubGrad/Deflection/PrimalDual.h