## 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!