Bundle Class Reference

#include <Bundle.h>

Inheritance diagram for Bundle:

Public Types
Public Types
enum	BndParam {   kBPar1 = kLastNDOParam , kBPar2 , kBPar3 , kBPar4 ,   kBPar5 , kBPar6 , km1 , km3 ,   kmxIncr , kmnIncr , kMnSSC , kmxDecr ,   kmnDecr , kMnNSC , ktMaior , ktMinor ,   ktInit , ktCurr , ktSPar1 , ktSPar2 ,   kPPar1 , kPPar2 , kPPar3 , kMPEFsb ,   kMPEOpt }
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
void	GetPar (const int wp, int &value)
void	GetPar (const int wp, HpNum &value)
Constructor
	Bundle (istream *iStrm=0)
Other initializations
void	SetMPSolver (MPSolver *MPS=0)
void	SetFiOracle (FiOracle *Fi=0)
void	SetLambda (cLMRow tLambda=0)
void	KeepBestLambda (const bool KBL=true)
void	SetPar (const int wp, const int value)
void	SetPar (const int wp, cHpNum 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	ReadSol (cIndex_Set &I, Index &D)
cLMRow	ReadBestSol (cIndex_Set &I, Index &D)
bool	IsOptimal (HpNum eps=0) const
HpNum	ReadSigma (void) const
HpNum	ReadDStart (cHpNum tt=1) const
bool	CurrentIsLast (void)
HpNum	ReadFiVal (cIndex wFi=Inf< Index >())
HpNum	ReadBestFiVal (cIndex wFi=Inf< Index >())
cHpRow	ReadMult (cIndex_Set &I, Index &D, cIndex wFi=Inf< Index >())
HpNum	ReadLBMult (cIndex wFi=Inf< Index >())
HpNum	Readt (void)
Index	NrSSs (void) const
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 >())
void	RemoveItem (cIndex Name)
void	RemoveItems (void)
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)
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 Types
enum	EIStatus { kEINorm = 0 , kEIAbort , kEILoopNow , kEIContAnyway }

Protected Member Functions
void	FormD (void)
void	FormLambda1 (HpNum Tau)
bool	FiAndGi (void)
void	GotoLambda1 (void)
void	UpdtCntrs (void)
void	SimpleBStrat (void)
void	Log1 (void)
void	Log2 (void)
bool	CheckAlfa (const bool All=false)
void	StrongCheckAlfa (void)
void	UpdtLowerBound (void)
void	UpdtaBP3 (void)
void	CmptaBPX (void)
Hook for derived classes
The following method is called by the solver to give derived classes, which may implement variants of the Generalized Bundle approach, a better control over the optimization process.
virtual EIStatus	EveryIteration (void)

Protected Attributes
MPSolver *	Master
int	BPar1
int	BPar2
HpNum	BPar3
HpNum	BPar4
HpNum	BPar5
int	BPar6
HpNum	mxIncr
HpNum	mnIncr
int	MnSSC
HpNum	mxDecr
HpNum	mnDecr
int	MnNSC
HpNum	m1
HpNum	m3
HpNum	tMaior
HpNum	tMinor
HpNum	tInit
int	tSPar1
HpNum	tSPar2
int	PPar1
int	PPar2
int	PPar3
HpNum	MPEFsb
HpNum	MPEOpt
Index	MaxNumVar
Bool_Vec	IsEasy
LMRow	Lambda
LMRow	Lambda1
LMRow	LmbdBst
Index_Set	LamBase
Index_Set	Lam1Bse
Index	LamDim
bool	KpBstL
bool	BHasChgd
bool	LHasChgd
bool	tHasChgd
HpRow	FiLambda
HpRow	FiBest
HpRow	FiLambda1
HpRow	RfrncFi
Index_Set	whisZ
Index_Set	whisG1
LMRow	ScPr1
HpRow	Alfa1
HpRow	DeltaAlfa
HpRow	LowerBound
HpNum	t
HpNum	Prevt
HpNum	Sigma
HpNum	DSTS
HpNum	vStar
HpNum	Deltav
HpNum	DeltaFi
HpNum	EpsU
HpNum	EpsCurr
HpNum	EpsFi
int	ParSS
int	CSSCntr
int	CNSCntr
Index	FreDim
Index_Set	FreList
SIndex_Set	OOBase
Index_Set	InctvCtr
Index_Set	nBase
bool	TrueLB
bool	LBHasChgd
bool	SSDone
bool	ItemsChgd
FiOracle::FiStatus *	FiStatus
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
bool	DoSS (void)
void	Delete (cIndex i)
bool	FindNextSG (Index &wFi)
Index	BStrategy (cIndex wFi)
Index	FindAPlace (cIndex wFi)
HpNum	Heuristic1 (void)
HpNum	Heuristic2 (void)
void	InitMP (void)
void	AggregateZ (cHpRow Mlt, cIndex_Set MBse, Index MBDm, cIndex wFi, cIndex whr)
HpNum	WhichFi (cHpRow FiVect, cIndex wFi)
void	MemDealloc (void)

