NDOSolver / FiOracle: SubGrad Class Reference

#include <SubGrad.h>

Inheritance diagram for SubGrad:

Public Types
Public Types
enum	SGParam { kSGPar1 = kLastNDOParam , kSGPar2 , kSGPar3 , kSGPar4 , kSGPar5 }

Public Types inherited from NDOSolver
enum	NDOParam { kMaxItr = 0 , kMaxTme , ktStar , kEpsLin , kEInit , kEFnal , kEDcrs , kEStps , kLastNDOParam }

enum	NDOStatus { kOK = 0 , kUnbndd , kUnfsbl , kStopped , kLwPrcsn , kStpIter , kStpTime , kError }

Public Member Functions
Constructor
	SubGrad (std::istream *iStrm=0)

Other initializations
void	SetStepsize (Stepsize *STP=nullptr)

void	SetDeflection (Deflection *Vol=nullptr)

void	SetFiOracle (FiOracle *Fi=nullptr)

void	SetLambda (cLMRow tLambda=nullptr)

void	KeepBestLambda (const bool KBL=true)

void	SetPar (const int wp, const int value)

void	SetPar (const int wp, cHpNum value)

void	SetPar (const int wp, const bool value)

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

Solving the problem
@ --------------------------------------------------------------------—
NDOStatus	Solve (void)

void	ReSetAlg (unsigned char RstLvl=0)

Reading the solution
cLMRow	ReadBestSol (cIndex_Set &I, Index &D)

HpNum	ReadBestFiVal (cIndex wFi=Inf< Index >())

cLMRow	ReadSol (cIndex_Set &I, Index &D)

HpNum	ReadFiVal (cIndex wFi=Inf< Index >())

HpNum	ReadHatFiVal (void)

bool	IsOptimal (HpNum eps=0)

cHpRow	ReadMult (cIndex_Set &I, Index &D, cIndex wFi=Inf< Index >())

HpNum	ReadLBMult (cIndex wFi=Inf< Index >())

Reading the data of the problem
void	GetPar (const int wp, int &value)

void	GetPar (const int wp, HpNum &value)

void	GetPar (const int wp, bool &value)

Adding / removing / changing data
void	AddVariables (Index NNwVrs, cLMRow IVs=0)

void	RemoveVariables (cIndex_Set whch=0, Index hwmny=0)

void	ChgFiV (cIndex wFi=Inf< Index >())

void	ChgSbG (cIndex strt=0, Index stp=Inf< Index >(), cIndex wFi=Inf< Index >())

Destructor
Public Member Functions inherited from NDOSolver
	NDOSolver (std::istream *iStrm=0)

virtual void	SetNDOLog (ostream *outs=0, const char lvl=0)

virtual void	SetNDOTime (const bool TimeIt=true)

virtual bool	IsOptimal (HpNum eps=0) const

Index	FiEval (void) const

Index	GiEval (void) const

Index	NrCalls (void) const

Index	NrIter (void) const

void	NDOTime (double &t_us, double &t_ss)

double	NDOTime (void)

Index	GetNumVar (void) const

virtual	~NDOSolver ()

Protected Member Functions
void	FiAndGi (cIndex wFi=Inf< Index >())

void	FormD (void)

void	SaveDir (void)

void	GotoLambda1 (void)

void	FormLambda1 (void)

Protected Attributes
Index	SGPar1
	projection-strategy parameters

HpNum	SGPar2
	incremental factor

Index	SGPar3
	scheme: stepsize(deflection)-restricted

bool	SGPar4
	control if $ \hat{\lambda}_i $ is kept

Index	SGPar5
	seed

Stepsize *	stepsize
	pointer to the Stepsize class

Deflection *	deflection
	pointer to the Deflection class

Index	MaxNumVar
	maximum number of variables

LMRow	LambdaBar
	the stability center $\bar{\lambda}_i$

HpNum	FiBar
	full function value at LambdaBar

LMRow	Lambda

HpNum	FiLambda
	full function value at Lambda

LMRow	LambdaHat
	the point $ \hat{\lambda}_i $

HpNum	FiHat
	full function value at HLmb

bool	LHasChgd

bool	LHasProj

bool	KpBstL
	if LambdaBest has to be kept

HpNum	FiBest
	the best value of $f$ found so far

LMRow	LambdaBest
	the best point found so far

HpNum	LowerBound
	Lower Bound over the full function $f$.

bool	TrueLB

SgRow	Gi
	Gi[ wFi ]( Lambda ), the subgradient.

SgRow	dir
	the direction $ d_i $

HpNum	alpha
	the deflection parameter $ \alpha_i $

HpNum	step
	the stepsize $ \nu_i $

HpNum	Sigma

HpNum	Epsilon

HpNum	SigmaHat

HpNum	HatEpsilon

Index_Set	SGBase
	the set of indices of Gi[ wFi ]( Lambda )

HpNum	NrmGi
	the (squared) subgradient's norm

HpNum	NrmDir
	the (squared) direction's norm

HpNum	dGk
	scalar product $ < d_i , g_i > $

HpNum	dM1Gk
	scalar product $ < d_{i-1} , g_i > $

bool	dM1GkDone

LMRow	ub
	upper bounds on the variables

LMRow	lb
	lower bounds on the variables

std::mt19937	myrandom
	random generator for incremental steps

bool	ZeroComp
	true if Fi() comes with the 0-th component

Index	NItIncr

bool	InnIter
	if true, the current iteration is an inner one

