QCQP and SOCP Methods

Continuous QCQP and SOCP problems are always solved by the Xpress Newton–barrier solver. For QCQP, SOCP and QP problems, there is no solution purification method applied after the barrier (such as the crossover for linear problems). This means that solutions tend to contain more active variables than basic solutions, and fewer variables will be at or close to one of their bounds.

When solving a linearly constrained quadratic program (QP) from scratch, the Newton barrier method is usually the algorithm of choice. In general, the quadratic simplex methods are better if a solution with a low number of active variables is required, or when a good starting basis is available (e.g., when reoptimizing).

Convexity Checking

The Optimizer requires that the quadratic coefficient matrix in each constraint or in the objective function is either positive semi–definite or negative semi–definite, depending on the sense of for constraints or the direction of optimization for the objective. The only exception is when a quadratic constraint describes a second order cone. Quadratic constraints and a quadratic objective is therefore automatically checked for convexity. Note that this convexity checker will reject any problem where this requirement is violated by more than a small tolerance.

Each constraint is checked individually for convexity. In certain cases it is possible that the problem itself is convex, but the representation of it is not. A simple example would be

The optimizer will deny solving this problem if the automatic convexity check is on, although the problem is clearly convex. The reason is that convexity of QCQPs is checked before any presolve takes place. To understand why, consider the following example:

This problem is clearly feasible, and an optimal solution is (x,y)=(1,2). However, when presolving the problem, it will be found infeasible, since assuming that the quadratic part of the first constraint is convex the constraint cannot be satisfied (remember that if a constraint is convex, then removing the quadratic part is always a relaxation). Thus since presolve makes use of the assumption that the problem is convex, convexity must be checked before presolve.

Note that for quadratic programming (QP) and mixed integer quadratic programs (MIQP) where the quadratic expressions appear only in the objective, the convexity check takes place after presolve, making it possible to accept matrices that are not PSD, but define a convex function over the feasible region (note that this is only a chance).

It is possible to turn the automatic convexity check off. By doing so, one may save time when solving problems that are known to be convex, or one might even want to experiment trying to solve non–convex problems. For a non–convex problem, any of the following might happen:

1. the algorithm converges to a local optimum which it declares optimal (and which might or might not be the actual optimum);
2. the algorithm doesn't converge and stops after reaching the iteration limit;
3. the algorithm cannot make sufficient improvement and stops;
4. the algorithm stops because it cannot solve a subproblem (in this case it will declare the matrix non semidefinite);
5. presolve declares a feasible problem infeasible;
6. presolve eliminates variables that otherwise play an important role, thus significantly change the model;
7. different solutions (even feasibility/infeasibility) are generated to the same problem, only by slightly changing its formulation.

There is no guarantee on which of the cases above will occur, and as mentioned before, the behavior/outcome might be formulation dependent. One should take extreme care when interpreting the solution information returned for a non–convex problem.

Quadratically Constrained and Second Order Cone Problems

Quadratically constrained and second order cone problems are solved by the barrier algorithm.

Mixed integer quadratically constrained (MIQCQP) and mixed integer second order problems (MISOCP) are solved using traditional branch and bound using the barrier to solve the node problems, or by means of outer approximation, as defined by control MIQCPALG.

It is sometimes beneficial to solve the root node of an MIQCQP or MISOCP by the barrier, even if outer approximation is used later; controlled by the QCROOTALG control. The number of cut rounds on the root for outer approximation is defined by QCCUTS.