Monday, July 18, 2016

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):

image

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:

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:

image

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.