vector< Index >	Seq

bool	DirPos

Index_Set	MultBse

Index	CSSCntr
	counter of consecutive SS

Index	CNSCntr
	counter of consecutive NS

Index	CSmallStep
	counter of consecutive short step

bool	DoSS
	SS vs NS.

FiOracle::FiStatus	fs
	FiOracle status.

bool	EmptySet
	true, if the feasible set is empty

Protected Attributes inherited from NDOSolver
FiOracle *	Oracle
	(pointer to) the oracle for Fi

Index	MaxIter
	maximum number of iterations

HpNum	MaxTime
	maximum time (in seconds) for each call to Solve()

HpNum	tStar
	optimality related parameter: "scaling" of Fi

HpNum	EpsLin
	optimality related parameter: relative precision

HpNum	EInit
	precision-related parameter: initial precision

HpNum	EFnal
	precision-related parameter: final precision

HpNum	EDcrs
	precision-related parameter: rate of decrease

int	EStps
	precision-related parameter: number of steps

NDOStatus	Result
	result of the latest call to Solve()

Index	NumVar
	(current) number of variables

Index	NrFi
	number of components of Fi()

Index	SCalls
	nuber of calls to Solve() (the current included)

Index	ParIter
	nuber of iterations in this run

Index	FiEvaltns
	total number of Fi() calls

Index	GiEvaltns
	total number of Gi() calls

ostream *	NDOLog
	the output stream object for log purposes

char	NDOLLvl
	the "level of verbosity" of the log

OPTtimers *	NDOt
	OPTtimer for timing purposes.

Private Member Functions
void	Log1 (void)

void	Log2 (void)

void	Log3 (void)

void	Log4 (void)

void	AllocateUBLB (cIndex strt, cIndex num)

LMNum	lbnd (cIndex i)

LMNum	ubnd (cIndex i)

void	EvalGi (Index wFi=Inf< Index >())

bool	ProjFsb (LMRow Lpt, bool &EmptySet)

void	ProjTng (SgRow Gpt, cLMRow Lpt, cIndex strt=0, Index stp=Inf< Index >())

void	InitStepsize (void)

void	InitDeflection (void)

void	ChgLambdaHat (void)

void	UpdateSigma (void)

void	UpdtLowerBound (void)

void	MemDealloc (void)

Friends
Friend classes
class	Stepsize

class	Deflection

Detailed Description

The SubGrad class implements the NDOSolver interface for NonDifferentiable Optimization Solvers, using a unified subgradient-type algorithm as described in:

A. Frangioni, E. Gorgone, B. Gendron. "On the Computational Efficiency of Subgradient Methods: a Case Study with Lagrangian Bounds" Mathematical Programming Computation 9(4), 573-604, 2017

This is in fact a subgradient method (SM) based on abstract rules for the computation of both the stepsize $\nu_i$ and the direction $d_i$. The algorithm in employs the simple recurrence formula:

\[ \breve{\lambda}_{i+1} \gets \bar{\lambda}_i - \nu_i d_i \quad , \quad \lambda_{i+1} \gets {\rm P}_{\Lambda}( \, \breve{\lambda}_{i+1} \, ) \]

where ${\rm P}$ denotes the orthogonal projection on $\bar{\Lambda}$. The point $\bar{\lambda}_i$ is not necessarily the current iterate. For instance, it could be required that $\bar{\lambda}_{i}$ remains unchanged if an ascent direction occurs. It recalls somehow the stability center of the bundle methods. The class relies on the objects of the friend classes Stepsize and Deflection, which have to return, respectively, the stepsize $\nu_i$ and the deflection coefficient $\alpha_i$. The latter scalar number defines in turn the direction $d_i$, i.e.. $ d_i = \alpha_i g_i + (1-\alpha_i)d_{i-1} $. These abstract classes allow us to derive several variants of the method. For the sake of simplicity, the original SM characterized by $\alpha_i = 1$ is performed setting the pointer to the object Deflection to nullptr. The class also includes the incremental variant for when the function to be maximized is composed by a sum of different functions.

Member Enumeration Documentation

◆ SGParam

enum SGParam

Public enum which "extends" the enum NDOSolver::NDOParam for handling the SubGrad-specific algorithmic parameters in (the two overloaded versions of) SubGrad::SetPar() [see below].

Constructor & Destructor Documentation

◆ SubGrad()

SubGrad ( std::istream * iStrm = 0 )

Constructor of the class. The parameter ‘iStrm’, if provided, is taken as a pointer to a istream from which the algorithmic parameters for the subgradient algorithm are sequentially read in the following order. Each parameter 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.

‘iStrm’ is passed to the constructor of NDOSolver [see NDOSolver.h], which reads the general algorithmic parameters out of it; since the constructor SubGrad is executed after the one of NDOSolver, the following parameters specific for the SubGrad have to be found in the stream after those of the base class:

Index SGPar1 [0] The direction $d_i$ is assumed to be such a convex combination of the subgradient $g_i$ and the direction $d_{i-1}$:
\[ d_i = \alpha_i g_i + ( 1 - \alpha_i ) d_{i-1} \]

