NDOSolver / FiOracle: QPPenaltyMP Class Reference

Inheritance diagram for QPPenaltyMP:

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

void	SetDim (cIndex MxBSz=0, FiOracle *Oracle=0, const bool UsAvSt=false) override

void	Sett (cHpNum tt=1) override

void	SetPar (const int wp, cHpNum value) override

void	SetLowerBound (cHpNum LwBnd=- Inf< HpNum >(), cIndex wFi=Inf< Index >()) override

void	CheckIdentical (const bool Chk=true) override

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

MPStatus	SolveMP (void) override

HpNum	ReadFiBLambda (cIndex wFi=Inf< Index >()) override

HpNum	ReadDt (cHpNum tt=1) override

HpNum	ReadSigma (cIndex wFi=Inf< Index >()) override

HpNum	ReadDStart (cHpNum tt=1) override

cLMRow	Readd (bool Fulld=false) override

void	ReadZ (LMRow tz, cIndex_Set &I, Index &D, cIndex wFi=Inf< Index >()) override

cHpRow	ReadMult (cIndex_Set &I, Index &D, cIndex wFi=Inf< Index >(), const bool IncldCnst=false) override

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

HpNum	ReadGid (cIndex Nm=Inf< Index >()) override

void	MakeLambda1 (cHpRow Lmbd, HpRow Lmbd1, cHpNum Tau) override

void	SensitAnals (HpNum &lp, HpNum &cp) override

Index	BSize (cIndex wFi=Inf< Index >()) override
	returns the current number of items (of either type) in the bundle.

Index	BCSize (cIndex wFi=Inf< Index >()) override
	returns the current number of constraints in the bundle.

Index	MaxName (cIndex wFi=Inf< Index >()) override

Index	WComponent (cIndex i) override

bool	IsSubG (cIndex i) override

Index	NumNNVars (void) override

Index	NumBxdVars (void) override

bool	IsNN (cIndex i) override

cHpRow	ReadLinErr (void) override

HpNum	ReadLowerBound (cIndex wFi=Inf< Index >()) override

Index	ReadGi (cIndex Nm, SgRow Gi, cIndex_Set &GB)

HpNum	EpsilonD (void) override

SgRow	GetItem (cIndex wFi=Inf< Index >()) override

void	SetItemBse (cIndex_Set SGBse=0, cIndex SGBDm=0) override

Index	CheckSubG (cHpNum DFi, cHpNum Tau, HpNum &Ai, HpNum &ScPri) override

Index	CheckCnst (HpNum &Ai, HpNum &ScPri, cHpRow CrrPnt) override

bool	ChangesMPSol (void) override

void	SetItem (cIndex Nm=Inf< Index >()) override

void	SubstItem (cIndex Nm) override

void	RmvItem (cIndex i) override

void	RmvItems (void) override

void	SetActvSt (cIndex_Set AVrs=0, cIndex AVDm=0) override

void	AddActvSt (cIndex_Set Addd, cIndex AdDm, cIndex_Set AVrs) override

void	RmvActvSt (cIndex_Set Rmvd, cIndex RmDm, cIndex_Set AVrs) override

void	AddVars (cIndex NNwVrs) override

void	RmvVars (cIndex_Set whch=0, Index hwmny=0) override

void	ChgAlfa (cHpRow DeltaAlfa) override

void	ChgAlfa (cHpRow NewAlfa, cIndex wFi) override

void	ChgAlfa (cIndex i, cHpNum Ai) override

void	ChangeCurrPoint (cLMRow DLambda, cHpRow DFi) override

void	ChangeCurrPoint (cHpNum Tau, cHpRow DFi) override

void	ChgSubG (cIndex strt, Index stp, cIndex wFi) override

void	SetPricing (cHpNum Brk=Inf< HpNum >())

void	SetMaxVarAdd (cIndex MVA=1)

void	SetMaxVarRmv (cIndex MVR=1)

Public Member Functions inherited from MPSolver
virtual void	SetMPTime (const bool TimeIt=true)

	MPSolver (void)

virtual void	SetThreads (int nthreads)

virtual cHpRow	ReadDualEasy (cIndex wFi)
	returns the dual variables of the constraints of an easy component

virtual cHpRow	ReadReducedCostsEasy (cIndex wFi)
	returns the reduced costs of the variables of an easy component

void	MPTime (double &t_us, double &t_ss)

double	MPTime (void)

Index	GetMaxBSize (void)
	returns the maximum bundle size

Index	GetMaxSGLen (void)
	returns the maximum subgradient length

Index	GetCrrSGLen (void)
	returns the current subgradient length

Index	GetNrFi (void)
	returns the number of components of Fi()

virtual void	ChgCosts (Index wFi, cLMRow Lambda)

virtual void	ChgRLHS (Index wFi)

virtual void	ChgLUBD (Index wFi)

virtual	~MPSolver ()
	destructor: deletes the timer. it is virtual, as it must be

Private Member Functions
void	ComputeRHSxd (void)
	just the destructor

void	Computedir (bool Fulld)

Index	CheckBCopy (void)

void	GiTG (cIndex i, QuRow Qi, cIndex iMax) override

cSgRow	GiTilde (cIndex i) override

LMNum	CalculateZ (cIndex h)

void	CalculateZ (cIndex_Set Wh, LMRow z)

void	CalculateZ (LMRow z) override

LMNum	GiTLB (cIndex h, cLMRow l, cIndex_Set lB, cIndex lBd) override

void	GiTLB (HpRow gtlb, cLMRow l, cIndex_Set lB, cIndex lBd, const bool add) override

SgRow	TSGi (cIndex i)

void	FullZ (LMRow z, cIndex_Set tB, cHpRow tM)

void	CompleteZ (bool Fullz=true)

void	CheckBounds (void)

void	ChgRHS (cIndex strt, cIndex stp)

void	CheckSG (void)

void	CheckGT (void)

void	MemDealloc (void)

Private Member Functions inherited from BMinQuad
	BMinQuad (void)

void	SetMaxDim (Index m, Index n, Index SDim)

void	SetEpsilonD (HpNum NeweD=0)

void	SetMaxVarAdd (cIndex MVA=1)

void	SetMaxVarRmv (cIndex MVR=1)

virtual void	SetBMQTime (const bool TimeIt=true)

void	AddSubGrad (cIndex n, cHpNum alfan)

void	AddConstr (cIndex n, cHpNum alfan)

void	ChangeAlfa (cIndex i, cHpNum DeltaAlfai)

void	ChangeAlfa (cHpNum DeltaAlfa)

void	MoveAlongD (cHpNum Tau, cHpNum DeltaFi)

void	ReadAlfa (HpRow NewAlfa)

cHpRow	ReadAlfa (void)

void	SetGTz (cIndex i, cHpNum GTzi)

void	SetD (Index i, LMNum Di)

LMRow	SetD (void)

LMRow	LowerBounds (void)

LMRow	UpperBounds (void)

void	ChangeBounds (void)

void	InitialSetUp (void)

char	NNVar (void)
	mask for variables with lower bound, used in InitialSetUp()

char	IsVar (void)
	mask for existing variables, used in InitialSetUp()

char	AcVar (void)
	mask for active variables, used in InitialSetUp()

char	UBVar (void)
	mask for variables with uppper bound, used in InitialSetUp()

void	AddVars (cIndex_Set whch, cIndex hwmny)

void	AddVars (cIndex strt, cIndex hwmny)

void	RemoveVars (cIndex_Set whch, Index hwmny)

void	MoveVar (cIndex i, cIndex j, const bool iIsLst=true)

void	RenameVars (cIndex_Set whch)

void	MakeVarCnstr (cIndex i)

void	MakeVarUnCnstr (cIndex i)

MQError	SolveQP (HpNum ti)

void	SettmpD (LMRow td)

LMRow	GettmpD (void)

HpNum	ReadzNorm (void)

HpNum	ReadSigma (const bool IncldCnst=true)

cLMRow	ReadZ (void)

void	ReadZ (LMRow z)

void	ReadZSprs (LMRow z)

Index	ReadVNames (Index_Set VNames)

void	ReadD (LMRow d, cIndex CpyFrst=0)

void	ReadDSprs (LMRow d)

cIndex_Set	ActiveVars (void)

Index	AVDim (void)
	Returns the size of the set of "active" variables, see ActiveVars().

cIndex_Set	InActiveVars (void)

Index	IAVDim (void)
	Returns the size of the set of "inactive" variables, see InActiveVars().

char	GetVar (cIndex i)

char *	GetVars (void)

HpNum	DPerG (cSgRow g)

void	AddD (LMRow L1, cLMRow L2, cHpNum Tau)

void	AddDSprs (LMRow L1, cLMRow L2, cHpNum Tau)

HpNum	ReadGTz (cIndex i)

void	SensitAnals1 (HpNum &v1, HpNum &v2, HpNum &v3)

void	BMQTime (double &t_us, double &t_ss)
	Returns the user and sistem time in seconds spent so far by SolveQP()

