Sunday, July 21, 2013

QP is convex or not?

I have a QP problem that is rejected (not convex) or solved depending on the solver or method:

Solver Objective
Gurobi 1.01022764e+02 (23 iterations, 0.16 seconds)
Cplex *** CPLEX Error  5002: Q in %s is not positive semi-definite.
MOSEK (QP) Return code - 1295 [MSK_RES_ERR_OBJ_Q_NOT_PSD]: The quadratic coefficient matrix in the objective is not PSD.
MOSEK (NLP) 1.0102276353e+002 (24 iterations, 0.30 seconds)
XPRESS 1.0102297e+002 (12 iterations, 1 second)
KNITRO 1.01022803552155e+002 (21 iterations, 0.5 seconds)
IPOPT (MUMPS) Out of memory in MUMPS.
IPOPT (MA27) 1.0102276352077803e+002 (40 iterations, 0.7 seconds)

Try this to explain in a coherent fashion to a client…

The IPOPT issues may be unrelated to the convexity issue. Replacing the linear solver MUMPS by Harwell’s MA27 will often speed things up but from this we also see a more reliable behavior.

More background on this behavior: the Q matrix is diagonal with one negative element, but that variable is constraint to be zero. The left model in the table below illustrates this. The right model is the same, but now the variable is fixed to zero. 

GAMS model

variables z,x1,x2;
equations obj,e;

obj.. z =e= sqr(x1-1) - sqr(x2-2);
e..   x2 =e= 0;

model m/all/;
solve m minimizing z using qcp;

variables z,x1,x2;
equations obj;

obj.. z =e= sqr(x1-1) - sqr(x2-2);
x2.fx=0;

model m/all/;
solve m minimizing z using qcp;

Cplex *** CPLEX Error  5002: Q in %s is not positive semi-definite. *** CPLEX Error  5002: Q in %s is not positive semi-definite.
Gurobi OK *** Objective Q not PSD (negative diagonal entry)
Xpress OK ?899 Warning: The quadratic objective is not convex
MOSEK

Return code - 1295 [MSK_RES_ERR_OBJ_Q_NOT_PSD]: The quadratic coefficient matrix in the objective is not PSD.

Return code - 1295 [MSK_RES_ERR_OBJ_Q_NOT_PSD]: The quadratic coefficient matrix in the objective is not PSD.

Cplex LP file

\ENCODING=ISO-8859-1
\Problem name: gamsmodel

Minimize
_obj: z - 2 x1 + 4 x2 + [ 2 x1 ^2 - 2 x2 ^2 ] / 2
Subject To
obj#0: z  = -3
_e#1:  x2  = 0
Bounds
      z Free
      x1 Free
      x2 Free
End

\ENCODING=ISO-8859-1
\Problem name: gamsmodel

Minimize
_obj: z - 2 x1 + 4 x2 + [ 2 x1 ^2 - 2 x2 ^2 ] / 2
Subject To
obj: z  = -3
Bounds
      z Free
      x1 Free
      x2 = 0
End

Gurobi LP file

Minimize
  - 2 x1 + 4 x2 - 3 Constant + [ 2 x1 ^ 2 - 2 x2 ^ 2 ] / 2
Subject To
e: x2 = 0
Bounds
x1 free
x2 free
Constant = 1
End

Minimize
  - 2 x1 + 4 x2 - 3 Constant + [ 2 x1 ^ 2 - 2 x2 ^ 2 ] / 2
Subject To
Bounds
x1 free
x2 = 0
Constant = 1
End

The LP files are reproduced here to show what Gurobi and Cplex think they are solving (these files were generated with a solver option). I am not sure why some solvers accept the version with an explicit equation x2=0 while reject the version with x2=0 as bounds. It is all a mystery to me.

The client solved this model as an NLP using MINOS. It is interesting to see how many issues we face just by solving it as a QP!