SGPar1 selects among $\{d_i,d_{i-1},g_i\} $ the vector(s) to be projected over the tangent cone at $\bar{\lambda}_i$. The field SGPar1 is coded bit-wise, in the following way:
- bit 0: if 1 the subgradient $g_i$ is projected, 0 otherwise;
- bit 1: if 1 the direction $d_{i-1}$ is projected, 0 otherwise;
- bit 2: if 1 the $d_{i}$ is projected, 0 otherwise;
The setting (+7) is redundant. In fact, it is equivalent to (+3) because $d_i$, being a (convex) combination of $g_i$ and $d_{i-1}$, coincides with its projection.
HpNum SGPar2 [0] To manage the incremental iterations. A sequence of incremental (or inner) iterations NItIncr performed along single-component subgradients could occur before a full (or normal, or outer) iteration. The number NItIncr is obtained as NItIncr = ceil( <Number of components of $f$> * SGPar2 ), where the number of components of $f$ includes the 0-th component, and then not necessarily coincides with NrFi. Finally, the incremental variant only works with no deflection object, i.e setting deflection = NULL, because we do not manage with the sum of subgradients of different components.
Index SGPar3 [1] The convergence scheme. This field is coded bit-wise in the following way:
- bit 0: 1 if the safe rule is used, 0 otherwise
- bit 1: 1 for the stepsize-restricted scheme, 0 for the deflection-restricted scheme.
bool SGPar4 [true] SGPar4 enables the use of
\[ \hat{\lambda}_{i+1} = \alpha_{i+1}\lambda_i + ( 1 - \alpha_{i+1} ) \hat{\lambda}_i \]
which could have a certain influence on the stopping test [see IsOptimal()].
Index SGPar5 [0] The seed value used in a call to srand. The components are re-shuffled in the incremental variant, and a random number generator is used.

Member Function Documentation

◆ AddVariables()

void AddVariables	(	Index	NNwVrs,
		cLMRow	IVs = 0 )

virtual

Adds ‘NNwVrs’ new variables to the NDO problem. The new variables are added at the end of the current variable set, i.e., their "names" will be set to NumVar , ... , NumVar + NNwVrs - 1 (where ‘NumVar’ means "the number of variables *before* the call"). The total number of variables after the call will be < NumVar + NNwVrs when NumVar + NNwVrs > FiOracle::GetMaxNumVar() [see FiOracle.h].

IVs is a NNwVrs-vector containing the initial values for the newly created variables; IVs == 0 means that all the initial values are 0.

After a call to this method, a different function, on a different variable space, has to be minimized. Of course, the two functions must not be unrelated to one another; more specifically, it is required that the new function Fi( Lambda , LambdaNew ) is identical to the old function Fi( Lambda ) when restricted to the old space, i.e. that

Fi( Lambda , 0 ) = Fi( Lambda ) for all Lambda.

This implies, for instance, that all the previously collected subgradients are still subgradients for the restriction of the new Fi() to the subspace where all the new variables are zero. We also require that the every subgradient of the old Fi() can be extended to a subgradient of the new Fi() by just "filling in" the entries corresponding to the new variables with proper values (this is always possible e.g. for polyhedral functions). In other words, if the linear function

L( Lambda ) = G * Lambda + a

is known to minorize the old Fi(), then there must exist NewG such that

L( Lambda , LambdaNew ) = G * Lambda + NewG * LambdaNew + a

minorizes the new Fi(). Even better than that, the "linearization error" of L() at any point Lambda

Fi( Lambda ) - L( Lambda ) >= 0

is identical to the linearization error of the new L() at [ Lambda , 0 ]

Fi( Lambda , 0 ) - L( Lambda , 0 ) >= 0.

Then, the NDOSolver can use GetGi() [see FiOracle.h] to retrieve the new entries NewG for the newly created variables of the items "recorded" in the FiOracle, if it needs so, while all the already fetched information remains valid. Note that, if IVs == 0, the value of the function in the new point [ Lambda , 0 ] is also known.

Therefore, a call to this method assumes that the FiOracle already knows about the new set of variables to be created. In particular, the NDOSolver can use GetGi() as outlined above, and it can also use GetUB() and GetUC() [see FiOracle.h] to retrieve the lower and upper bounds on the variables; also, the NDOSolver can assume that, when the method is called, Oracle->GetNumVar() [see FiOracle.h] already returns the number of variables after the addiction of the new NNwVrs ones. Note that the likely caller for AddVariables() is the FiOracle itself; this is one of the reasons why the FiOracle may need a pointer to the NDOSolver that is using it [see SetNDOSolver() in FiOracle.h]. If AddVariables() is not directly called by the FiOracle, the caller must ensure that the FiOracle has been properly updated before calling the method. Note that this requirement is, for obvious reasons, opposite to what is assumed for RemoveVariables() [see below].

This operation is typically useful in the case of Lagrangian optimization where the set of relaxed constraints A( x ) [<]= b is very large, leading to a very-large-scale NDO problem. Such a problem could be tackled with a row generation scheme, i.e., working with only an "active subset" of the full set of constraints and revising it as necessary. In this setting, adding variables corresponds to inserting new relaxed constraints in the current active set.

Reimplemented from NDOSolver.

◆ ChgFiV()

void ChgFiV ( cIndex wFi = Inf< Index >() )

virtual

This method signals to the NDO solver that there have been changes in the function Fi. These changes are such that the previously obtained information about the function is not completely useless, but it needs to be properly updated. If 0 <= wFi <= NrFi, the NDO solver is told that only the wFi-th component of Fi has changed; if Inf< Index >() > wFi > NrFi then all the components except the 0-th have changed, while if wFi == Inf< Index >() then all the components, comprised the 0-th, have changed.

