Compile-time switches in QPPnltMP.h

Macros
#define	HV_NNVAR   1
#define	G_IMPLM   0
#define	ADD_CNST   0
#define	RECOMPUTE_GTZ   0

Detailed Description

Some relevant switches are defined in MinQuad.h and BMinQuad.h. mandatory switches* (the code won't compile/run otherwise) are

LAZY_Q 0 if G_IMPLM > 1 (MinQuad.h) SIGNAL_MBCHG 0 (BMinQuad.h) SIGNAL_B2CHG 0 (BMinQuad.h)

Setting

TWOSIDED 1 (BMinQuad.h)

is required if upper bounds on the variables are present [see GetUB() in FiOracle.h]; if they are not, setting TWOSIDED == 0 saves some memory.

Obviously, switches in BMinQuad.h have no influence if HV_NNVAR == 0.

Although the compile-time switches are generally thought to be orthogonal to each other, certain combinations make no sense and should be avoided. Some strongly advised switches are

CONSTR 0 if ADD_CNST == 0 (MinQuad.h)

Macro Definition Documentation

ADD_CNST

#define ADD_CNST   0

If ADD_CNST == 1, general linear constraints on the Lambda space are allowed: automatic generation of constraints is done for cases where the feasible set is not know a priori [see Fi() and SetGi() / GetGi() below].

From a "primal" viewpoint, constraints are usually needed when the set X is not* compact, and therefore the Lagrangean subproblem can be unbounded: in this case, constraints correspond to extreme rays of X.

G_IMPLM

#define G_IMPLM   0

The two computationally expensive tasks of the (QP) algorithm are the calculation of the entries of the Hessian matrix Q[][] (each time a new item is inserted) and the calculation of the entries of the tentative direction d[] (at each iteration, and possibly more than once). How these two tasks are accomplished is in large part controlled by the switches LAZY_Q in MinQuad.h and LAZY_D in BMinQuad.h: however, another important issue is how the set of items (Bundle) is implemented.

There are essentially two ways: either by columns or by rows. A third possibility is clearly that of having both representations. Furthermore, in the latter case another degree of freedom is available, that is which of the two forms have to be used for each task.

Each choice has its pros and cons, depending on the instance (max dim. of the Bundle vs number of Multipliers), on other algorithmic options (wheter or not a LVG is used) and on the target architecture (caching etc.). All these issues are controlled by this switch, that has the following four possible values:

0 => the Bundle is implemented by columns only, i.e. as a set of NumVar-vectors each one being an item;

1 => the Bundle is implemented by rows and columns, that is both forms are kept: however, the column-wise implementation is used for calculating the entries of Q[][] while the row-wise implementation is used for calculating the entries of d[];

2 => as for 1, the Bundle is implemented by rows and columns; however, in this case the row-wise implementation is used for calculating the entries of Q[][] while the column-wise implementation is used for calculating the entries of d[];

3 => the Bundle is implemented by rows only, i.e. as a set of (max Bundle dim.)-vectors each one containing one entry of all the items: in this case, LAZY_Q must be 0 [see MinQuad.h].

4 => as 3, plus memory is allocated and deallocated on the fly to keep the number of allocated rows to the bare minimum.

Clearly, if only the column-wise implementation is available (G_IMPLM == 0) or only the row-wise implementation is available (G_IMPLM >= 3), they are used for both the tasks.

HV_NNVAR

#define HV_NNVAR   1

If no Multipliers are constrained to be NonNegative (NN), the QPPenaltyMP class can inherit directly from the base MinQuad class rather than from the derived class BMinQuad, saving time and space; in fact, if ! HV_NNVAR the BMinQuad.* files need not to be compiled and linked with the code. Obviously, tring to solve a problem with NN Multipliers and HV_NNVAR == 0 will result in an exception being thrown.

RECOMPUTE_GTZ

#define RECOMPUTE_GTZ   0

The scalar products between the subgradients G_i and z* are crucial because they are used to update the linearization errors during a Serious Step. This means that numerical errors accumulate into linearization errors, and there is no way in which they can be checked for their true value and the errors corrected. This may lead to them being very far off their true value, which may impair the correctness of the results of the bundle algorithm.

Although the flaw is inherent in the process of continuously updating the linearization errors, it can be minimized by computing the scalar products as accurately as possible. However, in MinQuad they are also computed "indirectly" during the optimality checks, and for efficiency one would typically use these already available values. Since they can be affected to errors, the RECOMPUTE_GTZ switch is available to allow to ignore them and rather use freshly computed scalar products, trading off a higher computational cost for (hopefully) better accuracy.

Note that the re-computation is only done when it actually matters, i.e., right before a Serious Step is performed.