Non-convex QPs and Marginals

The Cplex global QP solver has some problems providing marginals (duals and reduced costs) for a non-convex QP. Here is a small model taken from (1):

To solve this problem to optimality in GAMS we add ‘option optcr=0’ and we provide a Cplex option ‘OptimalityTarget = 3’.

Solution

The solution looks like:

LOWER          LEVEL          UPPER        ---- EQU Obj                 .              .              .                  ---- EQU Con               -INF           39.0000        40.0000                      Obj  objective function   Con  constraint function ---- VAR x            LOWER          LEVEL          UPPER         i1          .             1.0000         1.0000            i2          .             1.0000         1.0000            i3          .              .             1.0000             i4          .             1.0000         1.0000             i5          .              .             1.0000                                        LOWER          LEVEL          UPPER         ---- VAR f                 -INF          -17.0000        +INF

The marginals are missing. Indeed the log contains message:

*** No duals possible for models with quadratic objective when solved globally.

 

Workarounds

The simplest way to get the marginals of this problem is to use a global solver that provides duals:

• Baron
• GloMiQO

These solvers do not provide (correct) duals:

• Cplex
• Couenne
• LindoGlobal (strangely LindoGlobal provides some duals correctly, but others are incorrect).

One way to get marginals with a global solver that does not provide them is resolving the problem with a local solver. As in:

For this model it takes Cplex 28 iterations to find the global solution, and then Conopt needs 4 iterations to recover the duals. The results look like:

LOWER          LEVEL          UPPER         MARGINAL ---- EQU Obj                 .              .              .             1.0000      ---- EQU Con               -INF           39.0000        40.0000          .            Obj  objective function   Con  constraint function ---- VAR x            LOWER          LEVEL          UPPER         MARGINAL i1          .             1.0000         1.0000       -58.0000      i2          .             1.0000         1.0000       -56.0000      i3          .              .             1.0000        45.0000      i4          .             1.0000         1.0000       -53.0000      i5          .              .             1.0000        47.5000                                 LOWER          LEVEL          UPPER         MARGINAL ---- VAR f                 -INF          -17.0000        +INF             .

An alternative is to solve the non-convex QP as a MIP using a model with KKT conditions and a special objective (see here).

References

(1)  Floudas e.a., Handbook of Test Problems in Local and Global Optimization, Kluwer, 1999.