double	BMQTime (void)
	Returns the total time in seconds spent so far by SolveQP()

HpNum	EpsilonD (void)

virtual	~BMinQuad ()
	Memory deallocation. Statistics (if any) are printed.

void	RecomputeRealAlfa (void)

Private Member Functions inherited from MinQuad
	MinQuad (void)

void	SetCrrBDim (cIndex Newn)

void	SetLB (HpNum LB=-Inf< HpNum >())

void	SetEpsilonR (HpNum NeweR=0)

void	SetPricing (cHpNum Brk=Inf< HpNum >())

void	SetMaxTime (cHpNum NewMaxTime)

virtual void	SetMQTime (const bool TimeIt=true)

bool	IsThere (cIndex n)
	Returns true if there is an item with name 'n'.

bool	IsASubG (cIndex n)
	Returns true if the item with "name" 'n' is a subgradient.

bool	IsAConst (cIndex n)
	Returns true if the item with "name" 'n' is a constraint.

bool	IsLB (void)
	Returns true if a Lower Bound has been set.

Index	MaxItemN (void)

void	ResetBundle (cIndex which)

void	ResetBundle (void)
	Complete reset of the bundle: all items are eliminated.

cHpNum	ReadLB (void)
	returns the current value of the Lower Bound

void	AddSGSpaceDim (cSgRow NewDim, const bool UpdtB=true)

void	AddSGSpaceDim (cSgRow NewDim, cHpNum lbh, const bool UpdtB=true)

void	CutSGSpaceDim (cSgRow OldDim, const bool UpdtB=true)

void	CutSGSpaceDim (cSgRow OldDim, cHpNum lbh, const bool UpdtB=true)

void	ChangeQ (void)

void	UpdateB (void)

void	ResetB (void)

HpNum	Readv (void)

cHpRow	ReadMult (void)

Index	ReadBDim (void)

cIndex_Set	ReadBase (void)

bool	IsInBase (cIndex n)
	Returns true if the "name" 'n' is in the optimal base.

Index	ReadCBDim (void)

cHpRow	ReadInfDir (void)

HpNum	ReadLBMult (void)

void	SensitAnals2 (HpNum v1, HpNum v2, HpRow x1, HpRow x2)

void	SensitAnals3 (cHpNum v1, cHpNum v2, HpRow x1, HpRow x2, HpNum &tMin, HpNum &tMax)

void	MQTime (double &t_us, double &t_ss)
	Return the user and sistem time (in seconds) spent so far by SolveQP().

double	MQTime (void)
	Return the total time (in seconds) spent so far by SolveQP().

HpNum	EpsilonR (void)

QuNum	LowQ (cIndex i, cIndex j)

QuNum	LowQ (cIndex i)
	LowQ( i ) = LowQ( i , i )

virtual	~MinQuad ()
	Memory deallocation. Statistics (if any) are printed.

void	AlfaChanged (void)

Private Attributes
FiOracle *	CrrOrcl

Index	DimMinQuad

HpNum	MinNewAlfa

HpNum	tCurr

HpNum	Alfa1

HpNum	G1Perz

LMRow	dir

char	ZCmptd

char	dirCmptd

SgRow	RHSp

HpNum	RHSxd

cIndex_Set	ActvVrs

Index	ActvVDim

Index	NNVars

Index	BxdVars

SgMat	SubG

SgRow	TSGk

SgRow	tmpG1

bool	ChkIde

Private Attributes inherited from BMinQuad
Index_Set	Base2

Index	B2Dim
	Dimension of Base2.

Index_Set	MBase2

Index	MB2Dim
	Dimension of MBase2 ( <= SpaceDim - B2Dim )

Index_Set	MvdVars

Private Attributes inherited from MinQuad
Index	MaxBDim
	Max. dimension of the bundle.

Index	ActBDim
	Number of items currently in the bundle.

Index	ActCNum

Index	NxtBIdx

MQError	QPStatus
	termination code of SolveQP()

HpRow	Mult
	Primal variables.

Index_Set	Base
	Base (set of strictly positive variables)

Index	BDim
	n. of items in Base

HpNum	Quad
	Mult^T * Q * Mult.

HpNum	Lin
	Alfa^T * Mult.

HpRow	GTz

HpRow	Alfa
	Linearization errors.

HpNum	PrvsTi
	Value of ti in the latest call of CalcOptDir()

HpNum	eR
	Relative error for "== 0" tests.

HpRow	tmpa

HpRow	tmpv
	like tmpa

Additional Inherited Members
Public Types inherited from MPSolver
enum	MPParam { kMaxTme = 0 , kOptEps , kFsbEps , kLastMPParam }

enum	MPStatus { kOK = 0 , kUnbndd , kUnfsbl , kStppd , kError }

Protected Attributes inherited from MPSolver
Index	MaxBSize

Index	MaxSGLen

Index	CrrSGLen

Index	NrFi

std::ostream *	MPLog

char	MPLLvl

OPTtimers *	MPt

Private Types inherited from MinQuad
enum	MQError { kOK = 0 , kNegativeDelta , kIncreasingStep , kNegVarInBase , kInvalidV , kLoop , kQPPrimUnbndd , kStpTime , kFatal }

Member Function Documentation

◆ AddActvSt()

void AddActvSt	(	cIndex_Set	Addd,
		cIndex	AdDm,
		cIndex_Set	AVrs )

overridevirtual

Adds ‘AdDm’ new variables to the current active set, whose names are contained in the first AdDm positions of the vector Addd (ordered in increasing sense and Inf< Index >()-terminated); those names must not already belong to the active set.

AVrs must point to a vector containing the new active set; a pointer to that vector is kept and used from now on as the new active set, replacing the old vector set with the latest call to one of SetActvSt(), AddActvSt() or RmvActvSt(). Thus, the vector pointed by the "old" pointer can be freely modified after the return of AddActvSt(), while the one pointed by AVrs must not be modified until it is in turn substituted by a new one.

Thus, AVrs must usually be different from the "old" pointer; one exception is permitted, however, in the case when all the variables to be added are to be found after all the variables that were present previously. In this case, the caller is authorized to use the old pointer as the new pointer (and checking this is exactly how the MPSolver detects the fact), overwriting the "Inf< Index >()" which previously terminated the active set with the names of the variables to be added before the call to AddActvSt() (i.e., Addd = AVrs + <n. of variables in the old active set>).

This method can be used only if an active set has been previously defined with SetActvSt( <non-0> ) and not yet removed with SetActvSt( 0 ).

Important note: after a call to AddActvSt(), all the solution information corresponding to the last call to SolveMP() is lost, and the results returned by all the query methods are unpredictable. This is true even for CheckSubG(), CheckCnst() and ChangesMPSol(), so adding items to the bundle after a call to this method is not advised.

Implements MPSolver.

◆ AddVars()

void AddVars ( cIndex NNwVrs )

overridevirtual

This method adds ‘NNwVrs’ new variables to the MP, in response to a call to NDOSolver::AddVariables( NNwVrs , IVs ) [see NDOSlvr.h]. The derived classes are required to use GetUC(), GetUB(), GetGi() and (possibly) GetADesc() [see FiOracle.h] to acquire directly from the FiOracle all the information about the newly created variables they need.

The method is used when NDOSolver::AddVariables() is called, i.e., when new variables Lambda[ i ] of the original NDO problem are created. Note that adding variables Lambda[ i ] changes, in principle, the current point, and therefore the linearization errors of the items. For instance, in the Lagrangian case, it is easy to check that the linearization error alfa_{Lambda}[ i ] of the subgradient named ‘i’ with respect to the current point Lambda is simply

alfa_{Lambda}[ i ] = Fi( Lambda )

c( x[ i ] ) + Lambda * ( b - A( x[ i ] ) )

where x[ i ] is the solution of the Lagrangian problem corresponding to the subgradient. Thus, adding a new variable Lambda_j changes the linearization error of Lambda_j * ( b_j - A_j( x[ i ] ) ). Hence, the linearization errors of all items change except if Lambda_j == 0. In order to avoid the recomputation of the linearization errors, it is assumed that all the variables d[ i ] of the Primal Master Problem added with AddVars() correspond to variables Lambda[ i ] that are set to 0; in other words, it is assumed that adding the variables does not change the linearization errors (changing them is always possible with ChangeCurrPoint()).

Note that, if an "active set" has been defined [see SetDim() above], then the newly added variables are not added to the current active set; this must* be done explicitly, if needed, with [Set/Add]ActvSt() [see above]. If the active set option has not been selected, then the variables are automatically added to the MP.

Important note: after a call to AddVars(), all the solution information corresponding to the last call to SolveMP() is lost, and the results returned by all the query methods are unpredictable. This is true even for CheckSubG(), CheckCnst() and ChangesMPSol(), so adding items to the bundle after a call to this method is not advised.

Implements MPSolver.

◆ BCSize()

Index BCSize ( cIndex wFi = Inf< Index >() )

inlineoverridevirtual

returns the current number of constraints in the bundle.

Implements MPSolver.

◆ BSize()

