Internal QP Solver for unconstrained groundsets

Classes
class	ConicBundle::UQPSolver
	unconstrained QP solver combining the properties of a QPModelDataPointer and QPSolverObject More...
class	ConicBundle::UQPModelBlockObject
	abstract interface for model blocks in the unconstrained UQPSolver More...
class	ConicBundle::UQPModelBlock
	combines and provides basic functionalities of QPModelDataObject and UQPModelBlockObject, but is still abstract More...
class	ConicBundle::UQPSumModelBlock
	implements a (virtual) cutting model being built of a (possibly recursive) sum of UQPModelBlock cutting model instances for UQPSolver More...
class	ConicBundle::UQPConeModelBlock
	implements a UQPModelBlock for conic cutting models in UQPSolver More...

Detailed Description

If the groundset (see e.g. UnconstrainedGroundset) of the convex optimization problem is unconstrained or if it only involves box constraints (as a special case of an LPGroundset) towgether with a diagonal proximal term (eg BundleIdProx or BundleDiagonalTrustRegionProx) an unconstrained QP solver suffices 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 and managing core of the solver is UQPSolver. It 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 cutting models are realized by two implemtented classes derived from UQPModelBlock which brings together the abstract classes QPModelDataObject (interface for the cutting models of ConicBundle) and UQPModelBlockObject (interface for the interior point solver):

• UQPConeModelBlock : it allows to describe any of the cutting models employed by the classes NNCModel, SOCModel, PSCModel, BoxModel
• UQPSumModelBlock : it forms the sum of several UQPModelBlock instances as required in SumModel

The efficiency of the UQPSolver in comparison to the full QPSolver relies on first eliminating the unconstrained design variables (a kind of Schur complement step in the full KKT system of the saddle point prpboem) and solving the bundle subproblem in terms of the model variables only. Quite often the computation of the QP cost terms for this reduced problem is the most costly operation. How to do this efficiently depends mostly on the proximal term used. Therefore the routines for computing the reduced QP cost terms for the UQPSolver are implemented directly within each ProxObject by the routine BundleProxObject::compute_QP_costs(), which is called inside UQPSolver::QPsolve() for getting the quadratic cost terms.

When some of the convex functions are used with a FunctionTask in AdaptivePenaltyFunction, a change in the penalty term only affects the right hand side of the trace constraint in the models. It does not affect the unconstrained QP cost terms and if the cutting model is not changed otherwise they need not be recomputed. Thus, resolving for adpated penalty terms is particularly efficient and the BundleSolver then calls UQPSolver::resolve() instead of UQPSolver::QPsolve().

A major challenge is handling box constraints with an unconstrained solver, because the candidate may have to be pushed back into the feasible set thereby losing optimality with respect to the model representation. How to resolve this via potentially several repeated unconstrained solves with updated groundset aggregates in a Gauss-Seidl fashion is described by Helmberg and Kiwiel. It works best, if the optimal groundset aggregate pushing the candidate into the feasible set can be determined by explicit computations as in the case of a diagonal prox term (it also works for more general groundsets but then requires solving a separate QP over the groundset). If the model quality of the current model aggregate is poor for this corrected candidate, the BundleSolver may decide to recompute the subproblem with the corrected groundset aggregate. The latter only enters the cost terms of the QP. Doing the update of these costs efficiently is again important. This happens in BundleProxObject::update_QP_costs(), which is called by UQPSolver::QPupdate() which itself is called when the BundleSolver decides to recompute the bundel subproblem for the same cutting model with corrected groundset aggregate.

A feature that is particularly easy to handle in solving box constrained variants by the unconstrained approach is the fixing of some variables to the bounds. It simply means that in computing the unconstrained QP costs these variables may be considered to be constant values. So while the list of fixed values is passed through the interface of the UQPSolver it actually doesn't have to worry about it other than passing it on to the BundleProxObject which then takes care of this infomation in computing the QP costs.