Diagnosing QP Infeasibility

> Continuous Optimization > Solving Problems with a Quadratic Objective (QP) > Diagnosing QP Infeasibility

Diagnosing QP Infeasibility

Diagnosis of an infeasible QP problem is best done by relaxing it to its associated LP problem, that is, where the Q matrix has been set to 0.

To change the Problem Type:

in the Interactive Optimizer, use the command change problem lp;
from the Callable Library, use the routine CPXchgprobtype.

Since IloCplex handles Problem Types transparently, the way to diagnose an infeasible model is slightly different. Since infeasibility does not depend on the objective function, you start by removing the objective extractable from the extracted model. This way, the model seen by the cplex object is an LP with a 0 objective and the LP IIS finder can be applied. To get the original model back, simply add the objective back to the model.

You can then solve the relaxed linear version by means of the ILOG CPLEX simplex optimizer. Then you can apply the ILOG CPLEX infeasibility finder to that relaxed solution, with its associated, original QP information, to help you diagnose the source of the infeasibility. (Diagnosing LP Infeasibility explains how to use the ILOG CPLEX infeasibility finder following a simplex optimizer.)

Note that it is possible for the outcome of that analysis to be a confirmation that your model (viewed as an LP) is feasible after all. This is typically a symptom that your QP model is numerically unstable, or ill-conditioned. Unlike the simplex optimizers for LP, the QP optimizers are primal-dual in nature, and one result of that is the scaling of the objective function interacts directly with the scaling of the constraints.

Just as our recommendation regarding numerical difficulties on LP models (see Numerical Difficulties) is for coefficients in the constraint matrix not to vary by more than about six orders of magnitude, for QP this recommendation expands to include the quadratic elements of the objective function coefficients as well. Fortunately, in most instances it is straightforward to scale your objective function, by multiplying or dividing all the coefficients (linear and quadratic) by a constant factor, which changes the unit of measurement for the objective but does not alter the meaning of the variables or the sense of the problem as a whole. If your objective function itself contains a wide variation of coefficient magnitudes, you may also want to consider scaling the individual columns to achieve a closer range.

PREVIOUS NEXT