Private Attributes
Index	MBDim
Index	aBP3
Index	aBP4

Detailed Description

The Bundle class implements the NDOSolver interface for NonDifferentiable Optimization Solvers [see NDOSlver.h], using a "Generalized Bundle" algorithm as described in

A. Frangioni "Generalized Bundle Methods" SIAM Journal on Optimization 13(1), p. 117 - 156, 2002

This is in fact a "meta" algorithm, in that it is parametric over the type of "model" and of "stabilizing term" used, and therefore over the exact Master Problem that has to be solved at each iteration: it just relies over an object of class MPSolver [see MPSolver.h] to solve it.

As any other NDOSolver, the Bundle class requires that the function to be minimized be available under the form of a FiOracle object [see FiOracle.h].

The interface between the Bundle object and the applications that will use it is mostly derived from the interface of the base class NDOSolver [see NDOSlvr.h], thus greatly simplifying the task of using different NDOSolvers for solving the same NDO problem.

Member Enumeration Documentation

BndParam

enum BndParam

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

EIStatus

enum EIStatus

protected

Protected enum describing the possible return values of EveryIteration() [see below].

Constructor & Destructor Documentation

Bundle()

Bundle

(

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 Bundle 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.

Note that ‘iStrm’ is also passed to the constructor of the base class [see NDOSolver.h], which reads its algorithmic parameters out of it. It has to be remarked that the Bundle class adds its specific "twists" to some of the algorithmic parameters of the base class, in particular the ones regarding inexact computation of the function:

HpNum EInit [1e-2] HpNum EFnal [1e-6] HpNum EDcrs [.95] Index EStps [0]

For this it has to be remarked that the Bundle has an "emergency mechanism" such that if it detects that it is "stalling" because of insufficient accuracy in the oracle computation, it will automatically decrease the relative precision required to the FiOracle [see SetPrecision() in FiOracle.h]. Then, the above parameters now have the following meaning:

HpNum EInit ABS( EInit ) is the initial, and maximum, precision required to the oracle, but the sign tells how the "emergency mechanism" alluded to above interacts with the "regular mechanism" controlled by these parameters. In particular, if EInit > 0 then the accuracy is monotonically non-increasing: if the "emergency mechanism" reduces it, then it will remain "at least as small" in all the following iterations, even if the value computed by the "regular mechanism" would be larger. If EInit < 0 instead, then each time a "regular step" is computed the precision is reset to that dictated by the "regular mechanism", even if it is larger than the current one (for instance, if EStps == 0, see below, then the precision is set to a "fixed" value).

HpNum EFnal The other three parameters define a general formula that sets the "regular mechanism" for changing the precision along iterations. Note that EFnal has a completely different meaning as the one postulated by the base class (smallest precision) because that makes no sense: the "final" precision clearly has to be EpsLin. In fact, a value larger than EpsLin would make it impossible (in theory) to reach EpsLin-accuracy for the overall optimization, and a value smaller than EpsLin is wasteful as a higher precision than EpsLin is not required. The idea is that the precision should improve along the iterations, and the "speed" at which this happens is dictated by EStps and EFnal; however, one can also keep the precision "fixed" by setting EStps == 0. In this case, having defined

EpsU = ( ReadDStart( tStar ) + ReadSigma() ) / ReadFiVal()

the current estimate of the optimality measure, the formula is

precision = / ABS( EInit ) if EDcrs >= 0 \ ABS( EDcrs ) * EpsU if EDcrs < 0

and this is kept fixed along all the iterations (except, EpsU is not really fixed); only the "emergency mechanism" will increase it if this is absolutely needed. If instead EStps != 0, having defined

opt = / ABS( EInit ) if EDcrs >= 0 \ EpsU if EDcrs < 0

h = / NrIter() if EStps > 0 , k = ceil( h / ABS( EStps ) ) \ NrSSs() if EStps < 0

the formula is:

precision = opt * / ABS( EDcrs )^{ EFnal * k } if EFnal >= 0 \ ABS( EDcrs ) * k^{ EFnal } if EFnal < 0

(while ensuring precision <= ABS( EInit )).

Since the Bundle constructor is executed after the one of NDOSolver, the following Bundle-specific parameters have to be found in the stream after* those of the base class:

Index BPar1 [10] If an item has had a zero multiplier [see ReadMult() in NDOSolver.h] for the last BPar1 steps, it is eliminated; if BPar1 is "too small" precious information may be lost, but keeping the "bundle" small obviously makes the Master Problem cheaper.

Index BPar2 [100] Maximum dimension of the bundle: has more or less the Same "problems" as BPar1, but if the latter is well chosen then BPar2 can be kept big while the "B-strategy" keeps the actual number of items low. A small BPar2 can affect the convergence of the algorithm, in theory as well as in practice, if aggregation is not allowed. However, an unnecessarily large BPar2 may force the MP Solver to allocate a large amount of memory without a real need.

HpNum BPar3 [-1] Maximum ... HpNum BPar4 [-1] ... and minimum number of new subgradients/ constraints (items) to be fetched from the FiOracle for each function evaluation. Two different ways are given for specifying these numbers: positive values are (rounded up and) taken as absolute values, while negative numbers are first multiplied by FiOracle::GetNrFi()—the number of components of Fi()—(and then rounded up); thus, the default vale "-1" stands for "one for each of the components of Fi()". Clearly, the "finalized" value of BPar3 has to be <= BPar2, and the "finalized" value of BPar4 has to be <= than that.

HpNum BPar5 [30] These parameters control how the actual number of Index BPar6 [0] subgradients/constraints (items) that are requested to the FiOracle varies, between BPar4 and BPar3, as the algorithm proceeds; note that what varies in practice is the maximum number, as it is always legal for the FiOracle to refuse giving other items, although the Bundle code will complain and stop if less than BPar4 are given. In the Bundle code, the number

EpsU = Sigma + D_{tStar}*( z* ) / max( | ReadFiVal() | , 1 ) ,

where Sigma = Sum_i Fi[ i ]_{B,Lambda}*( z[ i ]* ) + \sigma_L( w ) and z* = - Sum_i z[ i ]* is the optimal solution of the stabilized Dual Master Problem [see MPSolver.h], is used as an estimate of the relative gap between the current and the optimal solution; that is, IsOptimal() returns true if EpsU <= EpsLin. Thus, the number EpsLin / EpsU is always smaller than one, and typically increases as the algorithm proceeds. Depending on the value of BPar6, the following formulae for the actual value of BPar3, aBP3, are used: 0: aBP3 is set to (the "finalized" value of) BPar3 and never changed; 1: if BPar5 > 0 then aBP3 is initialized to (...) BPar4 and increased every BPar5 iterations, while if BPar5 <= 0 then aBP3 is initialized to BPar3 and decreased every - BPar5 iterations; 2: aBP3 is set to ( BPar5 > 0 ? BPar4 : BPar3 ) + BPar5 * ( EpsLin / EpsU ) 3: aBP3 is set to ( BPar5 > 0 ? BPar4 : BPar3 ) + BPar5 / sqrt( EpsU / EpsLin ) 4: aBP3 is set to ( BPar5 > 0 ? BPar4 : BPar3 ) + BPar5 / log10( EpsU / EpsLin )

HpNum m1 [.1] SS condition: if DeltaFi >= | m1 | * Deltav, then a SS is done. What is taken as Deltav depends on the sign of m1: if m1 > 0 then Deltav = - v* (the decrease predicted by the model), while if m1 < 0 then Deltav = - ( v* + D_t( d* ) ), i.e. the optimal objective function value the dual Master Problem. Since

• v* >= - ( v* + D_t( d* ) ), the second condition is weaker and may lead to a larger number of SS (and therefore possibly a fater convergence) while still ensuring global convergence. The value m1 = 0, i.e., perform a SS for whatever small improvement in the objective function, can only be used, at least in theory, for some classes of functions (the polyhedral ones) and some under assumptions on the MP.

HpNum m3 [3] A nevly obtained subgradient is deemed "useless" if Alfa >= m3 * Sigma; in this case, if a NS has to be done, t is decreased. This parameter is mostly critical: if no "long-term" t-strategy [see tSPar1 below] is used, values < 2/3 usually make t to decrease rather fast to tMinor [see below], possibly making the algorithm to perform very short steps and therefore to converge very slowly. When a "long-term" t-strategy is used, .9 may be a good value.

HpNum mxIncr [10] each time t grows, the new value of t is chosen in HpNum mnIncr [1.5] the interval [t * mnIncr, t * mxIncr] (t is the previous value) Index MnSSC [0] minimum number of consecutive SS with the same t that have to be performed before t is allowed to grow

HpNum mxDecr [.1] each time t diminishes, the new value of t is chosen HpNum mmDecr [.66] in the interval [t * mxDecr, t * mnDecr] (t is the previous value) Index MnNSC [0] minimum number of consecutive NS with the same t that have to be performed before t is allowed to diminish

HpNum tMaior [1e+6] Maximum, ... HpNum tMinor [1e-6] ... minimum, and ... HpNum tInit [1] ... initial value of t. These parameters may be critical, but they are not very difficult to set. Usually, there is a "right" order of magnitude for t, that is the one that is guessed by the t-heuristics during most of the run, even though the starting value is very different. Hence, a good setting for tInit is in that order of magnitude, while tMinor should be set small enough to never enter into play. Note that t is always kept <= tStar [see NDOSolver.h], and that a "good" value for tStar (i.e., one that actually ensures that the stopping point is EpsLin-optimal) is usually one or two orders of magnitude larger than a "good" tInit.

Index tSPar1 [0] Select the t-strategy used. This field is coded bit-wise in the following way. The first two bits control which heuristics are used to compute a new value of t when increasing/decreasing it. There are two heuristics available, H1 and H2, both based on a quadratic interpolation of the function but differing in which derivative is used: H1 uses the derivative in the new tentative point, and it is guaranteed to produce a value greater than the current one if and only if the scalar product between the direction and the newly obtained subgradient is < 0 (indicating that a longer step along the same direction could have been advantageous), while H2 uses the derivative in the current point and it does not possess this property. The value of the first two bits of tSPar1 has the following meaning: bit 0: which heuristic is used to increase t: 0 = H1, 1 = H2 bit 1: which heuristic is used to decrease t: 0 = H2, 1 = H1 The following bits of tSPar1 tell which long-term t-strategy is used, with the following values: 0 (+ 0): none, only the heuristics are used 1 (+ 4): the "soft" long-term t-strategy is used: an optimality estimate EpsU is maintained which estimates how far from the optimal value one currently is, and decreases of t are inhibited whenever v < tSPar2 * EpsU * | Fi | 2 (+ 8): the "hard" long-term t-strategy is used: an optimality estimate EpsU is maintained as above and t is increased whenever v < tSPar2 * EpsU * | Fi | 3 (+12): the "balancing" long-term t-strategy is used, where the two terms D*_t( -z* ) and Sigma* are kept of "roughly the same size": if D*_1( -z* ) <= tSPar2 * Sigma* then t increases are inhibited (increasing t causes a decrease of D*_1( -z* ) that is already small), if tSPar2 * D*_1( -z* ) >= Sigma* then t decreases are inhibited (decreasing t causes an increase of D*_1( -z* ) that is already big). Still later bits of tSPar1 activate "special cases" t-strategies: 4 (+16): the "endgame" t-strategy is used, where if D*_1( -z* ) is "small" (~ 1/10 of the current absolute epsilon) t is decreased no matter what the other strategies dictated. The rationale is that we are "towards the end" of the optimization and here t needs decrease. However, note that having D*_1( -z* ) "small" is no guarantee that we actually are at the end, especially if the FiOracle dynamically generates its variables, so use with caution.

HpNum tSPar2 [.1] Numerical parameter for the long-term t-strategies, see tSPar1 above.

Index PPar1 [30] Parameters controlling the variables generator: "price in" (discover if new variables have to be added) is done all the first PPar1 iterations ... Index PPar2 [10] ... and then every PPar2 iterations; note that the price in is done anyway each time convergence is detected. If PPar2 == 0, all the variables are present from the beginning (PPar1 is ignored if PPar2 == 0). Index PPar3 [5] A variable that has been inactive for the last PPar3 pricings (this one included) is eliminated: note that the "price out" operation is done every PPar2 iterations, so that a variable that is eliminated is likely to have been inactive for (about) PPar2 * PPar3 iterations. For PPar3 == 1, a variable is eliminated in the very pricing in which it is discovered to be zero (and the direction saying that it would stay zero). If PPar3 == 0, variables are never* removed. PPar3 is ignored if PPar2 == 0.

HpNum MPEFsb [1e-6] (relative) precision required to the MP Solver as far as constraints satisfaction is concerned. HpNum MPEOpt [1e-6] (relative) precision required to the MP Solver as far as optimality of the solution is concerned.

The methods SetPar() of the base class are extended to allow the setting of the Bundle-specific parameters [see below].

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

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.

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.

CurrentIsLast()

bool CurrentIsLast ( void )

inline

The point returned by ReadSol() [see above], called the ‘current point’, may not be the point corresponding to the last call to FiOracle::Fi() [see FiOracle.h], because a number of ‘Null Steps’ may have performed done after the last ‘Serious Step’.

This method returns true if the current point is actually the last point for which Fi() was evaluated, and false otherwise. This may be useful in some cases.

EveryIteration()

virtual EIStatus EveryIteration ( void )

protectedvirtual

This method is an "hook" for derived classes: it is called at Every Iteration, between the computation of the tentative direction and the computation of Fi(). It can serve to various purposes, primarily checking extra stopping conditions or interfering with the usual stopping conditions of the Bundle code: however, any kind of operation can be performed here inside, e.g. adding or removing variables from the problem [see [Add/Remove]Variable() above]. More in general, this method can be used to merge the main cycle of the Bundle method within any other however complex code: the Bundle gives out the control at this time, and resumes its operations when EveryIteration() returns. The returned value influences the behaviour of the Bundle for the current iteration:

kEINorm the current iteration is continued normally;

kEIAbort the whole algorithm is aborted, and Solve() is immediately terminated returning kAbort: this is useful for instance to enforce new termination criteria;

kEILoopNow the current iteration is aborted, i.e. the stopping condition is not checked, and Fi() is not called: the next iteration is immediately started, but the iterations count is not increased. This is useful e.g. if something has been changed in the data of the problem that suggests to try a new direction, like a new "active" or variable [see AddVariable() above] to be inserted;

kEIContAnyway the current iteration is continued normally but for the fact that the stopping condition is not checked.

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.

IsOptimal()

bool IsOptimal ( HpNum eps = 0 ) const

inlinevirtual

This method should return true if the NDOSolver believes that the current solution [see ReadSol() above] is eps-optimal (relative). If eps == 0, then the optimality tolerances used by the solver to terminate are used.

This method may be called while Solve() is running, e.g. by the FiOracle: if IsOptimal(), then the NDOSolver is going to stop at this iteration, so the FiOracle can react accordingly.

Reimplemented from NDOSolver.

KeepBestLambda()

void KeepBestLambda ( const bool KBL = true )

virtual

Reimplemented from NDOSolver.

NrSSs()

Index NrSSs ( void ) const

inline

Returns the current number of Serious Steps; note that analogously to the number of iterations [see NrIter()] this is not necessarily reset each time Solve() is called.

ReadBestFiVal()

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

virtual

Returns the best Fi-value() found so far, i.e., those of the point returned by ReadBestSol(). Unlike ReadBestSol(), however, this method is supposed to work even if KeepBestLambda() is not called (too little storage is required here not to do that). If the NDO algorithm is of descent, the method returns the same values as ReadFiVal() [see above]; the implementation of ReadBestFiVal() provided by the base class works for this case.

For meaning of wFi, also refer to ReadFiVal().

Reimplemented from NDOSolver.

ReadBestSol()

cLMRow ReadBestSol ( cIndex_Set & I, Index & D )

virtual

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 EpsLin-optimal.

Reimplemented from NDOSolver.

ReadDStart()

HpNum ReadDStart ( cHpNum tt = 1 ) const

inline

Return the current value of the "two pieces" of the stopping criterion. Indeed, IsOptimal() returns true if

ReadDStart( tStar ) + ReadSigma() <= EpsLin * ReadFiVal()

where tStar and EpsLin are the general stopping parameters defined in NDOSolver [see NDOSolver.h]. For more details on what exactly ReadDStart() and ReadSigma() return see the same-named methods in MPSolver.h.

ReadFiVal()

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

virtual

Returns the Fi-value(s) of the point returned by ReadSol() [see above]. wFi tells the value of which "component" of Fi is required [see GetNrFi() in FiOracle.h]:

• wFi == 0 requires the value of the linear 0-th component of Fi.
• 1 <= wFi <= NrFi requires the value of the wFi-th component of Fi.
• Inf< Index >() > wFi > NrFi requires the value of the full function Fi except* the linear 0-th component.
• wFi == Inf< Index >() requires the value of the full function Fi.

Implements NDOSolver.

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

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 EpsLin-optimal.

Implements NDOSolver.

RemoveItem()

void RemoveItem

(

cIndex

Name

)

Remove the item ‘Name’ from the bundle.

Note that this method is not a part of the NDOSolver interface since it is somewhat subsumed by ChgFiV() and ReSetAlg() [see above]; however, it may still be of some use, so it is kept.

RemoveItems()

void RemoveItems

(

void

)

Remove all the items from the bundle, except the (sub)gradient of the linear 0-th component of Fi).