The class of changes that are signalled by ChgFiV() are those where only the Fi-values are affected, but not the first-order information. In the Lagrangian case, they correspond to = changes in the objective function c( x ) of the Lagrangian problem, or = changes in the feasible set X of the Lagrangian problem.

In both cases, the first-order information (subgradient/constraint) corresponding to a particular dual solution/dual extreme ray x that has been previously generated can be re-used. If c( x ) changes, the old information given by x is still meaningful for the new Fi provided that it is properly translated [see GetVal() in FiOracle.h]. For the linear 0-th component, this corresponds to a change of the constant ‘b0’. If X changes, x can either be feasible/an extreme ray or not; if it is, then the old item associated to x is still valid for Fi with no changes, otherwise it should probably be discarded, which is signalled by GetVal() returning - INF.

In both cases, the changes that are needed to update the information are given by just one number for each dual solution x, which can be queried by means of the method GetVal() of class FiOracle. Of course, this means that the FiOracle already knows about the change. Indeed, the most likely caller for ChgFi() is the FiOracle itself; this is one of the reasons why the FiOracle may need a pointer to the NDOSolver that is using it [see SetNDOSolver() in FiOracle.h]. If ChgFiV() is not directly called by the FiOracle, the caller must ensure that the FiOracle has been properly informed before calling the method.

Reimplemented from NDOSolver.

◆ ChgSbG()

void ChgSbG	(	cIndex	strt = 0,
		Index	stp = Inf< Index >(),
		cIndex	wFi = Inf< Index >() )

virtual

ChgSbG() signals that the first-order information relative to the variables with "names" comprised between strt and min( stp , NumVar ) - 1 for the specified components has changed. The changes are intended not to involve the Fi-values, i.e., if Fi-values change together with the first-order information then a separate call to ChgFiV() [see above] is required. In the Lagrangian case, changes to the first-order information correspond to changes in the constraints ‘A[ h ]()’/ right hand side ‘b’ (note that these changes are typically accompanied by changes of the Fi-values).

A call to this method assumes that the FiOracle already knows about the changes. In particular, the NDOSolver can use GetGi() [see FiOracle.h] to retrieve the new values for the changed entries of the items of the specified components of Fi, if it needs so. Indeed, the likely caller for ChgSbG() is the FiOracle itself; this is one of the reasons why the FiOracle may need a pointer to the NDOSolver that is using it [see SetNDOSolver() in FiOracle.h]. If ChgSbG() is not directly called by the FiOracle, the caller must ensure that the FiOracle has been properly updated before calling the method.

Reimplemented from NDOSolver.

◆ FiAndGi()

void FiAndGi ( cIndex wFi = Inf< Index >() )

protected

Evaluates the function at the new point $\lambda_{i+1}$, i.e., $f(\lambda_{i+1})$, and it either computes a subgradient $g_{i+1} \in \partial f(\lambda_{i+1})$, or, if the point is infeasible, a constraint.

◆ FormD()

void FormD ( void )

protected

The method is used within Solve(), and its job is to compute the direction $d_i$ that appears in the formula of $\lambda_{i+1}$. The direction is actually saved after the variables generation because i) the subgradient keeps in memory just the current direction, and ii) by generating/removing variables the direction may quickly come to be deteriorated. When the variables generation is ended [see GetFiStatus() in FiOracle.h], SaveDir() must be called in order to update the direction.

In addition, the deflection coefficient is computed inside FormD(). As for the stepsize, the computation is performed within FormD() only if the scheme is deflection-restricted.

◆ FormLambda1()

void FormLambda1 ( void )

protected

After a (successful) call to FormD(), sets the new (unprojected) tentative point $\breve{\lambda}_{i+1}$ as

\[ \breve{\lambda}_{i+1} = \lambda_i - \nu_i d_i \,. \]

Remark that the point $\breve{\lambda}_{i+1}$ must be projected before calling FiandGi() [see above], i.e., $ \lambda_{i+1} = {\rm P}_{\Lambda} ( \breve{\lambda}_{i+1} ) $.

◆ GetPar() [1/2]

void GetPar	(	const int	wp,
		HpNum &	value )

inlinevirtual

Read the current value of the "float" algorithmic parameters of the NDO solver [see SetPar() above].

Reimplemented from NDOSolver.

◆ GetPar() [2/2]

void GetPar	(	const int	wp,
		int &	value )

inlinevirtual

Read the current value of the "int" algorithmic parameters of the NDO solver [see SetPar() above].

Reimplemented from NDOSolver.

◆ GotoLambda1()

void GotoLambda1 ( void )

protected

Move the current point to $\lambda_{i+1}$.

◆ IsOptimal()

bool IsOptimal ( HpNum eps = 0 )

Returns true if the solution $\bar{\lambda}_i$ is $\epsilon$-optimal (relative), being $\epsilon $ set to EpsLin. The parameter SGPar4 controls the linearization error to be used in the stopping condition:

SGPar4 = true:
\[ t^* \|d_i\| + \max\{ \hat{\epsilon}_i , \epsilon_i \} <= \epsilon * max( 1 , |f_i^{rec}| ) \]
SGPar4 = false: The criteria is just
\[ t^* \|d_i\| + \epsilon_i <= \epsilon * max( 1 , |f_i^{rec}| ) \]

where $ f^{rec}_i = \min \{ \, f_l \,:\, l = 1, \ldots, i \, \}$, i.e. the record value on the optimum $f_*$