Index BSize ( cIndex wFi = Inf< Index >() )

inlineoverridevirtual

returns the current number of items (of either type) in the bundle.

Implements MPSolver.

◆ CalculateZ()

void CalculateZ ( LMRow z )

overrideprivatevirtual

Dealing with constraints on the direction d requires at least checking if they are violated; since d[ i ] = - ti * z[ i ] wherever this does not violate a constraint, the entries of the "aggregate item" z must be computed.

In the usual (simple) case where there exist a "naive" form of the items as vectors of SgNum's with SDim components, all of which corresponding to constrained variables, and the subgradient whose "name" is ‘i’ is just the i-th row of the matrix G, CalculateZ( < all > ) (the third form) must do

for( i = 0 ; i < SDim ; i++ ) for( z[ i ] = 0 , h = 0 ; h < BDim ; h++ ) z[ i ] += G[ Base[ h ] ][ i ] * Mult[ i ];

where Mult (HpRow), Base (Index_Set) and BDim (Index) are protected fields of class BMinQuad (actually, of base class MinQuad). Note that the memory of z is provided by the BMinQuad object. To ease the calculation, Base[] is guaranteed to be Inf< Index >()-terminated, i.e., Base[ BDim ] == Inf< Index >().

If the components of z are requested one by one (the first form), the intended semantic of CalculateZ( < one > ) is that of the following code

cLMRow temp = GiTilde( h ); LMNum zh = 0;

for( Index i = 0 ; i < BDim ; i++ ) zh += temp[ Base[ i ] ] * Mult[ i ];

return( zh );

but smarter implementations may be possible in some circumstances.

Finally, if the components of z are requested "in slots" (the second form), intended semantic of CalculateZ( < a set > ) is that of

for( Index h = 0 ; Wh[ h ] < Inf< Index >() ; h++ ) z[ Wh[ h ] ] = CalculateZ( Wh[ h ] );

Which of these three implementations is better depends on the details of how the subgradients are kept in memory (by rows or by columns, in dense or sparse format) and on the instances to be solved (average number of items vs number of variables, presence of unconstrained variables), so that the final decision should be due to the final user.

Implements BMinQuad.

◆ ChangeCurrPoint() [1/2]

void ChangeCurrPoint	(	cHpNum	Tau,
		cHpRow	DFi )

overridevirtual

Equivalent to ChangeCurrPoint( ( Tau / t ) * d* , DFi ), where d* is the optimal solution of the direction finding subproblem (Tau is a relative step along d, relative w.r.t. t). Here, however, no problem with the active set can arise, since d* is nonzero only for variables of the active set.

Implements MPSolver.

◆ ChangeCurrPoint() [2/2]

void ChangeCurrPoint	(	cLMRow	DLambda,
		cHpRow	DFi )

overridevirtual

Updates the data of the Master Problem in response to a change of the "current point" Lambda:

DLambda = newLambda - Lambda,

i.e., DLambda is the direction that is followed (with step 1) to go from the old current point Lambda to the new current point newLambda. DLambda is in "dense" format [see MakeLambda1() above], i.e., ‘DLambda[ i ]’ contains the displacement relative to variable ‘i’ for i = 0 .. CrrSGLen - 1. Note that the set of variables with nonzero displacement may not be a subset of the "active set" [see [Set/Add/Rmv]ActvSt() above], i.e., that the entry of the current point for variable ‘i’ may vary even if i is currently forced to be zero by being out of the active set, In order for the Master problem to become "aware" of the change for these variables, the active set has to be changed.

DFi[ k ] must be the change in the value of the function between the two points, i.e.,

DFi[ k ] = Fi[ k ]( newLambda ) - Fi[ k ]( Lambda )

for 1 <= k <= NrFi, while

DFi[ 0 ] = Fi( newLambda ) - Fi( Lambda )

(i.e., the value of the whole function). Note that the values for "easy" components are provided as well, altough the MPSolver in principle knows them already.

The formulae for updating the data are the following. If z[ i ] is a alfa[ i ]-subgradient to the k-th component of Fi in Lambda, then it is a newalfa[ i ]-subgradient (to the k-th component of Fi) in newLambda, where

newalfa[ i ] = alfa[ i ] + DFi[ k ] - DLambda * z[ i ] .

If z[ i ] is a constraint

z[ i ] * ( Lambda + d ) <= RHSi

its right-hand side in the d-variables is RHSi - z[ i ] * Lambda. Hence, for newLambda = Lambda + DLambda the constraint has to become

z[ i ] * ( newLambda + d ) <= RHSi ,

that is, its right-hand side in the d-variables is

RHSi - z[ i ] * newLambda = ( RHSi - z[ i ] * Lambda ) - z[ i ] * Dlambda .

In particular, for box constraints on the Lambda variables [see GetUC() and GetUB() in FiOracle.h], the Master Problem has to contain box constraints on the d variables (assuming for simplicity every variable is box constrained)

LB - Lambda <= d <= UB - Lambda .

Clearly, when the current point is changed to newLambda = Lambda + DLambda these constraints have to become

LB - newLambda <= d <= UB - newLambda ,

that is, ( LB - Lambda ) - Dlambda <= d <= ( UB - Lambda ) - Dlambda.

Implements MPSolver.

◆ ChangesMPSol()

bool ChangesMPSol ( void )

overridevirtual

After that Check[SubG/Cnst]() [see above] has been called, this method can be used to check whether or not the introduction of the new item changes the solution of the MP. If not, the Bundle algorithm may decide not to insert it in the bundle, and however knows if the newly obtained information is enough for obtaining a different d* at the next iteration. This allows to cope with "non-exact functions", i.e., with a FiOracle that is not capable of - or is instructed not to - computing the Fi-values and/or the subgradients exactly. Note that ChangesMPSol() must not be called for the constant subgradient of the linear 0-th component of Fi.

Implements MPSolver.

◆ CheckCnst()

Index CheckCnst	(	HpNum &	Ai,
		HpNum &	ScPri,
		cHpRow	CrrPnt )

overridevirtual

After that SetItemBse() has been called, CheckCnst() [if the item is a constraint, otherwise see CheckSubG() above] must be called to:

verify that the new item is not already in the bundle, and
compute some information about the item, i.e., the Right Hand Side of the item and the scalar product with d*.

The return value must be the "name" of a constraint in the bundle that is identical (element-wise) to GS, if such an item exists, or Inf< Index >() otherwise. This allows to check for useless copies (but this check is costly and can be deactivated, see CheckIdentical() above). Note, however, that the component to which the constraint belongs is now irrelevant, and therefore that the checks have to be performed across all the components (comprised the 0-th). The reason is that while a constraint nominally belongs to one component (in Lagrangian terms, the corresponding primal unbounded ray is for one particular subproblem) this has no impact on the master problem: unlike subgradients, two identical constraints (columns) corresponding to two different components actually are the same constraint (column) in the master problem, and therefore one is redundant. Thus one can (and therefore should) safely declare a constraint a copy of another even if they belong to different components. Note that this corresponds, from the primal side, to choose between two different primal rays belonging to different subproblems, and therefore it does have an impact on the generated primal (convexified) solution. However, if one would keep the two constraints then it would be the Master Problem solver which would arbitrarily "split the corresponding primal variables among them", so a decision would still be somewhat taken in this respect that is entirely out of control; better, then, to at least save some running time and memory. If this turns out to be a problem for some weird reason, the check can be deactivated with CheckIdentical() and the problem solved.

As for CheckSubG(), the scalar product between the primal optimal solution d* of the MP and SG must be calculated and returned in ScPri.

Ai must contain the Right Hand Side, i.e., the constraint on the original variables is

SG * Lambda <= Ai.

However, the MP is defined over the d variables, that is the constraint in the MP must be

SG * ( CrrPnt + d ) <= Ai

where CrrPnt is the current point of the Bundle algorithm. The format of CrrPnt depends on whether or not the "active set" strategy has been activated with SetDim() [see above]. If the active set is used, then CrrPnt[] is in "sparse" format, i.e., ‘CrrPnt[ i ]’ is the value for the variable with name ‘AVrs[ i ]’ for i = 0 .. AVDm - 1, all the other values being zero. Otherwise, CrrPnt[] is in "dense" format. Upon return, Ai must be updated to the "scaled" Right Hand Side w.r.t. the current point, that is

Ai = Ai - SG * CurrPnt.

The Ai computed by CheckCnst() are typically used in the MP. Note that CheckCnst() must be called before SetItem() for all constraints, comprised* those of the 0-th component (wFi == 0 in GetItem()).

Implements MPSolver.

◆ CheckIdentical()

void CheckIdentical ( const bool Chk = true )

inlineoverridevirtual

When a new item is inserted in the bundle, checks can be done to ensure that it is not identical to other items already present, i.e., an useless duplicate [see CheckItem() below]. Since these checks can be costly, they are done only if CheckIdentical( true ) is called; by default, or if CheckIdentical( false ) is called, they are not.

Reimplemented from MPSolver.

◆ CheckSubG()