Note that this method is not a part of the NDOSolver interface since it is somewhat subsumed by ChgFiV() and ReSetAlg() [see above]; however, it may still be of some use, so it is kept.

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 Bundle 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 from the bundle, except the constant (sub)gradient of the linear 0-th component, while if 1 the subgradients are left there;
• bit 3: if 0, all the constraints are removed from the bundle, while if 1 the constraints are left there.
• bit 4: if 0 the value of Fi() in the current point is reset to HpINF (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.

SetFiOracle()

void SetFiOracle ( FiOracle * Fi = 0 )

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 = 0 )

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.

SetMPSolver()

void SetMPSolver

(

MPSolver *

MPS = 0

)

Gives to the Bundle object a pointer to an object of class MPSolver that will be used as Master Problem Solver during the Bundle algorithm.

The MPSolver can be changed during the life of a Bundle object, but this change clearly forces the reset of all the information about the function accumulated so far (the bundle). Passing a 0 pointer does exactly this job.

In contrast with the standard rule, SetMPSolver() can be called even if no FiOracle is currently set to the NDO solver, that is, SetFiOracle() has not already been called or it has been called the last time with 0.

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;

The remaining of lvl is coded bit-wise, so that logging of specific features can be activated independently:

bit 4 == 1 (+ 16) => every operation on the set of items (adding, removing, aggregating) is logged;