◆ KeepBestLambda()

void KeepBestLambda ( const bool KBL = true )

virtual

Reimplemented from NDOSolver.

◆ ReadBestFiVal()

HpNum ReadBestFiVal ( cIndex wFi = Inf< Index >() )

virtual

Returns the best $f$ value found so far. Independently from which "component" of Fi() is chosen, it returns the full function.

Reimplemented from NDOSolver.

◆ ReadBestSol()

cLMRow ReadBestSol	(	cIndex_Set &	I,
		Index &	D )

virtual

Returns a read-only pointer to the point having the lowest $f$ value found so far [see below].

Reimplemented from NDOSolver.

◆ ReadFiVal()

HpNum ReadFiVal ( cIndex wFi = Inf< Index >() )

virtual

Independently from which "component" of Fi() is chosen, it returns the full function Fi at the stability center $\bar{\lambda}_i$.

Implements NDOSolver.

◆ ReadHatFiVal()

HpNum ReadHatFiVal ( void )

Returns $\hat{f}$, if $ \hat{\lambda}_i $ is kept in memory. Otherwise it returns Inf< HpNum >().

◆ ReadLBMult()

HpNum ReadLBMult ( cIndex wFi = Inf< Index >() )

virtual

Some NDO algorithms may exploit the knowledge of Lower Bounds on the optimal value of the function [see GetLowerBound() in FiOracle.h] as a whole, or of its components. These bound can be thought as all-0 subgradients, and therefore they have a dual multiplier associated; think to the case when the LB is the optimal value of the function, so that the dual multiplier of the (all-0 subgradient associated to the) LB is 1. This method returns the value of the optimal dual multiplier associated to the LB; if 1 <= wFi <= NrFi the LB is that on the wFi-th component of Fi, otherwise the LB is that on the whole function.

Note: The multipliers returned by ReadMult( wFi ) [see above] should sum to 1 - ReadLBMult( wFi ) - ReadLBMult(), except when wFi == 1 so that two multipliers are the same and the sum must be 1 - ReadLBMult().; For "easy" components of Fi() [see FiOracle::GetBNC() ...], it makes no sense to define lower bounds on the component because they (if any) are already implicit in the available complete description of the function; in fact, FiOracle::GetLowerBound() never produces anything for "easy" components.

If the NDO algorithm does not exploit the LBs, no dual multipliers are associated with them, and this method must return 0.

Reimplemented from NDOSolver.

◆ ReadMult()

cHpRow ReadMult	(	cIndex_Set &	I,
		Index &	D,
		cIndex	wFi = Inf< Index >() )

virtual

Convex minimization problems have a "dual" viewpoint (which is also briefly described in the general notes section of FiOracle.h). This method should return "dual" information about the problem, if the NDO algorithm is capable of computing it; as this is not always the case, a default implementation returning "no such information is available" is provided by the base class.

In general, the dual for the convex minimization problem

(P)   min{ Fi( Lambda ) }

is (D) inf{ Fi*( z ) : z = 0 }

where "*" indicates the Fenchel's conjugate operator; in fact, it is well-known that

inf{ Fi( Lambda ) } = - Fi*( 0 ),

so that the minimization of Fi is equivalent to problem of computing the conjugate of Fi in 0. The standard form in which Fi is available is that of a "black box" or "oracle" [see FiOracle.h]; from the dual viewpoint, an oracle is something that takes a point Lambda in the primal space and returns a point z in the dual space (essentially, the space of subgradients of Fi) such that Lambda is a subgradient of Fi* in z, together with the value Fi*( z ). This information is all that can be used from a "dual" NDO algorithm in order to solve the dual problem.

Since Fi* is a convex function, its epigraph is a convex set; each point (z, Fi*( z )) of the epigraph can be obtained as a convex combination of at most n + 1 other points of the epigraph. From the dual viewpoint, an NDO algorithm should produce a set of multipliers Theta[ z ] attached to all the subgradients/constraints (items) z generated by the oracle, such that

Sum{z} z * Theta[ z ] = 0 && Sum{z} Fi*( z ) * Theta[ z ] = Fi*( 0 ).

A (read-only) pointer to these Theta[] must be returned by ReadMult(), with 0 meaning that they are not available. The "format" of Theta[] depends on I: if I == 0, then Theta[] is a "dense" D-vector, i.e., the multiplier of item with "name" i is found in Theta[ i ] for i = 0, ..., D - 1, otherwise Theta[ i ] is the multiplier of the item with "name" I[ i ] for i = 0, ..., D - 1. I[] must be ordered in increasing sense and Inf< Index >()-terminated. The "names" of the items are those that are passed to the FiOracle [see SetMaxName() and SetGiName() in FiOracle.h].

In the Lagrangian case, a dual object x[ i ] is attached to the item z with name i; x[ i ] \in X if z is a subgradient, while x[ i ] is an extreme ray for X if z is a constraint. Then,

x = Sum{i \in D[]} Theta[ i ] * x[ i ]

is an optimal solution for the "convex relaxation" (D) of the original problem (OP) [see the general notes section in FiOracle.h], which can be constructed with this dual information and the help of the FiOracle.

When Fi is decomposable, the dual information is naturally "splitted" among the components of Fi, since the subgradients are. If 1 <= wFi <= NrFi (the number of different components, see SetFiOracle() above) then only the dual information relative to that component will be returned, i.e., I[] will only contain "names" of items corresponding to component wFi; otherwise all the dual information will be returned. In the Lagrangian case, a decomposable Fi corresponds to a separable X [see FiOracle.h], so that the dual information is divided among the disjoint components of X.