Index CheckSubG	(	cHpNum	DFi,
		cHpNum	Tau,
		HpNum &	Ai,
		HpNum &	ScPri )

overridevirtual

After that SetItemBse() has been called, CheckSubG() (if the item is a subgradient, otherwise see CheckCnst() below] must be called to:

verify that the new item is not already in the bundle, and
compute some information about the item, i.e., the linearization error of the item and the scalar product with d*.

The return value must be the "name" of an item in the bundle that is identical (element-wise) to GS, if such an item exists, or Inf< Index >() otherwise. This allows to check for useless copies (but this check is costly and can be deactivated, see CheckIdentical() above), which is not an unlikely possibility e.g. when Fi is the Lagrangian function of a combinatorial optimization problem (and therefore the set of possible subgradients is finite). Note that subgradients that are element-wise identical but belong to different components are not identical and should not be substituted for one another; in other words, the check only has to be performed with subgradients of the same component as SG* (which, besides being correct, is also likely to be less costly). Also, subgradients should not be checked against constraints*, as they are two entirely different kinds of items.

Also, the scalar product between the primal optimal solution d* of the MP and SG must be calculated and returned in ScPri.

DFi must contain the valueof Fi[ wFi ]( Lambda1 ) - Fi[ wFi ]( Lambda ), where Lambda1 = Lambda + ( Tau / t ) * d*, and must Ai contain its linearization error w.r.t. Lambda1, i.e., SG is an Ai-subgradient of Fi[ wFi ]() in Lambda1. Ai must be updated to the linearization error of SG w.r.t. the current point Lambda, that is

Ai = Ai - ( DFi - ( Tau / t ) * SG * d* ).

A special case, that has a separate treatment, is that of Tau <= 0. This is taken to mean that SG is an Ai-subgradient in Lambda (typically, DFi then is also 0). This happens when adding subgradients for whom the linearization error in Lambda is already known, an important case being that of aggregation, i.e., adding to the bundle the dual optimal solution z* as provided by ReadZ() and ReadSigma(). In such a case, Ai is not modified, and the original one is directly used.

A further specific difference is whether CheckSubG() with Tau <= 0 is called inside the normal loop "compute function value and subgradient at next iterate, put them in the master problem, re-solve" or outside it; in other words, if it is possible that ChangeCurrPoint() is called before the next master problem solution. If not, then the computation of the scalar product (that anyway is not used to update Ai) can be avoided, saving some cost: this is done if Tau == 0. If, instead, ChangeCurrPoint() may be called, then the scalar product need be computed anyway, even if it is not used to update Ai: this is done if Tau < 0.

The Ai computed by CheckSubG() are typically used in the MP. Note that CheckSubG() must be called before SetItem() for all items except the constant subgradient of the "linear part" of Fi (wFi == 0 in GetItem()), where CheckSubG() must not be called.

Implements MPSolver.

◆ ChgAlfa() [1/3]

void ChgAlfa ( cHpRow DeltaAlfa )

overridevirtual

Changes the vector of the linearization errors of the subgradients.

DeltaAlfa[] is a (NrFi + 1)-vector; the linearization error of each subgradient corresponding to a component wFi is increased by DeltaAlfa[ wFi ]. DeltaAlfa[ 0 ] is ignored, and the right hand sides of the constraints are unchanged.

This is the typical correction that ought to be done when "nonexact" functions have to be handled.

Implements MPSolver.

◆ ChgAlfa() [2/3]

void ChgAlfa	(	cHpRow	NewAlfa,
		cIndex	wFi )

overridevirtual

Changes the vector of the linearization errors of the subgradients/right hand sides of the constraints.

For every item i in the bundle, the new value for its linearization error/ right hand side is taken from NewAlfa[ i ]. 0 <= wFi <= NrFi means that only the items corresponding to the wFi-th component of Fi are affected by the change. In particular, if wFi == 0 then what changes is the constant term ‘b0’ in the linear 0-th component of Fi; the new value for b0 is to be found in NewAlfa[ MaxBSize ]. 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.

Implements MPSolver.

◆ ChgAlfa() [3/3]

void ChgAlfa	(	cIndex	i,
		cHpNum	Ai )

overridevirtual

Changes the linearization error of the item with name i in the bundle to the new value Ai.

Implements MPSolver.

◆ ChgSubG()

void ChgSubG	(	cIndex	strt,
		Index	stp,
		cIndex	wFi )

overridevirtual

This method allows to change the entries corresponding to variables with names between strt (included) and stp (excluded) for all the items in the bundle corresponding to the wFi-th component of Fi, in response to a call to NDOSolver::ChgSbG( strt , stp, wFi ) [see NDOSlvr.h]. The method has to use GetGi() and (possibly) GetADesc() [see FiOracle.h] to acquire directly from the FiOracle the new information about the changed variables. 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.

Note that Fi-values, and therefore the Alfas, are assumed not to be involved in the changes.

Implements MPSolver.

◆ EpsilonD()

HpNum EpsilonD ( void )

inlineoverridevirtual

Must return the threshold used by the solver to decide when a variable is zero; Lambda[ i ] <= EpsilonD() is considered as == 0.

Implements MPSolver.

◆ GetItem()

SgRow GetItem ( cIndex wFi = Inf< Index >() )

overridevirtual

GetItem( wFi ) must return a pointer SG to a vector of SgNum's where a new item has to be written. wFi tells to which of the components of Fi() [see SetDim() above] the new item belongs, with the usual format:

when wFi == 0, the new item is relative to the linear 0-th component of Fi, i.e., it is either its constant (sub)gradient, or a constraint which defines its domain Feas0;
when 1 <= wFi <= NrFi, the new item is relative to the wFi-th component of Fi;
when Inf< Index >() > wFi > NrFi, the new item is relative to all the components except the 0-th;
when wFi == Inf< Index >(), the new item is relative to all the components, comprised* the 0-th.

This information allows the MPSolver to properly dimension the vector to be returned [see GetMaxNZ() in FiOracle.h].

Implements MPSolver.

◆ GiTG()

void GiTG	(	cIndex	i,
		QuRow	Qi,
		cIndex	iMax )

overrideprivatevirtual

These are the methods used by the base class MinQuad to access the data of the problem. However, within BMinQuad there is an important difference: the scalar products must not be performed on all the entries of the items, but only on the subset specified by the protected fields MBase2 (Index_Set) and MB2Dim (Index), i.e.

GiTGj( i , j ) = Sum{ p = 0 .. MB2Dim - 1 } G[ i ][ MBase2[ p ] ] * G[ j ][ MBase2[ p ] ].

