Internal QP Solver for linearly constrained groundsets

Classes
class	ConicBundle::QPSolver
	QPSolver is the access point for ConicBundle to the internal constrained QP Solver, see Internal QP Solver for linearly constrained groundsets. More...
class	ConicBundle::QPSolverBasicInterface
	defines the abstract interface for QPSolverBasicStructures that the basic routines there need to access the cost and constraint data; it also defines the interface to QPSolverBasicStructures, how to call those routines and how to retrieve the results. More...
class	ConicBundle::QPSolverParameters
	parameters for steering the termination criteria and solution method of the solver More...
class	ConicBundle::QPKKTSolverObject
	abstract class for setting up and solving the primal dual KKT System within QPSolverBasicStructures More...
class	ConicBundle::QPDirectKKTSolver
	implements a direct KKT Solver variant of QPKKTSolverObject More...
class	ConicBundle::QPKKT_SolverStats
	Used for collecting statics in QPKKTSolverComparison: For each bundle subproblem there is a block QPKKT_ProbStats, which holds for each KKT system a block of QPKKT_KKTStats, which holds for each solver a block QPKKT_SolverStats (this). More...
class	ConicBundle::QPKKT_KKTStats
	Used for collecting statics in QPKKTSolverComparison: For each bundle subproblem there is a block QPKKT_ProbStats, which holds for each KKT system a block of QPKKT_KKTStats (this), which holds for each solver a block QPKKT_SolverStats. More...
class	ConicBundle::QPKKT_ProbStats
	Used for collecting statics in QPKKTSolverComparison: For each bundle subproblem there is a block QPKKT_ProbStats (this), which holds for each KKT system a block of QPKKT_KKTStats, which holds for each solver a block QPKKT_SolverStats. More...
class	ConicBundle::QPKKTSolverComparison
	This is a pseudosolver designed for producing comparative statistics on the performance of mainly iterative solvers for the interior point KKT systems of QPSolver. More...
class	ConicBundle::QPIterativeKKTSolver
	Iterative solver for the full symmetric, in general indefinite primal dual KKT System within QPSolverBasicStructures. More...
class	ConicBundle::QPIterativeKKTHASolver
	Iterative solver for the reduced symmetric, in general indefinite primal dual KKT System within QPSolverBasicStructures, where only H and A blocks remain, B and C are removed by Schur complements. If there is no A, PCG may used. More...
class	ConicBundle::QPIterativeKKTHAeqSolver
	Iterative solver for the reduced symmetric, in general indefinite primal dual KKT System within QPSolverBasicStructures, where only the block H and the equality rows of A remain, the inequalities of A as well as B and C are removed by Schur complements. If there are no equalities in A, PCG may used, but MinRes seems to be more stable. More...
class	ConicBundle::QPKKTPrecondObject
	Abstract Interface for preconditioners to be used with a QPIterativeKKTSolver and a CH_Matrix_Classes::IterativeSolverObject, see Interfaces and Classes for Iterative Solvers like PCG, MINRES and PSQMR. It will depend on the system setup and the solver method which preconditioning routines are called and what requirements the preconditioners have to fulfill. Feasible combinations lie in the responsibility of the caller and are not checked for correctness. More...
class	ConicBundle::QPKKTSubspaceHPrecond
	Subspace projection preconditioner for the H-block of the KKT-System assuming that B and C have been Schur complemented into the H-block. For the A-Block, if it is there, the identity is used. If there is no A-block, PCG may be used. More...
class	ConicBundle::QPModelBlockObject
	abstract interface for model blocks in the constrained QPSolver More...
class	ConicBundle::QPModelBlock
	combines and provides basic functionalities of QPModelDataObject and QPModelBlockObject, but is still abstract More...
class	ConicBundle::QPSumModelBlock
	implements a (virtual) cutting model being built of a (possibly recursive) sum of QPModelBlock cutting model instances for QPSolver More...
class	ConicBundle::QPConeModelBlock
	implements a QPModelBlock for conic cutting models in QPSolver More...
class	ConicBundle::InteriorPointBlock
	abstract interface for interior point vector/matrix variables and routines specific to primal dual complementarity conditions of symmetric cones More...
class	ConicBundle::NNCIPBlock
	interface for the interior point variable vector and routines specific to the primal dual complementarity conditions of the nonnegative cone More...
class	ConicBundle::SOCIPBlock
	interface for interior point variable and routines specific to primal dual complementarity conditions of a second order cone More...
class	ConicBundle::InteriorPointBundleBlock
	abstract interface for interior point routines specific to primal dual complementarity conditions of a symmetric cone with special routines for handling the bundle and the trace constraint More...