Note: For "easy" components of Fi() [see FiOracle::GetBNC() ...], a different type of information naturally "takes the place" of the multipliers: the optimal solution x[ wFi ]* of the Lagrangian problem in the current point in terms of the "original variables" of the wFi-th component. Thus, calls to ReadMult( wFi ) with an "easy" wFi have the following different meaning: the vector returned by the method (that may be "dense" or "sparse" as in the standard case) represents x[ wFi ]*, and it is therefore a FiOracle::GetBNC( wFi )-vector. This information, however, can only* be accessed when calling ReadMult( wFi ) for wFi <= NrFi: in "global" calls (wFi > NrFi) only the multipliers corresponding to non-easy components are returned.; The dual multipliers Theta[] corresponding to subgradients [of any given component] should be nonnegative and sum to 1—they are convex combinators—while the multipliers Theta[] corresponding to constraints [for any given component] need only be nonnegative. There is an exception to this rule, however, which happens if the NDO algorithms exploits the information provided by Lower Bounds on the optimal value of Fi and/or its components Fi[ i ]; these bounds have a dual meaning and therefore dual information attached to them, that is returned by the separate method ReadLBMult() [see below]. If this happens, the "ordinary" dual multipliers returned by ReadMult() and corresponding to subgradients may sum to a quantity strictly smaller than 1.

If Solve() returns kUnfeasible, the problem is unfeasible; this means that it is either dual unbounded or dual empty. In fact, the dual solution obtained as above is then a feasible ascent extreme ray for (D), that is c( x ) > 0 , A( x ) [<]= 0 and x' + beta * x \in X for each x' \in X and beta > 0. Thus, if X is nonempty then (D) is unbounded, otherwise it is empty.

Reimplemented from NDOSolver.

◆ ReadSol()

cLMRow ReadSol	(	cIndex_Set &	I,
		Index &	D )

virtual

Returns a read-only pointer to the stability center $\bar{\lambda}_i$. If Solve() has returned a kOK and the tStar has been properly set, the point returned by ReadSol() - and, a fortiori, the one returned by ReadBestSol() - is $\epsilon$-optimal.

Implements NDOSolver.

◆ RemoveVariables()

void RemoveVariables	(	cIndex_Set	whch = 0,
		Index	hwmny = 0 )

virtual

Removes the variable whose "names" are contained in the vector ‘whch’, that should contain ‘hwnmy’ distinct values in the range 0 ... NumVar - 1, be ordered in increasing sense and be Inf< Index >()-terminated, i.e., whch[ hwnmy ] must be == Inf< Index >().

If whch == 0, all the variables are eliminated; in this case, hwmny is ignored.

The set of variable "names" is kept contiguous, i.e., it is always the set 0 ... NumVar - 1 for the value of NumVar after the call to the method; hence, some of the variables that are not eliminated need to be "renamed". This is done as follows: when variable ‘i’ is eliminated, all variables with names i + 1 ... NumVar - 1 take names i ... NumVar - 2, respectively (i.e., the names are shifted left by one to fill the gap). If multiple variables are eliminated, this is repeated for each variable, starting with the one with smaller name (the first one in whch) upwards. Note that if the last* variable is eliminated, no renaming has to be done.

After a call to this method, a different function, on a different variable space, has to be minimized. Of course, the two functions must not be unrelated to one another; more specifically, it is required that the new function Fi( Lambda ) is just the restriction of the old function Fi( Lambda , LambdaOld ) to the subspace where all the eliminated variables are zero, i.e. that

Fi( Lambda , 0 ) = Fi( Lambda ) for all Lambda.

This implies, for instance, that the projection of all the previously collected subgradients on the new space (the elimination of the entries corresponding to the removed variables) are still subgradients for the new function in the new space. In other words, if the linear function

L( Lambda , LambdaOld ) = G * Lambda + OldG * LambdaOld + a

is known to minorize the old Fi(), then

L( Lambda ) = G * Lambda + a

minorizes the new Fi(). Even better than that, the "linearization error" of L() at any point with LambdaOld = 0

Fi( Lambda , 0 ) - L( Lambda , 0 ) >= 0

is identical to the linearization error of L() at Lambda

Fi( Lambda ) - L( Lambda ) >= 0.

Also, note that the value of the new function in all the previously tested points with LambdaOld = 0 (if any) is known.

When this method is called, the removed variables must still be defined in the FiOracle, i.e., the NDOSolver is still allowed to query information about the variables being removed from the FiOracle. Of course, after the termination of the call to RemoveVariables() the FiOracle must be updated to reflect the change in the variables set. Note that the likely caller for RemoveVariables() is the FiOracle itself; this is one of the reasons why the FiOracle may need a pointer to the NDOSolver that is using it [see SetNDOSolver() in FiOracle.h]. If RemoveVariables() is not directly called by the FiOracle, the caller must ensure that the FiOracle is also properly updated after that the method returns. Note that this requirement is, for obvious reasons, opposite to what is assumed for AddVariables() [see above].

This operation is typically useful in the case of Lagrangian optimization, where it corresponds to the deletion of some of the relaxed constraints A( x ) [<]= b, hopefully because they have been detected to be redundant.

Reimplemented from NDOSolver.

◆ ReSetAlg()