bit 5 == 1 (+ 32) => the activity of the variables generator [see PPar* in the comments of Bundle() above] is logged.

SetPar() [1/2]

void SetPar ( const int wp, cHpNum value )

inlinevirtual

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

Some remarks are needed about setting some of the parameters:

• if a "variable Fi() precision" scheme is used, the current precision is not* re-initialized to its initial value if Solve() is called more than once (it is, however, if the FiOracle changes or ReSetAlg() is called); analogously, the counter of Fi() evaluations left before decreasing the precision is not reset. SetPar( NDOSolver::kEInit , 0 ) forces a reset of the scheme.

Reimplemented from NDOSolver.

SetPar() [2/2]

void SetPar ( const int wp, const int value )

inlinevirtual

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

Some remarks are needed about setting some of the parameters:

• the extra parameter Bundle::ktCurr can be used to force "from the outside" a change of the current value of t. Note that the change only takes effect the next time the Master Problem is solved, and could be overridden if the normal t-strategy is executed in the meantime. If this is done in GetFiStatus(), a possible trick is to have that call to return kFiChgd, so that the next iteration is immediately started and the change of t takes effect.
• changing BPar2 may force the Master Problem solver to restructure its internal data structures [see MPSolver::SetDim()], and therefore may be expensive; also, diminishing the bundle size forces some subgradients to be discarded.