In the simplest case (there exist a "naive" form of the items as vectors of SgNum's with SDim components, the variable with "name" ‘i’ corresponds to the i-th entry of those vectors and the item whose "name" is 'h' is the h-th row of the matrix G) the above scalar product can be calculated with

ScalarProduct( MBase2 , G[ i ] , G[ j ] )

Note that MBase2 will contain (the names of) a possibly proper subset of the constrained variables, but all the unconstrained variables.

Hence, assume that an item is a k-array of SgNum's, with k possibly > SDim. Let C be the set of "declared" variables (a subset of { 0 .. SDim - 1 }, containing names of both constrained and unconstrained variables) and U be the set of "undeclared" variables (a subset of { SDim .. k - 1 }, containing names of only unconstrained variables). Then, a correct GiTGj() would return

ScalarProduct( MBase2 , G[ i ] , G[ j ] ) + ScalarProduct( U , G[ i ] , G[ j ] )

Hence, the objects of class BMinQuad (as their ancestors MinQuad) need not know anything about the "real" implementation of the subgradients: the implementation of GiTGj( i , j ) is not provided, and it's due to the derived class, that can access to MBase2 and MB2Dim. The rationale is (as usual) that the items may have some structure (e.g. sparsity) that can be exploited to fasten the calculation of the scalar product.

GiTG() is exactly as in the base class, i.e. the pseudo-code

for( j = 0 ; j < iMax ; j++ ) if( IsThere( j ) ) Qi[ j ] = GiTGj( i , j );

is still a valid representation of what GiTG( i , Qi ) is required to do provided that "GiTGj()" accomplish the right task.

The implementing code can rely on the following invariants, guaranteed by the BMinQuad and MinQuad classes:

MBase2 is ordered, i.e. i < j => MBase2[ i ] < MBase2[ j ];
each element is unique;
MBase2 is "infinity terminated", i.e. MBase2[ MB2Dim ] == Inf< Index >();
GiTGj( i , j ) is always called with i <= j.

Implements BMinQuad.

◆ GiTilde()

cSgRow GiTilde ( cIndex i )

overrideprivatevirtual

In this case, the scalar products does not give "enough information" to solve the problem: it is also necessary to access to the matrix G of the subgradients, in a row-wise fashion. This method must return a read-only pointer RG to the i-th row of G, i.e.

        / G[ h ][ i ] if h is the "name" of a subgradient in the bundle

RG[ h ] = | \ anything otherwise

In the simplest case (there exist a "naive" form of items as vectors of SgNum's with SDim components, the variable with "name" ‘i’ corresponds to the i-th entry of those vectors and the item whose "name" is 'h' is the h-th row of the matrix G) the correct RG[] is

forall( < h = index of an item currently in the bundle > ) RG[ h ] = G[ h ][ i ];

Implements BMinQuad.

◆ GiTLB() [1/2]

LMNum GiTLB	(	cIndex	i,
		cLMRow	l,
		cIndex_Set	lB,
		cIndex	lBd )

overrideprivatevirtual

This method must compute the scalar product between the item whose "name" is ‘i’ / all the items and the vector l, limited to the entries whose indices are in the lBd-vector lB (ordered in increasing sense and Inf< Index >()-terminated).

As usual, this is better visualized by a fragment of code; for the first form this is

LMNum res = 0; for( j = 0 ; j < lBd ; j++ ) res += G[ i ][ lB[ j ] ] * l[ lB[ j ] ];

return( res );

lB[] is always a set of names of declared constrained variables, while l is the vector of the "active" bounds.

GiTLB() is called inside Add[SubGrad/Constr]() and ChangeBounds(), so be sure that all the data structures are updated before invoking those methods.

Implements BMinQuad.

◆ GiTLB() [2/2]

void GiTLB	(	HpRow	gtlb,
		cLMRow	l,
		cIndex_Set	lB,
		cIndex	lBd,
		const bool	add )

overrideprivatevirtual

Like GiTLB( i , ... ), but the code is

for( j = 0 ; j < iMax ; j++ ) if( < an item of name "j" is in the bundle > ) if( add ) gtlb[ j ] += GiTLB( j , l , lB , lBd ); else gtlb[ j ] -= GiTLB( j , l , lB , lBd );

(but, of course, depending on the implementation different and more efficient ways for modifying gtlb[] may exist).

Implements BMinQuad.

◆ IsNN()

bool IsNN ( cIndex i )

inlineoverridevirtual

This method shall return true if the variable ‘i’ is constrained to be NonNegative, and false otherwise; the standard implementation is fine for MP Solvers not accepting constrained problems.

Reimplemented from MPSolver.

◆ IsSubG()

bool IsSubG ( cIndex i )

inlineoverridevirtual

Returns true if item ‘i’ is in the Bundle and it is a subgradient, and false otherwise; hence, an item ‘i’ for which wFi == WComponent( i ) > 0 [see above] and IsSubG( i ) == false is a constraint relative to the wFi-th component of Fi (again, wFi here can be zero).

Implements MPSolver.

◆ MakeLambda1()

void MakeLambda1	(	cHpRow	Lmbd,
		HpRow	Lmbd1,
		cHpNum	Tau )

overridevirtual

Writes in (the array pointed by) Lmbd1 the vector Lmbd + ( Tau / t ) * d*, where d* is the optimal primal solution of the MP.

The "format" of Lmbd and Lmbd1 depends on whether or not the "active set" is being used [see SetActvSt() below]; if not, then Lmbd is (and Lmbd1 is expected to be) just a "dense" CrrSGLen-vectors. Otherwise, both Lmbd and Labd1 are intended to be "restricted" to the set of "active" variables that are defined by SetActvSt(); that is, only the first k entries of Lmbd/Lmbd1 are significant, where k is the size of the active set as resulting from all the previous calls to *ActvSt() [see below], and Lmbd/Lmbd1[ i ] contain the value of the i-th "active" variable (all the other variables being fixed to zero).

Note that, if an "active set" is defined, this method can compute only the entries of d* that are strictly necessary for the purpose (like Readd() does, see above), thereby possibly saving some time.

Implements MPSolver.

◆ MaxName()

Index MaxName ( cIndex wFi = Inf< Index >() )

inlineoverridevirtual

Returns 1 + the maximum "name" of an item in the bundle if the bundle is nonempty, and 0 otherwise. wFi "restricts" the count to the items corresponding to that particular component, with the usual convention.

Implements MPSolver.

◆ NumBxdVars()

Index NumBxdVars ( void )

inlineoverridevirtual

Return the number of variables (<= CrrSGLen) that have either a lower bound constraint or an upper bound constraint, or both. Hence, NumBxdVars() >= NumNNVars(), and the difference gives the number of variables with u.b. but not l.b.. The standard implementation is fine for MP Solvers not accepting constrained problems.

Reimplemented from MPSolver.

◆ NumNNVars()

Index NumNNVars ( void )

inlineoverridevirtual

Return the number of variables that are constrained in sign; this must of course be <= CrrSGLen. The standard implementation is fine for MP Solvers not accepting constrained problems.

Reimplemented from MPSolver.

◆ Readd()

cLMRow Readd ( bool Fulld = false )

overridevirtual

Returns a read-only pointer d to a vector containing the primal optimal solution d*; the entry of d* relative to variable ‘i’, if required (see below), can be found in d[ i ] for i in [ 0 .. CrrSGLen - 1 ] (see [Add/Remove/Subst]Var() below for a discussion on variable "names").

If Fulld == true, the solution d[] returned by Readd() is a "full" one, even if an "active set" of variables has been defined [see SetActvSt() below]; that is, even the entries of d* relative to variables that are not "active" are computed in response to a call to Readd( true ). This may be costly, and it is not always necessary: thus, a call to Readd( false ) computes only the entries relative to "active" variables, the contents of d[ i ] for an "inactive" variable ‘i’ being unpredictable.

Note that the returned pointer may point to a temporary data structure rather than to a "persistent" one: the pointer is no more valid (it may even point to no-more-allocated memory) after any call to any other method of the class.

Implements MPSolver.

◆ ReadDStart()

HpNum ReadDStart ( cHpNum tt = 1 )

inlineoverridevirtual

Returns the value of the dual stabilizing term D*() in the dual optimal solution z* if tt is taken as the proximal parameter.

Implements MPSolver.

◆ ReadDt()

HpNum ReadDt ( cHpNum tt = 1 )

inlineoverridevirtual

Returns the value of the primal stabilizing term D() in the primal optimal solution d* if tt is taken as the proximal parameter.

Implements MPSolver.

◆ ReadFiBLambda()

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

overridevirtual

Returns the value of the model Fi_{B,Lambda} in d*, the optimal primal solution of the MP; this value is often called "v*". This is the value of the translated model

v* = Fi_{B,Lambda}( d* ) = Fi_B( Lambda + d* ) - Fi( Lambda ) ,

hence it is a negative value that indicates the improvement in the Fi-value that the model Fi_B() predicts for a step to Lambda + d*.

When Fi is a decomposable function [see SetDim() above], each of its components has a separate model Fi[ k ]_{B,Lambda}; ReadFiBx() must return:

Fi[ wFi ]_{B,Lambda}( d* ), if 0 <= wFi <= NrFi;
\sum_{k = 1}^{NrFi} Fi[ k ]_{B,Lambda}( d* ) if Inf< Index >() > wFi > NrFi, i.e., the value of all the models excluding the linear one;
the value of the aggregated model if wFi == Inf< Index >().

Note that if there are no subgradients (of a given component) in B, the problem that is solved is different from the standard one, as there is no such thing as a model for that component. Thus the model is temporarily removed from the master problem (like adding a constraint v[ wFi ] >= 0 for the usual representation where v[ wFi ] is the value of the model). In this case, ReadFiBLambda( wFi ) must return Inf< HpNum >().

The above changes if Fi has "easy" components [see FiOracle::GetBNC() ...], because the model of each "easy" component is not translated by value. Hence, if wFi is the index of an easy component then the method returns

Fi[ wFi ]( Lambda + d* )

rather than

Fi[ wFi ]( Lambda + d* ) - Fi[ wFi ]( Lambda ) .

Note that in both cases this is the actual value of the (corresponding component of the) function, because for easy components the model is the actual function (that is, Fi[ wFi ] == Fi_B[ wFi ]). This information is easily extracted out of the solution of the (Dual) Master Problem: if x[ wFi ]* is the optimal solution of the Master Problem in terms of the "original variables" of the wFi-th component, the required value is just ( c[ wFi ] - (Lambda + d* ) * A[ wFi ] ) x[ wFi ]*).

Note that the 0-th component is an "easy" one but it is dealt with as a "difficult" one, in that the translated model (the only possible one, the true linear function) is used.

Implements MPSolver.

◆ ReadGid()

HpNum ReadGid ( cIndex Nm = Inf< Index >() )

overridevirtual

Must return the scalar product between the item with name ‘Nm’ [see SetItem() below] and the primal optimal solution d*; this information is typically computed anyway, so it may be made available at little cost. When Nm >= MaxBSize, then the scalar product to be returned is that with the constant subgradient of the "linear part" of Fi, the 0-th component.

Implements MPSolver.

◆ ReadLBMult()

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

overridevirtual

Must return the information required by NDOSolver::ReadLBMult(), see NDOSlver.h.

Implements MPSolver.

◆ ReadLinErr()

cHpRow ReadLinErr ( void )

inlineoverridevirtual

Must return a read-only pointer to a vector containing in position i the current value of the linearization error/right hand side of item ‘i’.

Implements MPSolver.

◆ ReadLowerBound()

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

inlineoverridevirtual

Reads back the current value of the Lower Bound; see SetLowerBound() for the meaning of wFi. Note that the value is relative to the function values in the current point, and therefore changes when these (say, the current point itself) do. The updating need be done by the MPSolver, which is why it makes sense to be able to read the current value.

Implements MPSolver.

◆ ReadMult()

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

overridevirtual

The dual optimal solution z* lies in the domain of Fi_{B,Lambda}*; at least with the "classical" Cutting Plane model \hat{Fi}_{B,Lambda}, this is the convex hull of all the subgradients in B. Hence, there is another possible forms in which the dual optimal solution can be represented, i.e., as a set of (convex, for \hat{Fi}) multipliers Theta[] (>= 0 and summing to 1) such that

z* = Sum{ i \in B } Theta[ i ] * z[ i ]

where z[ i ] is the item with "name" ‘i’ [see [Set/Get]Item() below]. ReadMult() returns these multipliers. The format is "dense" if I == 0 and "sparse" otherwise: if I != 0, then only the first D entries of the returned vector contain relevant information, the i-th entry being relative to item with name ‘I[ i ]’, all other entries being zero. If I == 0, a full MaxBSize-vector is returned.

If Fi is separable, then there are as many dual optimal solutions z[ i ]* as components [see ReadSigma() above], the optimal solution z being their sum; thus, ReadMult() must return:

the multipliers making z[ wFi ]* (those relative to the subgradients of the i-th component) if 1 <= wFi <= NrFi (wFi = 0 makes no sense since z[ 0 ]* is a known constant vector, i.e., its multiplier is always 1);
the union of all the things that would be reported by calls with wFi going from 1 to NrFi otherwise.

If the parameter IncldCnst is left to true, then the returned multipliers are both of subgradients and constraints (corresponding to component wFi). In the constrained case, "extra" dual variables w (w[ i ]) corresponds to constraints, and the optimal solution is actually z* + w* (z[ i ]* + w[ i ]*): the multipliers corresponding to constraints are just nonnegative—they are not constrained to sum to 1—as they represent "extreme rays" in the dual feasible set. If IncldCnst == false, only the multipliers corresponding to subgradients are returned.

Note: The pointers returned by ReadMult() may point to a temporary data structure; the pointers are no more valid (they may even be dangling) after any call to any other method of the class.; No subgradient of "easy" components of Fi() [see FiOracle::GetBNC() ...] are ever produced, so a call to ReadMult( wFi ) with wFi the index of an "easy" component may appear to make no sense. However, something else naturally "takes the place" of the multipliers: the optimal solution x[ wFi ]* of the Master Problem in terms of the "original variables" of the wFi-th component. Thus, calls to ReadMult( wFi ) with an "easy" wFi are indeed allowed, with 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.

Implements MPSolver.

◆ ReadSigma()

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

inlineoverridevirtual

Returns the value of the conjugate Fi_{B,Lambda}* of the model Fi_{B,Lambda} in z*, the optimal dual solution of the MP; this value is often called "sigma*".

When Fi is a decomposable function [see SetDim() above], each component (of the model) has a separate conjugate function Fi[ k ]_{B,Lambda}* and a separate dual solution z[ k ]*: the dual stabilizing term is then

D_t*( - \sum_{k = 0}^{NrFi} z[ k ] ).

If primal constraints Lambda \in L are added to the primal, this is viewed as adding the indicator function I_L of the feasible set to the stabilized Primal Master Problem; this corresponds to having the support function \sigma_L appearing in the dual objective function. Thus, in this case the dual objective function is

\sum_{k = 1}^{NrFi} Fi[ k ]_{B,Lambda}*( z[ k ] ) + \sigma_L( w ) + D_t*( - \sum_{k = 0}^{NrFi} z[ k ] )

i.e., it has a term for each component, the stabilizing term and an extra term for constraints (this term is always zero in the primal because the indicator function I_L is zero in L).

Thus, ReadSigma() must return:

Fi[ wFi ]_{B,Lambda}*( z[ i ]* ) if 1 <= wFi <= NrFi: note that the value for the 0-th component of Fi is always 0, since the conjugate of a linear function is 0 iif its argument is equal to the gradient and +Infinity otherwise—in other words, z[ 0 ] is always equal to the gradient of the 0-th component;
\sum_{k = 1}^{NrFi} Fi[ k ]_{B,Lambda}*( z[ k ] ) + \sigma_L( w ) if wFi > NrFi, i.e., the dual objective function except the (dual) stabilizing term.

Note: For "easy" components of Fi() [see FiOracle::GetBNC() ...] the value that should be returned by this method is the actual value of the conjugate of the (corresponding component of) Fi(). Although it may be possible to extract that information out of the solution of the MP, a Bundle algorithm typically will never use it, so the MPSolver is allowed to assume that ReadSigma( wFi ) will never be called with wFi the index of an "easy" component. Furthermore, as in the case of ReadFiBLambda() [see above], in an "aggregated" call (that is, with wFi > NrFi) only the difficult components are counted, that is, the value of the conjugate of the model of an "easy" component never has to be computed.

Implements MPSolver.

◆ ReadZ()

void ReadZ	(	LMRow	tz,
		cIndex_Set &	I,
		Index &	D,
		cIndex	wFi = Inf< Index >() )

overridevirtual

Writes in tz[] the dual optimal solution z* in its "natural" format, i.e., a single vector z*, with as many components as d*. The format is "dense" if I == 0 and "sparse" otherwise: if I != 0, then only the first D entries of tz[] contain relevant information, the i-th entry being relative to the variable ‘I[ i ]’, all other entries being zero. If I == 0, a full CrrSGLen-vector is returned. Note that all the entries of z are "significant", even the ones corresponding to variables which are not in the "active set" [see SetActvSt() below].

If Fi is separable, then there are as many dual optimal solutions z[ i ]* as components [see ReadSigma() above], the optimal solution z being their sum. Thus, ReadZ() must return:

z[ 0 ]* == the gradient of the 0-th component if wFi == 0;
z[ wFi ]* if 1 <= wFi <= NrFi;
the sum of all the things that would be reported by calls with wFi going from 1 to NrFi if NrFi < wFi < Inf< Index >();
the sum of all the things that would be reported by calls with wFi going from 0 to NrFi if wFi == INF (this is the same as summing what is separately obtained with wFi == 0 and wFi == NrFi + 1).

Note: In the constrained case, "extra" dual variables w (w[ i ]) corresponds to constraints, and the optimal solution is actually z* + w* (z[ i ]* + w[ i ]*); ReadZ() only returns the "z* part" of the dual solution, leaving the "w* part" out.; The vector pointed by I[] may be that of a temporary data structure; hence, it is no more valid (it may even be dangling) after any call to any other method of the class. There is one notable exception: I[] can be passed to SetItemBase(), and be used as set of indices af a sparse subgradient to be inserted in the Master Problem. In fact, this is the typical reason why a z[ i ]* is computed: to perform "aggregation".; For "easy" components of Fi() [see FiOracle::GetBNC() ...] the vector that should be returned by this method is a subgradient of Fi[ wFi ] in Lambda. Although it is possible to extract that information out of the solution of the Master Problem (if x[ wFi ]* is the optimal solution of the Master Problem in terms of the "original variables" of the wFi-th component, this is just - A[ wFi ] x[ wFi ]*), a Bundle algorithm typically will never use it except in its "aggregated" form (that is, in a call with wFi > NrFi), so the MPSolver is allowed to assume that ReadZ( wFi ) will never be called with wFi the index of an "easy" component.

Implements MPSolver.

◆ RmvActvSt()

void RmvActvSt	(	cIndex_Set	Rmvd,
		cIndex	RmDm,
		cIndex_Set	AVrs )

overridevirtual

Removes ‘RmDm’ variables from the current active set, whose names are contained in the first RmDm positions of the vector Rmvd (ordered in increasing sense and Inf< Index >()-terminated); those names must be in the current active set.

AVrs must point to a vector containing the new active set; a pointer to that vector is kept and used from now on as the new active set, replacing the old vector set with the latest call to one of SetActvSt(), AddActvSt() or RmvActvSt(). Thus, the vector pointed by the "old" pointer can be freely modified after the return of RmvActvSt(), while the one pointed by AVrs must not be modified until it is in turn substituted by a new one.

This method can be used only if an active set has been previously defined with SetActvSt( <non-0> ) and not yet removed with SetActvSt( 0 ).

Important note: after a call to RmvActvSt(), all the solution information corresponding to the last call to SolveMP() is lost, and the results returned by all the query methods are unpredictable. This is true even for CheckSubG(), CheckCnst() and ChangesMPSol(), so adding items to the bundle after a call to this method is not advised.

Implements MPSolver.

◆ RmvItem()

void RmvItem ( cIndex i )

overridevirtual

Removes the item with name ‘i’ from the bundle. Items removed are unused, and their names can be used again in GetItem() [see above]. Initially, all the items are unused.

Implements MPSolver.

◆ RmvItems()

void RmvItems ( void )

overridevirtual

Removes all items from the bundle. Note that RmvItems() does not remove the constant subgradient of the linear 0-th component of Fi (RmvItem() [see above] also cannot be used for the purpose as that subgradient has no name). In principle, any Fi has a linear part, possibly all-0; thus, to remove that item one has just to use the [Get/Check/Set]Item() sequence passing an all-0 vector.

Implements MPSolver.

◆ RmvVars()

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

overridevirtual

This method removes a set of variables from the MP, in response to a call to NDOSolver::RemoveVariables( which ) [see NDOSlvr.h]; the remaining variables in the MS have to be renamed as described in the comments to NDOSolver::RemoveVariables(). As for NDOSolver::RemoveVariables(), whch == 0 means "remove all variables" (hwmny is ignored in this case).

As opposed to RmvActvSt() [see above], the effect of this removal is permanent; the variables are eliminated from the whole MP, rather than just "temporarily set aside" outside of the active set. Indeed, this "permanent" removal can only happen after the removal from the active set: no variable in the active set can be removed, i.e., RmvVars( 0 ) can only be called if the active set is empty (if, of course, the active set has been at all defined).

As for AddVars() [see above], it is assumed that the removal of the variables does not change the linearization errors of the items, i.e., that all the variables d[ i ] of the Primal Master Problem that are removed correspond to variables Lambda[ i ] of the NDO problem that have value zero in the current point; it is responsibility of the caller to ensure this, using ChangeCurrPoint() if required.

Important note: after a call to RmvVars(), all the solution information corresponding to the last call to SolveMP() is lost, and the results returned by all the query methods are unpredictable. This is true even for CheckSubG(), CheckCnst() and ChangesMPSol(), so adding items to the bundle after a call to this method is not advised.

Implements MPSolver.

◆ SensitAnals()

void SensitAnals	(	HpNum &	lp,
		HpNum &	cp )

overridevirtual

< Gives a linear lower approximation on the optimal value of v (the predicted decrease from the Cutting Plane model) as a function of the parameter t in the subproblem. That is, returns two numbers lp and cp such that

v( t ) = Fi_{B,x}( x + t * d ) >= t * lp + cp.

Implements MPSolver.

◆ SetActvSt()

void SetActvSt	(	cIndex_Set	AVrs = 0,
		cIndex	AVDm = 0 )

overridevirtual

Solving the MP can be costly; a possible way of decreasing the cost is to resort to an "active set" strategy over the primal variables d[ i ]. That is, one may guess that a (large) set of the variables will have 0 as the optimal value, and only let the others (the "active set") to vary; if it turns out that the guess has been incorrect, the active set must be revised by inserting or deleting variables [see [Add/Rmv]ActvSt() below]. This way, a smaller MP is solved at each step.

Whether or not an "active set" is used is decided in SetDim() [see above]; if it is, then SetActvSt() sets it to the variables whose names are in the first AVDm entries of the vector AVrs[] (which must be ordered in increasing sense and Inf< Index >()-terminated, i.e. AVrs[ AVDm ] == Inf< Index >()). It is an error to call SetActvSt() if the active set option has not previously been selected with SetDim().

Note that changing the active set has no impact on the linearization errors of the items. Setting the active set dictates which among the primal variables d[ i ] of the MP can be different from zero, hence, which primal variables Lambda[ i ] of the original NDO problem may change their value w.r.t. the value that they have in the current point. The linearization errors of the items depend on the current point only, and therefore they change if and only if the current point changes [see ChangeCurrPoint() and [Add/Rmv]Vars() below]. Since setting the active set affects only the variables d[ i ] of the MP and does not affect the value of the primal variables Lambda[ i ] of the Bundle algorithm, setting (or changing) the active set has no impact on the linearization errors.

Note that the pointer passed to SetActvSt() will be retained and used until it is changed, either by a new call to SetActvSt() - which just substitutes any previous active set with the new one - or by calls to [Add/Rmv]ActvSt() [see below]. Thus, the caller should not change it while it is "in use" by the MPSolver object; the vector can only be changed after* the return of the call to SetActvSt() or [Add/Rmv]ActvSt() which makes it unused. This implies that any call to SetActvSt() which sets an entirely new active set must pass a pointer that is different from the one which contained the old active set [see also [Add/Rmv]ActvSt() below]. Exception is of course AVrs == 0, that sets an empty active set: that is, the active set option is used (only SetDim() can change this), and it currently contains no variables. This is the default if SetActvSt() has not been called yet.

Important note: after a call to SetActvSt(), all the solution information corresponding to the last call to SolveMP() is lost, and the results returned by all the query methods are unpredictable. This is true even for CheckSubG(), CheckCnst() and ChangesMPSol(), so adding items to the bundle after a call to this method is not advised.

Implements MPSolver.

◆ SetDim()

void SetDim	(	cIndex	MxBSz = 0,
		FiOracle *	Oracle = 0,
		const bool	UsAvSt = false )

overridevirtual

Constructor of the class. The parameter ‘iStrm’, if provided, is taken as a pointer to a istream from which the algorithmic parameters for the QP solver are sequentially read in the following order. Each parameter must be placed at the beginning of a separate line, max 128 characters long, with all the rest of the line up to the first newline character '
' (apart from a separating whitespace) being available for comments. If NULL 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.

HpNum CtOff [.01] The "break" value for the pricing in the base class MinQuad [see SetPricing() in MinQuad.h]: positive values are passed untouched, while any negative value is turned into Inf< HpNum >().

Index MxAdd [0] How many variables can be "moved" at each iteration of the Index MxRmv [0] "upper-level method" for solving bound-constrained MPs implemented into the base class BMinQuad (if any, see HV_NNVAR above, otherwise the parameters are just ignored); see SetMaxVar[Add/Rmv]() in BMinQuad.h. If 0 [the default] is used, no bound is given.

Reimplemented from MPSolver.

◆ SetItem()

void SetItem ( cIndex Nm = Inf< Index >() )

overridevirtual

If – after all the above checks – the Bundle code decides to actually insert the item in the bundle, it has just to call SetItem( Nm ). ‘Nm’ is the "name" of the new item: the names of items are the integers between 0 and MaxBSize - 1. ‘Nm’ must be a currently unused name, that is, either a name that has not yet been used or a name that has been used in RmvItem() [see below] and not yet used in GetItem() ever since. However, if wFi == 0 has been passed to GetItem(), then Nm == Inf< Index >() has to be passed, as the only subgradient corresponding to the (linear) 0-th component of Fi has no name.

Implements MPSolver.

◆ SetItemBse()

void SetItemBse	(	cIndex_Set	SGBse = 0,
		cIndex	SGBDm = 0 )

overridevirtual

When the correct values have been written in the vector SG returned by GetItem() [see above], SetItemBse() can be used to tell the MPSolver the "format" of the information. If SGBse == 0, then SG is in "dense" format, i.e., SG[ i ] contains the entry of the subgradient relative to the variable with name ‘i’, 0 <= i < CrrSGLen - 1. If SGBse != 0 instead, then SG is in "sparse" format, i.e., SG[ i ] is the entry of the subgradient relative to the variable with name ‘SGBse[ i ]’, 0 <= i < SGBDm - 1. SGBse is assumed to be ordered in increasing sense and Inf< Index >()-terminated, i.e., SGBse[ SGBDm ] == Inf< Index >(); if SGBse == 0, then the value of SGBDm is ignored. If SetItemBse() is not called, then the "dense" format is assumed.

Note that all the CrrSGLen entries of the item must be given (although in the sparse format those that are 0 can be given only implicitly); that is, the entry relative to the variable ‘i’ must be given even if ‘i’ is currently out of the "active set" [see SetActvSt() below].

The MPSolver is allowed not to copy the memory pointed by SGBse (if any) and to keep using it throughout all the sequence of Check[SubG/Const](), ChangesMPSol() and SetItem() [see below] that is needed to decide the "fate" of the item. As soon as SetItem() returns, or GetItem() [see above] is called again, the memory pointed by SGBse must not be accessed again.

Implements MPSolver.

◆ SetLowerBound()

void SetLowerBound	(	cHpNum	LwBnd = - Inf< HpNum >(),
		cIndex	wFi = Inf< Index >() )

overridevirtual

Setting an individual lower bound on the component 1 is not supported unless RHSp == nullptr, i.e., there is no component 0; in this case clearly the lower bound on component 1 is a global lower bound for all the model, which can be set.

Implements MPSolver.

◆ SetMaxVarAdd()

void SetMaxVarAdd ( cIndex MVA = 1 )

inline

At each iteration, variables are added to the "active set", i.e. the set of variables that are fixed to their lower[/upper] bound. This method sets the maximum number of variables that can be added to the active set in one iteration: usually a "large" value helps in avoiding many unnecessary iterations, but this is in principle instance-dependent.

If the method is not called, "Inf< Index >()" is assumed, i.e., "no limit".

◆ SetMaxVarRmv()

void SetMaxVarRmv ( cIndex MVR = 1 )

inline

At each iteration, variables removed from to the "active set", i.e. the set of variables that are fixed to their lower[/upper] bound. This method sets the maximum number of variables that can be removed from the active set in one iteration: usually a "large" value helps in avoiding many unnecessary iterations, but this is in principle instance-dependent.

If the method is not called, "Inf< Index >()" is assumed, i.e., "no limit".

◆ SetMPLog()

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

inlineoverridevirtual

The meaning of lvl is:

0 => no log at all (also assumed if log = 0), except if errors are found in the Check****() routines;

1 => "basic" log: only the errors are reported;

2 => a more detailed log where also non-necessarily erroneous but "strange" situations are reported;

Note that most of the log is demanded to the ancestor classes [B]MinQuad, that actually solve the problem. They will use outs as the log stream, but their "verbosity" is rather set by the compile-time switches LOG_MQ (in MinQuad.h) and LOG_BMQ (in BMinQuad.h).

Reimplemented from MPSolver.

◆ SetPar()

void SetPar	(	const int	wp,
		cHpNum	value )

inlineoverridevirtual

Change "float" algorithmic parameters of the MPSolver. This method is pure virtual, i.e., it has to be defined in derived classes, which may extend this it to allow setting the algorithmic-specific parameters.

The enum MPParam is used for selecting the parameter to be set, with the following intended meaning:

kMaxTme: maximum running time (in seconds) for each call to SolveMP() [see below]. A 0 or negative value means "no time limit", which should be the default. If more time required, SolveMP() should stop returning kStppd. Note that this check can only be performed if timing of the code is activated [see SetMPTime() below].
kOptEps: tells the solver to solve the MP only with at least the specified relative precision (>= 0), the exact meaning of this being solver-dependent. The solver can always decide to use higher precision than that, if so it prefers. By default a solver-specific "minimal" precision is used.
kFsbEps: tells the solver to tolerate the specified relative violation of in the (primal) constraints; the solver can always decide to use higher precision than that, if so it prefers. By default a solver-specific "minimal" precision is used.

Note that the type of ‘wp’ is int rather than MPParam, which is not a problem as enums can always be used where intsare required (i.e., SetPar( MPSolver::kMaxTime , ... ) is a valid call). This is done in order to allow derived classes to extend the set of parameters they can handle while keeping the same signature for SetPar().

Implements MPSolver.

◆ SetPricing()

void SetPricing ( cHpNum Brk = Inf< HpNum >() )

inline

At each "outer" iteration, i.e. when a restricted optima is reached, the non-basic items are checked for insertion in the base. The MinQuad class implements a "Steepest - Reverse Entering Order with Early Break" pricing, that is:

in principle, all non-basic items are checked and the item with the most negative directional derivative (the mostly violated dual constraint), if any, is put in the base; (unlikely) ties are break since the items are (essentially) checked in Reverse Entering Order, i.e. items that have entered first are checked last;
however, pricing is interrupted as soon as an item with derivative <
- Brk * BDim * | f( < current point > ) | is found (the BDim factor is because it is assumed that no multiplier will be larger than 1 / BDim, hence Brk * BDim is an upper bound on the expected decrease in f()).

Setting Brk == 0 (the default if SetPricing() is not called) means that the pricing is in fact a "pure" Reverse Entering Order; the most recently entered item with negative directional derivative is selected. Note that this avoids to calculate the directional derivative for all the items entered before that one, hence it is less expensive. On the other hand, setting Brk == Inf< HpNum >() means using a "pure" Steepest pricing, where just the item with the most negative directional derivative is selected; this may help in reducing the overall iterations count, but it is more expensive, and therefore an intermediate value of Brk may help.

The value of Brk can be changed at any time.

◆ Sett()

void Sett ( cHpNum tt = 1 )

inlineoverridevirtual

Sets the value of the proximal parameter, t, to tt. Prior to the first call to Sett(), t is taken to be equal to 1.

Implements MPSolver.

◆ SolveMP()

MPStatus SolveMP ( void )

overridevirtual

Attempts to solve the current Master Problem.

Note: The bundle for some components of Fi may be empty; if this happens, those components must just be temporarily ignored (like they did not exist) in the solution of the MP. If all the "sub-bundles" for each of the components are empty, what is solved is just a "pure feasibility" MP which returns just any point in the polyhedron defined by the constraints, if any. If there are neither subgradient nor constraints, then the optimal (both primal and dual) solution must be all-0.; The last sentence is not valid if there there are "easy" components of Fi() [see FiOracle::GetBNC() ...], since in this case the primal solution d* of the MP is typically non-0 even if there is no subgradient for any of the "difficult" components; what happens is that the bundle is not empty since "those of the easy components always contain all the possible subgradients".

The method must return:

kOK if the solver found an optimal solution;

kUnbndd if the MP is primal unbounded: this can only happen with some "not-really-stabilizing" terms D_t, and should always be solvable by properly increasing the proximal parameter t;

kUnfsbl if the MP is primal unfeasible (dual unbounded or empty, see ReadMult() below);

kStppd the algorithm has been stopped because the time/resources allotted to solve the MP have been depleted; this is not a "serious" condition, in that it can be "solved" by providing the MPSolver with more time/resources (usually, just calling it again, possibly multiple times);

kError in case of a failure in the MP solver.

If the "active set technique" is being used [see SetActvSt() below], the problem that is solved is actually a restriction of the "real" MP, where (possibly many) primal variables d[ i ] are forced to 0; this "restricted" MP may be empty (so that the solver might have to return kUnfsbl) while the full MP is nonempty. Hence, after a kUnfsbl return a "price in" [see Readd() below] should be done to find if new variables can to be added to the "restricted" MP in order to try to make it nonempty. Thus, in the unfeasible case ReadMult() [see below] must return the multipliers that make a feasible ascent extreme ray in the dual, so that the corresponding direction returned by Readd() [see below] is nonzero on variable ‘i’ (strictly positive if ‘i’ is constrained) if and only if that variable has to be added.

Implements MPSolver.

◆ SubstItem()

void SubstItem ( cIndex Nm )

overridevirtual

Although having multiple copies of the same item in the bundle is legal, it is also useless and it should be avoided. If CheckItem() returned a "valid" name (< Inf< Index >()), then SubstItem( Nm ) can be used to replace the current item in the bundle with name ‘Nm’ with SG. It is assumed that ‘Nm’ is the name of an item element-wise identical to SG (but possibly with different Ai), typically the name returned by CheckItem(). Typically, this operation makes sense when the Ai (Right Hand Side/linearization error) of the new item is smaller than that of the existing copy in the bundle. Thus, SubstItem( Inf< Index >() ) - that would operate on the (only) (sub)gradient of the 0-th component of Fi - cannot be called.

Implements MPSolver.

◆ WComponent()

Index WComponent ( cIndex i )

inlineoverridevirtual

Returns the name of the component that the item ‘i’ is relative to; a return value of Inf< Index >() means that no item with name ‘i’ is in the bundle. Note that a return value of 0 is possible only if the item is a constraint, since the 0-th component may have constraints but no subgradients: its only (sub)gradient is dealt with in a special way and it has no name.

Implements MPSolver.

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

QPPnltMP/QPPnltMP.h

Public Member Functions

Private Member Functions

Private Attributes

Additional Inherited Members

Member Function Documentation

◆ AddActvSt()

◆ AddVars()

◆ BCSize()

◆ BSize()

◆ CalculateZ()

◆ ChangeCurrPoint() [1/2]

◆ ChangeCurrPoint() [2/2]

◆ ChangesMPSol()

◆ CheckCnst()

◆ CheckIdentical()

◆ CheckSubG()

◆ ChgAlfa() [1/3]

◆ ChgAlfa() [2/3]

◆ ChgAlfa() [3/3]

◆ ChgSubG()

◆ EpsilonD()

◆ GetItem()

◆ GiTG()

◆ GiTilde()

◆ GiTLB() [1/2]

◆ GiTLB() [2/2]

◆ IsNN()

◆ IsSubG()

◆ MakeLambda1()

◆ MaxName()

◆ NumBxdVars()

◆ NumNNVars()

◆ Readd()

◆ ReadDStart()

◆ ReadDt()

◆ ReadFiBLambda()

◆ ReadGid()

◆ ReadLBMult()

◆ ReadLinErr()

◆ ReadLowerBound()

◆ ReadMult()

◆ ReadSigma()

◆ ReadZ()

◆ RmvActvSt()

◆ RmvItem()

◆ RmvItems()

◆ RmvVars()

◆ SensitAnals()

◆ SetActvSt()

◆ SetDim()

◆ SetItem()

◆ SetItemBse()

◆ SetLowerBound()

◆ SetMaxVarAdd()

◆ SetMaxVarRmv()

◆ SetMPLog()

◆ SetPar()

◆ SetPricing()

◆ Sett()

◆ SolveMP()

◆ SubstItem()

◆ WComponent()