void ReSetAlg ( unsigned char RstLvl = 0 )

virtual

Resets the internal state of the SubGrad algorithm. Since several different things can be reset independently, RstLvl is coded bit-wise:

bit 0: if 0, all the algorithmic parameters are reset to the default values read by the stream/set by SetPar(), while if 1 they are left untouched;
bit 1: if 0 the current point is reset to the all-0 vector, while if 1 it is left untouched;
bit 2: if 0, all the subgradients are removed, except the constant (sub)gradient of the linear 0-th component, while if 1 the subgrads are left there;
bit 3: if 0, all the constraints are removed from the, while if 1 the constraints are left there.
bit 4: if 0 the value of Fi() in the current point is reset to INF (i.e., unknown), while if 1 it is left untouched; note that resetting the current point [see bit 1] has this as a side-effect, regardless to the value of bit 4.

Reimplemented from NDOSolver.

◆ SaveDir()

void SaveDir ( void )

protected

The method is combined with FormD() [see above] to carry out the direction computation. Moreover, the stepsize is determined into SaveDir() when the adopted scheme is stepsize-restricted.

◆ SetDeflection()

void SetDeflection ( Deflection * Vol = nullptr )

Gives to the SubGrad object a pointer to an object of class Deflection that will be used to provide a deflection coefficient $ \alpha_i$ .

The Deflection object can be changed during the life of a SubGrad object, but this change clearly forces the reset of all the information about the function accumulated so far. Passing nullptr does exactly this job. Note that the Deflection object becomes property of the SubGrad object: if a new one is passed, or the SubGrad object is destroyed, then the current Deflection object in the SubGrad one (if any) is destroyed.

Unlike with Stepsize, SubGrad can work with a nullptr Deflection: this just means that the deflection coefficient is kept to 1, i.e., no deflection.

◆ SetFiOracle()

void SetFiOracle ( FiOracle * Fi = nullptr )

virtual

Passes the FiOracle object to the NDOSolver class.

This MUST be done PRIOR to ANY CALL to ANY OTHER method of the class!

This is not done in the constructor in order to allow the user to change the function to be minimized during the lifetime of one NDOSolver object. Of course, this method must not be called within any other method of the class, as it (presumably) causes a complete reset of most internal data structures (e.g. the starting point, see below). Note that extensive support [see [Add/Remove]Variables() and Chg[FiV/SbG]() below] is given for cases where the function changes but the new function is "related" to the old one, so that "warm starts" can be attempted; of course, nothing of this kind can be expected when the FiOracle is changed with SetFiOracle().

Passing 0 as the pointer is intended signal the NDOSolver to release as much memory as possible and to sit down quietly in its corner, waiting for a new FiOracle to become available. After a SetFiOracle( 0 ) call, NO OTHER method of the class (apart from the destructor) should be called before SetFiOracle() is called again with a non-0 argument. However, specific NDO solvers may allow exceptions to this rule.

Reimplemented from NDOSolver.

◆ SetLambda()

void SetLambda ( cLMRow tLambda = nullptr )

virtual

Sets the starting point of the NDO algorithm; if 0 is given, or if the method is not called, some starting point is chosen by the solver (the all-0 vector being one of the prime candidates). Note that Solve() [see below] is expected to repotimize somehow using the results of the previous calls, if any, and using the latest "current point" as the starting point is one very typical way of doing it; SetLambda() can be used to reset the starting point.

No calls to SetLambda() are allowed while Solve() is running; the starting point can only be changed between two calls to Solve(), and this possibly has a nontrivial computational cost.

Note that tLambda must be feasible at least with respect to the non-negativity and upper bound constraints on the variables [see GetUC() and GetUB() in FiOracle.h]. Since one needs the FiOracle to check it, this method must not be called before SetFiOracle() [see above].

The vector pointed by tLambda is supposedly copied into internal data structures of the NDSolver, hence it can be modified and/or destroyed after the completion of the method.

Implements NDOSolver.

◆ SetNDOLog()

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

lvl controls the "level of verbosity" of the code. The first four bits of lvl have the following meaning:

0 => no log at all (also assumed if log = 0);
1 => "basic" log: only the errors are reported;
2 => a detailed step-by-step log of the algorithm is displayed;
4 .. 15 unused, available to derived classes;

◆ SetPar() [1/3]

void SetPar	(	const int	wp,
		cHpNum	value )

virtual

Extends NDOSolver::SetPar( , cHpNum ) for handling the SubGrad-specific parameters; the enum SGParam is used (in the obvious way) for selecting the parameter to be set.

Reimplemented from NDOSolver.

◆ SetPar() [2/3]

void SetPar	(	const int	wp,
		const bool	value )

Change boolean algorithmic parameters of the SubGrad solver. The enum SGParam is used for selecting the parameter to be set.

◆ SetPar() [3/3]

void SetPar	(	const int	wp,
		const int	value )

virtual

Extends NDOSolver::SetPar( , cIndex ) for handling the SubGrad-specific parameters; the enum SGParam is used (in the obvious way) for selecting the parameter to be set.

Reimplemented from NDOSolver.

◆ SetStepsize()

void SetStepsize ( Stepsize * STP = nullptr )

Gives to the SubGrad object a pointer to an object of class Stepsize that will be used to provide $\nu_i$ during the subgradient algorithm.

