NDOSolver / FiOracle: BMinQuad Class Reference

#include <BMinQuad.h>

Inheritance diagram for BMinQuad:

Public Member Functions
	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.

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

Protected Member Functions
virtual void	GiTG (cIndex i, QuRow Qi, cIndex iMax)=0

virtual cSgRow	GiTilde (cIndex i)=0

virtual void	CalculateZ (LMRow z)=0

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

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

void	RecomputeRealAlfa (void)

Protected Member Functions inherited from MinQuad
void	AlfaChanged (void)

Protected Attributes
Index_Set	Base2

Index	B2Dim
	Dimension of Base2.

Index_Set	MBase2

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

Index_Set	MvdVars

Protected 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

Private Member Functions
void	CalcOptDir (HpNum ti)

void	AddToB2 (cIndex_Set MVD, cIndex MVDd)

void	RmvFrmB2 (cIndex_Set MVD, cIndex MVDd)

void	AddToMB2 (cIndex_Set MVD, cIndex MVDd)

void	RmvFrmMB2 (cIndex_Set MVD, cIndex MVDd)

void	CutOffConstrs (cIndex_Set MVD, Index MVDd)

void	PutInConstrs (cIndex_Set MVD, Index MVDd)

void	ClearTabooList (void)

void	MemDealloc (void)

void	CheckB2 (void)

void	CheckMB2 (void)

void	CheckGS (void)

void	CheckRA (void)

void	CheckDS (void)

Private Attributes
HpNum	eD

HpNum	Bf

HpNum	bNorm

Index	MaxVarAdd

Index	MaxVarRmv

Index	TLDim

Index	NNStop

HpRow	RealAlfa

Index	SpaceDim

char *	GS

LMRow	bounds

LMRow	lb

LMRow	ub

LMRow	di

LMRow	tmpdi

OPTtimers *	BMQt

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

Detailed Description

BMinQuad solves the modified version of the (QP)

(P) min v + 1/(2 ti) || d ||_2^2 s.t. v * e_i >= G[ i ] * d - Alfa[ i ] , i = 0 .. n - 1 l[ j ] <= d[ j ] <= u[ j ] \forall j