Reimplemented from NDOSolver.

Solve()

NDOStatus Solve ( void )

virtual

Tries to minimize the function. If there are constraints the minimization is divided into two phases: in Phase 0 a feasible point is sought for, and in Phase 1 the function is minimized moving on feasible points only.

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 Fi() 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 by EveryIteration() [see below];

kStpIter the max. number of iterations has been exhausted;

kLwPrcsn the algorithm cannot proceed because the function cannot be computed with enough precision [see FiOracle::SetPrecision()]: this means that the function has been minimized up to the maximum extent that is possible due to the limited precision that the FiOracle can provide;

kError There was an error in the Master Problem solver, and this condition has not been corrected by the elimination of items.

Note that, whatever the exit condition be, the current point is always available by calling ReadSol(), and its Fi() value by calling ReadFiVal() [see below]. There are constraints and kStpIter has been returned, Phase 0 may not have finished yet: hence, the current point may not be feasible, so that ReadFiVal() may return + HpINF.

Solve() is "virtual" in order to allow derived classes to implement different "main" strategies: this can be easily done by exploiting the methods FormD(), FormLambda1(), FiAndGi(), GotoLambda1(), UpdtCntrs() and EveryIteration() in the protected interface of the class [see below].

Implements NDOSolver.

---

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

• Bundle/Bundle.h