class	ConicBundle::NNCIPBundleBlock
	interior point variables and routines specific to primal dual complementarity conditions of a nonnegative cone with special routines for handling the bundle and the trace constraint More...
class	ConicBundle::SOCIPBundleBlock
	interior point variables and routines specific to primal dual complementarity conditions of a second order cone with special routines for handling the bundle and the trace constraint More...
class	ConicBundle::QPPSCOracleDataObject
	defines an interface for passing on oracle information to PSCIPBundleBlock More...

Detailed Description

If the groundset (see e.g. LPGroundset) of the convex optimization problem involves box constraints with a general quadratic proximal term (i.e. not just a diagonal) or general linear constraints even with diagonal proximal term, a constrained QP solver is required to determine the next candidate as the solution of the bundle subproblem. Because ConicBundle is designed to handle also nonpolyhedral cutting models arising from support functions over the second order cone and positive semidefinite cone the general solver is an intererior point method. More precisely, it implements a primal dual predictor corrector method.

The main visible object is QPSolver. This mainly serves as an interface for ConicBundle as it implements a QPSolverObject (for finding the next candidate via solving the quadratic bundle subproblem) and a QPDataPointer (for collection the cutting model information). The internal solver routines are mostly defined in QPSolverBasicStructures. The basic structures serve to describe all parts in connection with the linearly constraint groundset and the general iterative procedure of when to collect which data, when to solver the primal dual KKT-system and when to perform line searches. The central part of setting up and solving the primal dual KKT-system is supplied externally via the QPSolverParameters, which must specify a QPKKTSolverObject. Currently the following options exist for such an QPKKTSolverObject:

• QPDirectKKTSolver : by a Schur complement the quadratic term is computed into the lines of the linear constraints and the constraints describing the models. This system is then solved either with an aditional Schur complement by Cholesky or directly in indefinite form by Aasen's method.
• QPIterativeKKTSolver : It mainly offers a general interface for iterative methods, but also provides the matrix times vector multiplication for the entire KKT-System. This iterative solver class always just provides the matrix vector product for a special variant of the KKT-System in the style of a CH_Matrix_Classes::IterativeSystemObject, the actual iterative solver with a suitable preconditioner must always be specified during construction by passing a CH_Matrix_Classes::IterativeSolverObject and possibly a QPKKTPrecondObject that fits the iterative solver and the system variant. So far no specific preconditioner is implemented for this system configuration, but CH_Matrix_Classes::Psqmr and CH_Matrix_Classes::MinRes are possible iterative solver options.
• QPIterativeKKTHASolver : is dervied from QPIterativeKKTSolver and differs in that in the KKT-system the model block is Schur complemented into the lines of the prox-termin (the H block), but the linear constraints of the ground set (the A block) is left untouched. So the KKT-System is reduced to the H and A blocks and the class implements the matrix vector product for this system variant. A preconditioning class for this setting is provided in QPKKTSubspaceHPrecond, which provides various options for obtaining a preconditioner for the H-block (and so far only for the H-block) via subspace projection and low rank inversion. If the linear constraint block A is friendly, this works fine with the iterative solvers CH_Matrix_Classes::MinRes CH_Matrix_Classes::Psqmr. If there is no A at all (but maybe box constraints), the best method is likely CH_Matrix_Classes::PCG.
• QPIterativeKKTHAeqSolver : is dervied from QPIterativeKKTSolver and differs to QPIterativeKKTHASolver in that in the KKT-system also the inequality constraints of the A block are Schur complemented into the H block. Thus, in the presence of equality constraints the iterative solvers CH_Matrix_Classes::MinRes is needed, if there are inequality constraints in A only then CH_Matrix_Classes::PCG can also be used. The combination with MinRes seems to be a bit more stable and together with preconditioner 31 of QPKKTSubspaceHPrecond this is currently the recommended combination for the iterative case.

The cutting models are realized by two implemtented classes derived from QPModelBlock which brings together the abstract classes QPModelDataObject (interface for the cutting modles of ConicBundle) and QPModelBlockObject (interface for QPSolverBasicInterface and the QPKKTSolverObject)

• QPConeModelBlock : it allows to describe any of the cutting models employed by the classes NNCModel, SOCModel, PSCModel, BoxModel by tying together the following implementations of the abstract class InteriorPointBundleBlock NNCIPBundleBlock (building on NNCIPBlock for a nonnegative cone) SOCIPBundleBlock (building on SOCIPBlock for a second order cone) PSCIPBundleBlock (building on PSCIPBlock for a positive semidefnite cone) BoxIPBundleBlock (building also on NNCIPBlock for the bounds)
• QPSumModelBlock : it forms the sum of several QPModelBlock instances as required in SumModel