where some of the lb[ i ] can be - INF and some of the ub[ i ] can be + INF (actually, finite upper bounds are only allowed if TWOSIDED > 0, (see), and the corresponding dual problem. Although these problems are very similar to the standard ones solved by MinQuad, there are some differences, the main one being that it is no longer true that d^* = - ti * z^*, but rather

d[ i ]^* = min( u[ i ] , max( l[ i ] , - ti * z[ i ]^* ) ).

The user is assumed to be familiar with the base class MinQuad [see MinQuad.h], and in particular with the issue of the "virtual items". As a resume, MinQuad never deals directly with items (e.g. vectors of SgNum's), but rather allow the user to add and remove items from the bundle by means of a symbolic "name". The necessary information is then requested by means of the GiTG[j]() method.

Analogously, BMinQuad works with "virtual variables: all it knows is that a certain number of variables (<= SDim) have been "declared" by invoking AddVars() or InitialSetUp() [see]. Variables can be either constrained or unconstrained; in the former case, lower [and upper] bounds have to be given, that can however also be -[+] infinity. BMinQuad identifies these variables with the "name" ‘i’ (in the range 0 .. SDim - 1) that the user has given them, and that must be unique; then, it may ask for the i-th entry of something (a subgradient, the whole matrix G, the aggregated subgradient z ...), requiring the entry relative to the variable whose "name" is ‘i’. A constrained variable can be turned into an unconstrained one by invoking MakeVarUnCnstr(), and vice-versa with MakeVarCnstr(); this can be repeated any number of times. BMinQuad "thinks" that the "declared" variables are the only ones of the problem; this is not necessarily true, however, since other unconstrained variables can be "implicitly" dealt with by "silently" adding their contribution to the results of GiTG[j]() [see] as in the base class MinQuad. In fact, "unnamed" unconstrained variables can be added / removed from the problem by calling the methods [Add/Cut]SGSpaceDim(). As its base class MinQuad, BMinQuad is an abstract class, since it has pure virtual methods; see the "pure virtual methods" part of the protected interface below]. Hence, instances of BMinQuad cannot be built, and a derived class has to be defined where such methods are actually implemented.

Constructor & Destructor Documentation

◆ BMinQuad()

BMinQuad ( void )

Constructor: initialize the object, but, as in the base MinQuad class, it does not allocate memory, as this is done is SetMaxDim() [see below].

Member Function Documentation

◆ ActiveVars()

cIndex_Set ActiveVars ( void )

inline

Returns the set of "active" variables, i.e., where d[ i ] is set to the bound that is violated by - ti * z[ i ]. Such a set is described by the protected field Base2[]; [see the methods in the pure virtual protected interface]. However, to let this information available to non-derived classes, it is also returned by ActiveVars().

◆ AddConstr()

void AddConstr	(	cIndex	n,
		cHpNum	alfan )

virtual

Add to the current bundle one more constraint whose "name" in 'n'. Note that nothing is known about the constraint (item), except that somewhere "outside" there is a constraint whose name is 'n' and whose Right Hand Side is alfan.

IMPORTANT ADVICE: in constrained problem, a wrong scaling of constraints may have an adverse influence on the behaviour of the algorithm. In fact, even though the constraints C * d <= e and [ k * C ] * d <= k * e (for k a positive scalar) are equivalent in theory, using a vector C whose norm is much different from the "average" norm of the subgradients in the bundle may result in a badly conditioned problem. Since error-recovering procedures are costly, and may cause significant losses of time/precious information, the caller should scale the constraints appropriately.

Reimplemented from MinQuad.

◆ AddD()

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

Set L1 = L2 - ( Tau / ti ) * d^*, a typical "move" in the primal space.

The intended "format" of L2 and L1 is the same of Read[Z/D](); that is, L2 and L1 are considered at least as long as the maximum current name of a variable, and the result relative to variable ‘i’ is taken from L2[ i ] and written to L1[ i ] (the components not corresponding to declared variables are left untouched).

The method recognises the case Tau = t and deals with it explicitly.

◆ AddDSprs()

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

Set L1 = L2 - ( Tau / ti ) * d^*, a typical "move" in the primal space.

The intended "format" of L2 and L1 is the same of Read[Z/D]Sprs(); that only the first NV components of L2 and L1 are used.

The method recognises the case Tau = t and deals with it explicitly.

◆ AddSubGrad()

void AddSubGrad	(	cIndex	n,
		cHpNum	alfan )

virtual

Add to the current bundle one more subgradient whose "name" in 'n'. Note that nothing is known about the subgradient (item), except that somewhere "outside" there is a subgradient whose name is 'n' and whose linearization error is alfan.

Reimplemented from MinQuad.

◆ AddVars() [1/2]

void AddVars	(	cIndex	strt,
		cIndex	hwmny )

Like AddVars( whch , hwmny ), but adds all those variable with names from ‘strt’ to ‘strt + hwmny - 1’, extremes included, and it can only be called if strt is larger than the name of any declared variable. Thus, none of the variable can be declared just prior to the call of the method.

◆ AddVars() [2/2]

void AddVars	(	cIndex_Set	whch,
		cIndex	hwmny )

Adds ‘hwmny’ new variables to the set of declared variables, those whose names are found in the set whch[], that has to be ordered in increasing sense, without replicated elements and Inf< Index >()-terminated (that is, whch[ hwmny ] == Inf< Index >()). None of the variable can be declared just prior to the call of the metho.

The type of the variable must be written in GetVars()[ i ] prior to the call: see InitialSetUp() above for how to choose the value.

Note that the "basic type" (constrained or unconstrained) of a variable is maintained even when the variable is removed [see RemoveVars()]; hence, if ‘i’ has been constrained previously, it has been removed and it is created again, it will be taken as constrained unless GetVars()[ i ] is explicitly changed (and the same holds for unconstrained variables).

If ‘i’ is a constrained variable, the corresponding lower[upper] bound must be written in Lower[Upper]Bounds()[ i ] prior to the calls as for ChangeBounds().

◆ CalculateZ()

virtual void CalculateZ ( LMRow z )

protectedpure virtual

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.

Implemented in QPPenaltyMP.

◆ ChangeAlfa() [1/2]

void ChangeAlfa ( cHpNum DeltaAlfa )

virtual

Performs a "relative" change of all the vector Alfa[], i.e.

            / DeltaAlfa   'i' is a subgradient

Alfa[ i ] += | \ 0 'i' is a constraint

This is the typical correction that ought to be done in bundle algorithms when "nonexact" functions have to be handled, and can be managed faster than the "general" case above.

Reimplemented from MinQuad.

◆ ChangeAlfa() [2/2]

void ChangeAlfa	(	cIndex	i,
		cHpNum	DeltaAlfai )

inlinevirtual

Changes the Alfa (linearization error of a subgradient or RHS of a constraint) of the item with name 'i', adding it DeltaAlfai; that is, at the end of the call

Alfa[ i ] = < old Alfa[ i ] > + DeltaAlfai.

Reimplemented from MinQuad.

◆ ChangeBounds()

void ChangeBounds ( void )

Change the lower [and upper, if any] bounds on the variables. The new values must first be written in the appropriate entries of Lower[Upper]Bounds() (that does not return read-only pointers just because of that), and then ChangeBounds() must be called. The same technique is used for passing the bounds to InitialSetUp() and AddVars().

Since it is assuned that d = 0 should always be a feasible solution, it is required that l[ i ] <= 0 <= u[ i ] for each constrained variable ‘i’.

If TWOSIDED > 0, it makes sense to allow "mixtures" of variables with only one (upper or lower) bound and variables with two bounds; hence, l[ i ] can be set to - LMINF and u[ i ] can be set to + LMINF, that will be recognized and appropriately handled. However, it is required that at least one of the bounds be finite; this is not restrictive, since a variable i with both infinite bounds is simply unconstrained, and it should be explicitly declared such [see InitialSetUp(), AddVars() and MakeVarUnCnstr()]. Consequently, if TWOSIDED == 0 it is not allowed to pass - LMINF as a lower bound for a constrained variable.

◆ DPerG()

HpNum DPerG ( cSgRow g )

Returns

( 1 / ti ) * ( d[] * g[] )

i.e. the (scaled) scalar product between the direction d[] and the vector g[]. g[] is assumed to be in the "naive" format, i.e. a vector of SgNum such that g[ i ] is the entry of the variable whose "name" is i. The "- (1 / ti)" scaling factor is used for this result to be immediately passed to the SetGTz() method of the base class [see MinQuad.h and ReadGTz()].

◆ GetVar()

char GetVar ( cIndex i )

inline

Describes the status of each variable; see InitialSetUp() above for how to decode the returned value.

Note that the "basic type" (constrained or unconstrained) of a variable is maintained even when the variable is removed [see RemoveVar() below]; hence, GetVar( i ) & NNVar() is nonzero for a variable that is not currently defined if and only if it has been a constrained variable the last time that it has been destroyed. By default, the variables are all constrained initially (even those that are not defined).

◆ GetVars()

char * GetVars ( void )

inline

GetVars()[ i ] == GetVar( i ); the returned pointer is not a read-only one, since writing in that memory area is allowed prior to a call to InitialSetUp(), AddVar() or MakeVarCnstr() for passing a "guess" on the initial statuses of the variables.

◆ GiTG()

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

protectedpure virtual

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

Implemented in QPPenaltyMP.

◆ GiTilde()

virtual cSgRow GiTilde ( cIndex i )

protectedpure virtual

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 ];

Implemented in QPPenaltyMP.

◆ GiTLB() [1/2]

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

protectedpure virtual

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.

Implemented in QPPenaltyMP.

◆ GiTLB() [2/2]

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

protectedpure virtual

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

Implemented in QPPenaltyMP.

◆ InActiveVars()

cIndex_Set InActiveVars ( void )

inline

Returns the set of "inactive" variables, i.e., where d[ i ] = - ti * z[ i ]. Such a set is described by the protected field MBase2[]; [see the methods in the pure virtual protected interface]. However, to let this information available to non-derived classes, it is also returned by InActiveVars().

◆ InitialSetUp()

void InitialSetUp ( void )

InitialSetUp allows some initializations to be performed more efficiently, and some user-defined knowledge to be passed to the solver. The method reads the first SDim entries of the vector of chars returned by GetVars() and sets the variables according to the values found there.

The type of a variable, that is coded in the bits of the char: if vi = GetVars()[ i ], one has

vi & NNVar() is nonzero <=> ‘i’ is constrained to be nonnegative (this is guaranteed to be coded in the first bit);
vi & IsVar() is nonzero <=> ‘i’ is defined in (P);
vi & AcVar() is nonzero <=> ‘i’ is a nonnegative variable that is set to one of its bounds in the optimal solution of (P); if TWOSIDED == 0, the bound is clearly the lower one;
vi & UBVar() is nonzero <=> ‘i’ is a nonnegative variable that is set to its upper bound in the optimal solution of (P) (this should be used only if TWOSIDED > 0).

For constrained variables, the values written there prior to a call to InitialSetUp() are meant to provide a guess of the variables that will be fixed at their lower[upper] bounds in the optimal solution of the problem: a good guess can considerably decrease the time required to solve the problem. Hence set GetVars()[ i ] to

NNVar() | IsVar() | AcVar() | UBVar() if the entry d[ i ] of the optimal solution (direction) corresponding to variable ‘i’ is probably == u[ i ];

NNVar() | IsVar() | AcVar() if d[ i ] == l[ i ] (probably);

NNVar() | IsVar() if l[ i ] < d[ i ] < u[ i ] (probably);

IsVar() if ‘i’ is declared in (P) as unconstrained;

NNVar() if ‘i’ is not declared in (P), but it will be constrained;

0 if ‘i’ is not declared in (P), but it will be unconstrained.

The bit-wise coding allow to set each field separately; for instance, vi |= IsVar() sets the variable as declared whatever its "sign" be, while vi &= ~IsVar() sets the variable as not declared.

The default (i.e. if nothing is written in vi) is that the variable is not declared but it is constrained. Note that the "basic type" (constrained or unconstrained) of a variable is maintained even when the variable is removed [see RemoveVars()]; hence, if ‘i’ has been unconstrained previously and it has been removed, GetVar( i ) & NNVar() will be zero instead.

If the method is called prior to the first iteration, there are not general linear constraints in the bundle but exactly one subgradient is available, the optimal solution will just be - ti * < the subgradient > "projected" over the box constraints, hence the above sets can be exactly guessed (e.g. - ti * subg[ i ] <= l[ i ] ==> AcVar()).

Note that a call to InitialSetUp() will overwrite any previous setting, making all and only these variables declared. The values of the bounds for the constrained variables must be provided as in ChangeBounds().

If the bundle is empty, the method is very cheap; if there are items, the whole matrix Q of the problem must be recomputed. This is done by invoking ChangeQ() [see MinQuad.h], which in turn may call GiTG[j]() [see] for calculating the entries. Hence, it is better that this method be called before inserting items in the bundle, if possible.

◆ LowerBounds()

LMRow LowerBounds ( void )

inline

Access the lower bounds on the variables. Return a pointer to a vector containing the current values of the bounds, that changes at each call to MoveAlongD(): LowerBounds()[ i ] holds the lower bound of the variable with name ‘i’.

◆ MakeVarCnstr()

void MakeVarCnstr ( cIndex i )

Converts the unconstrained variable ‘i’ into a constrained variable, reading its "status" and its lower [and upper] bound like AddVar() does. It is uncorrect to call this method with an i not being the name of a declared variable, and also if ‘i’ is already a constrained variable.

◆ MoveAlongD()

void MoveAlongD	(	cHpNum	Tau,
		cHpNum	DeltaFi )

virtual

Has the same effect than that of the base class, but also the bounds on the variables are updated accordingly. Note that steps Tau > ti lead to an unfeasible solution if ActiveVars()[] is nonempty (and see the comments to MinQuad::MoveAlongD() for linear constraints).

Important note: to update the bounds on the constrained variable named ‘i’, the i-th component of the latest direction d is needed; this is clearly available if i was already constrained at the time when SolveQP() was last invoked, but it is not if i has been created in the meantime with AddVars() or MakeVarCnstr( i ).

Therefore, in order to make MoveAlongD() work properly, it needs

either that no new constrained variables be added between the end of SolveQP() and the call to MoveAlongD();
or that SetD( i , ... ) is invoked after the "creation" of the i-th variable to provide the required information.

Reimplemented from MinQuad.

◆ MoveVar()

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

Renames the variable with name ‘i’, giving it name ‘j’, but maintaining the same type (constrained or unconstrained), bounds and so on. There must not be already a variable with name ‘j’ among the declared ones.

In the typical use, ‘i’ is the last variable (the one with largest name); if this is the case, setting iIsLst == true (the default) allows some operations to be performed more efficiently.

◆ ReadAlfa() [1/2]

void ReadAlfa ( HpRow NewAlfa )

virtual

Writes the current vector of Alfas, i.e., Alfa[ i ] is the item with "name" i, in the vector NewAlfa.

Reimplemented from MinQuad.

◆ ReadAlfa() [2/2]

cHpRow ReadAlfa ( void )

inlinevirtual

Returns a read-only pointer to the current vector of Alfas, i.e., Alfa[ i ] is the item with "name" i.

Reimplemented from MinQuad.

◆ ReadD()

void ReadD	(	LMRow	d,
		cIndex	CpyFrst = 0 )

Analogous ReadZ( LMRow ) for the optimal primal solution d; that is, d[ i ] = min( u[ i ] , max( l[ i ] , - ti * z[ i ] ) ) where z[] is the vector reported by ReadZ[Sprs]().

The parameter CpyFrst that all the first CpyFrst entries of the vector d have to be written, even those corresponding to non-declared variables. If CpyFrst > 0, it is assumed that "correct" values for z have been provided during the calculation [see ReadZ()] and they are available in the data structure: - ti * z[ i ] is then written in d[ i ] for all non-declared variables i < CpyFrst. Otherwise, only the entries of d[] corresponding to declared variables are written.

◆ ReadDSprs()

void ReadDSprs ( LMRow d )

Analogous ReadZSprs( LMRow ) for the optimal primal solution d; that is, d[ i ] = min( u[ i ] , max( l[ i ] , - ti * z[ i ] ) ) where z[] is the vector reported by ReadZSprs().

◆ ReadGTz()

HpNum ReadGTz ( cIndex i )

virtual

Same meaning as in the base class, except that here ReadGTz( i ) returns

( d^* / ti ) * G[ i ]

i.e., DPerG( G[ i ] ). This is the same as z^* * G[ i ] if there are no "active" variables.

Reimplemented from MinQuad.

◆ ReadSigma()

HpNum ReadSigma ( const bool IncldCnst = true )

inlinevirtual

Same meaning as in the base class, i.e.,

f() = (1/2) * ti * ReadzNorm() + ReadSigma(),

but it is important to remark that now ReadSigma() contains an extra term concerning the bounds of the "active" variables; since the "active variables" corresponds to constraints in Base[], their contribution can be eliminated (together with that of ordinary constraints) by setting IncldCnst == false.

Important Note: if BEXACT == 0, it may give wrong results if called after MoveAlongD(), ChangeBounds(), RemoveVar() or MakeVarUnCnstr().

Reimplemented from MinQuad.

◆ ReadVNames()

Index ReadVNames ( Index_Set VNames )

Writes the (ordered) names of declared variables in the first NV components of VNames, and returns NV.

◆ ReadZ() [1/2]

void ReadZ ( LMRow z )

Like ReadZ( void ), but writes z^* into z. z must be at least as long as the maximum number i that has been used as a name for a variable. Note that z[ i ] is written if and only if ‘i’ is the name of a declared variable, all the other entries being left untouched.

◆ ReadZ() [2/2]

cLMRow ReadZ ( void )

inline

All the variables "live" in the space of components [ 0 .. SDim - 1 ], so that any object in the primal space (the direction d or a subgradient) is naturally viewed as a vector (of LMnum's) with SDim components. This method return a read-only pointer the "aggregated subgradient" z^*, that is for each declared variable ‘i’ one has

z[ i ] = Sum{ h in Base } G[ Base[ h ] ][ i ] * Mult[ h ].

Note that z^* may not be, strictly speaking, an "aggregate subgradient", as constraints might be in Base: however, the constraints are subgradients of the characteristic function of the feasible set.

Note that the content of the entries of z[] not corresponding on a declared variable the depends on LAZY_D and the (user-provided) implementation of CalculateZ(). If LAZY_D > 0 then again only the entries corresponding to constrained variables are significant, but if LAZY_D == 0 then the returned pointer points to the same vector that has been passed to CalculateZ(), and that has not been modified ever since. Hence, if some sort of "correct values" have been written there, they will still be there.

◆ ReadzNorm()

HpNum ReadzNorm ( void )

inlinevirtual

Same meaning as in the base class, i.e.,

f() = (1/2) * ti * ReadzNorm() + ReadSigma(),

but it is important to remark that now

 ReadzNorm() = || d^* / ti ||_2^2 != || z^* ||_2^2.

That is, ReadzNorm() reports the norm of the scaled direction d^*, that is no longer equal to the "aggregate subgradient" z^*.

Important Note: if BEXACT == 0, they may give wrong results if called after MoveAlongD(), ChangeBounds(), RemoveVar() or MakeVarUnCnstr().

Reimplemented from MinQuad.

◆ ReadZSprs()

void ReadZSprs ( LMRow z )

Like ReadZ( LMRow ), but gives z in a "sparse" format, i.e. it only uses the first NV positions of z, where NV is the total number of declared variables. The variables are ordered in ascending sense by their name, and the h-th variable (h = 1 .. NV - 1) is written in z[ h ]. The names and the number of variables should be known by the calling program, but they can be queried by a call to ReadVNames().

◆ RecomputeRealAlfa()

void RecomputeRealAlfa ( void )

protected

In case some data of the problem changes, RealAlfa has to be recomputed from scratch (as opposed to being smartly updated); this method does just that.

◆ RemoveVars()

void RemoveVars	(	cIndex_Set	whch,
		Index	hwmny )

Deletes the variable with name ‘i’ from the set of declared variables, regardless to its type (constrained or unconstrained).

◆ RenameVars()

void RenameVars ( cIndex_Set whch )

Renames all the variables to make the set of variable names fit with the elimination of the variables whose names are contained in the set ‘whch’ (ordered in increasing sense, without duplications and Inf< Index >()-terminated).

The removal of a variable with RemoveVar() from the set of declared variables can be thought to be a "temporary" operation; in fact, it is arranged in such a way that re-declaring the variable with AddVar() is very simple (for instance, the type of the variable is kept).

A more "permanent" removal of a variable can be required, where all the information about the variable is lost. This is what happens to the single variable ‘j’ in MoveVar() [see above]. This method provides means for eliminating a (large) set of variables all at once.

The set ‘whch’ must contain names of undeclared variables (that is, variables that have never been declared with InitalSetUp() or AddVar(), or finally undeclared with either RemoveVar() or MoveVar()). All the variables, both declared and undeclared ones, are renamed as to fit with the elimination of those variables. For instance, if SDim == 10 [see SetMaxDim()] and whch = { 2, 3, 7 }, after a call to RenameVars() one has

current name 0 1 2 3 4 5 6 7 8 9 previous name 0 1 4 5 6 8 9 n n n

where "n" means "this is a new variable, completely unrelated to the previous ones, and currently undeclared".

◆ SensitAnals1()

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

virtual

Let x( t ) be the optimal solution of (D) as a function of the parameter t, and let v( t ), z( t ) be the corresponding solutions of (P) (actually, d( t ) is a solution of (P), but d( t ) = - t * z( t )); there exists an interval [tMin, tMax] [see SensitAnals3()] in which the currently optimal base stays optimal. This function reports three numbers v1, v2 and v3 such that within that interval

v( t )               =    t * v1 + v2

|| z( t ) ||^2       =  - v1 + ( 1 / t )^2 * v3

Alfa * x( t )        =  - v2 - ( 1 / t ) * v3

Outside the "stability interval", the above expressions give lower approximations of the real figures.

Reimplemented from MinQuad.

◆ SetBMQTime()

virtual void SetBMQTime ( const bool TimeIt = true )

inlinevirtual

SetBMQTime() decides whether or not an OPTtimers object is used to compute the solution time of the BTT algorithm.

Note that time accumulates over the calls; calling SetBMQTime(), however, resets the counters, allowing to time specific groups of calls.

◆ SetD() [1/2]

void SetD	(	Index	i,
		LMNum	Di )

inline

Used to provide the i-th component of the latest direction d (without the (-t) factor) relative to the newely "created" constrained variable i, prior to a call to MoveAlongD().

◆ SetD() [2/2]

LMRow SetD ( void )

inline

Like SetD( i , Di ), but the second returns a pointer to a vector such that SetD( i , Di ) is equivalent to SetD()[ i ] = Di.

◆ SetEpsilonD()

void SetEpsilonD ( HpNum NeweD = 0 )

In the code, a number eD is used as a measure of the relative precision required for the box constraints: l[ i ] <= d[ i ] is satisfied if

d[ i ] >= l[ i ] - t * eD * size( l[ i ] )

and analogously for d[ i ] <= u[ i ].

eD is automatically increased by SolveQP() to try to face badly conditioned problems: this method allow to set its current value. Passing 0 (clearly, an impossible value) to SetEpsilonD() resets eD to some "default" value.

◆ SetGTz()

void SetGTz	(	cIndex	i,
		cHpNum	GTzi )

virtual

Provides the scalar product between z^* and the newely inserted item 'i' prior to a call to MoveAlongD() [see above].

Reimplemented from MinQuad.

◆ SetMaxDim()

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

virtual

Same meaning as in the base MinQuad class; here, however, the third parameter is not optional, and 0 is not a valid value.

Reimplemented from MinQuad.

◆ 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".

◆ SettmpD()

void SettmpD ( LMRow td )

inline

If CNDVD_TMP > 0, a temporary vector of SDim LMNum's must be provided by the calling code prior to a call to SolveQP() by calling SettmpD(). The temporary may become "property" of BMinQuad, but if it happens then the same amount of memory becomes available: hence, if the calling code wants to reclaim that memory, it must require its address by calling GettmpD() after SolveQP().

◆ SolveQP()

MQError SolveQP ( HpNum ti )

virtual

Solves the problem with the current data, i.e. the current bundle, Alfa, ti and lower[/upper] bounds. The second level of dynamic tolerances adjustment is implemented here inside: hence, eD [see SetEpsilonD() above] can be changed to face increase "requests".

Exit codes:

kOK , kQPPrimUnbndd = as in the base class;
kFatal = either MinQuad::SolveQP() returned a kFatal, or even adjusting eD was not sufficient to handle the problems: that eD has been increased out of the bound.

Reimplemented from MinQuad.

◆ UpperBounds()

LMRow UpperBounds ( void )

inline

If TWOSIDED != 0, access the upper bounds on the variables. Return a pointer to a vector containing the current values of the bounds, that changes at each call to MoveAlongD(): UpperBounds()[ i ] holds the upper bound of the variable with name ‘i’.

Member Data Documentation

◆ Base2

Index_Set Base2

protected

Set of names of defined constrained variables at their LB or UB in the optimal solution

◆ MBase2

Index_Set MBase2

protected

Set of names of defined constrained variables that are not in Base2 or defined unconstrained variables

◆ MvdVars

Index_Set MvdVars

protected

Set of names of defined variables that are being moved from Base2 to MBase2 or vice-versa

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

QPPnltMP/BMinQuad.h

Public Member Functions

Protected Member Functions

Protected Attributes

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ BMinQuad()

Member Function Documentation

◆ ActiveVars()

◆ AddConstr()

◆ AddD()

◆ AddDSprs()

◆ AddSubGrad()

◆ AddVars() [1/2]

◆ AddVars() [2/2]

◆ CalculateZ()

◆ ChangeAlfa() [1/2]

◆ ChangeAlfa() [2/2]

◆ ChangeBounds()

◆ DPerG()

◆ GetVar()

◆ GetVars()

◆ GiTG()

◆ GiTilde()

◆ GiTLB() [1/2]

◆ GiTLB() [2/2]

◆ InActiveVars()

◆ InitialSetUp()

◆ LowerBounds()

◆ MakeVarCnstr()

◆ MoveAlongD()

◆ MoveVar()

◆ ReadAlfa() [1/2]

◆ ReadAlfa() [2/2]

◆ ReadD()

◆ ReadDSprs()

◆ ReadGTz()

◆ ReadSigma()

◆ ReadVNames()

◆ ReadZ() [1/2]

◆ ReadZ() [2/2]

◆ ReadzNorm()

◆ ReadZSprs()

◆ RecomputeRealAlfa()

◆ RemoveVars()

◆ RenameVars()

◆ SensitAnals1()

◆ SetBMQTime()

◆ SetD() [1/2]

◆ SetD() [2/2]

◆ SetEpsilonD()

◆ SetGTz()

◆ SetMaxDim()

◆ SetMaxVarAdd()

◆ SetMaxVarRmv()

◆ SettmpD()

◆ SolveQP()

◆ UpperBounds()

Member Data Documentation

◆ Base2

◆ MBase2

◆ MvdVars