The Stepsize object can be changed during the life of a SubGrad object, but this change clearly forces the reset of all the information about the function accumulated so far. Passing nullptr does exactly this job. Note that the Stepsize object becomes property of the SubGrad object: if a new one is passed, or the SubGrad object is destroyed, then the current Stepsize object in the SubGrad one (if any) is destroyed.

◆ Solve()

NDOStatus Solve ( void )

virtual

Tries to minimize the function. It implements the subgradient algorithm exploiting the protected methods FormD(), SaveDir(), FormLambda1(), FiAndGi(), and GotoLambda1().

Returns if

kOK optimization has been successful: a solution that is "optimal" (w.r.t. the current parameters settings) has been found;
kUnbndd there has been an error in the FiOracle, i.e. Fi() has returned -HpINF, or the function is unbounded below: the latter case can be detected only if a lower bound on the min. value of $f$ is available [see FiOracle::GetMinusInfinity()];
kUnfsbl the polyhedral set defined by the constraints is empty: in this case, the primal optimal solution is an unbounded extreme ray for the dual problem;
kStopped Solve() has been stopped, either by FiOracle::GetFiStatus() or because the stepsize has been "too small" during 100 consecutive outer iterations [or 100 * NrFi consecutive inner iterations];
kStpIter the max. number of iterations has been exhausted;
kStpTime the max. running time has been reached;
kError There have been some problem in the FiOracle that require to stop the optimization.

As for kStopped, "too small" means that $ \nu_i \leq 1e-8 * t^*$, where $ t^* $ is the optimality related parameter scaling Fi(). There is no reason, in principle, why we couldn't replace $1e-8$ by a parameter, but in order to make the test easier this parameter has been fixed to $1e-8$. We also decided to replace by 100 the parameter saying how many outer iterations of consecutive small stepsizes are sufficient to stop the algorithm.

Note that, whatever the exit condition be, the current point is always available by calling ReadSol(), and its Fi() value by calling ReadFiVal().

Implements NDOSolver.

Friends And Related Symbol Documentation

◆ Stepsize

friend class Stepsize

friend

The classes Stepsize and Deflection are "friends" of SubGrad. This is done because Stepsize and Deflection objects may need some protected data to work. An issue, however, is that derived classes from friend classes are not friend, and therefore actual implementations of Stepsize and Deflection cannot access data of SubGrad unless this capability is explicitly provided by the base classes, who are friends. This is why Stepsize and Deflection define a few methods that allow to read protected data of SubGrad: so that any derived class can use them to access to these data. These methods are, in fact, implemented at the end of SubGrad.C.

Member Data Documentation

◆ DirPos

bool DirPos

protected

indicates where the direction $d_i$ in located in the oracle

◆ dM1GkDone

bool dM1GkDone

protected

true if the scalar product $d_{i-1}^{\top} g_i$ has been computed

◆ Epsilon

HpNum Epsilon

protected

the linearization error $\epsilon_i$ of $d_i$ at $\bar{\lambda}_i$

◆ HatEpsilon

HpNum HatEpsilon

protected

the linearization error $ \hat{\epsilon}_i $ of $d_i$ with respect to $\hat{\lambda}_i$

◆ Lambda

LMRow Lambda

protected

the current point $ \lambda_i $ or the trial point $ \lambda_{i+1} $

◆ LHasChgd

bool LHasChgd

protected

true if Lambda has changed since the latest call to FiAndGi()

◆ LHasProj

bool LHasProj

protected

true if Lambda has projected in the current iteration

◆ NItIncr

Index NItIncr

protected

number of incremental iterations after an outer iteration

◆ Seq

vector< Index > Seq

protected

vector containing the randomly shuffled components of the function $f$

◆ Sigma

HpNum Sigma

protected

the linearization error $ \sigma_i$ of $ g_i$ at $\bar{\lambda}_{i}$

◆ SigmaHat

HpNum SigmaHat

protected

the linearization error $ \hat{\alpha}_i $ of $g_i$ with respect to $\hat{\lambda}_i$

◆ TrueLB

bool TrueLB

protected

true if LowerBound is a "true" lower bound rather than just the "minus infinity"

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

SubGrad/SubGrad.h

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Private Member Functions

Friends

Detailed Description

Member Enumeration Documentation

◆ SGParam

Constructor & Destructor Documentation

◆ SubGrad()

Member Function Documentation

◆ AddVariables()

◆ ChgFiV()

◆ ChgSbG()

◆ FiAndGi()

◆ FormD()

◆ FormLambda1()

◆ GetPar() [1/2]

◆ GetPar() [2/2]

◆ GotoLambda1()

◆ IsOptimal()

◆ KeepBestLambda()

◆ ReadBestFiVal()

◆ ReadBestSol()

◆ ReadFiVal()

◆ ReadHatFiVal()

◆ ReadLBMult()

◆ ReadMult()

◆ ReadSol()

◆ RemoveVariables()

◆ ReSetAlg()

◆ SaveDir()

◆ SetDeflection()

◆ SetFiOracle()

◆ SetLambda()

◆ SetNDOLog()

◆ SetPar() [1/3]

◆ SetPar() [2/3]

◆ SetPar() [3/3]

◆ SetStepsize()

◆ Solve()

Friends And Related Symbol Documentation

◆ Stepsize

Member Data Documentation

◆ DirPos

◆ dM1GkDone

◆ Epsilon

◆ HatEpsilon

◆ Lambda

◆ LHasChgd

◆ LHasProj

◆ NItIncr

◆ Seq

◆ Sigma

◆ SigmaHat

◆ TrueLB