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!

4 comments:

  1. To the best of my knowledge all optimizers verify convexity by computing a Cholesky factorization of the Q matrix. We know if the matrix is PSD all pivots will be nonnegative. However, due to rounding errors some pivots may be negative. Therefore, small negative pivots will be truncated to zero. Each optimizer uses their own tolerance and that is the explenation for the difference. Other factors like ordering and actual linear algebra will also affect the conclusion.

    For which values of eps>0 do you think

    [1 1 ]
    [1 1-eps]

    is positive definite? This is the issue we have to deal with. What is the right eps?

    The conclusion is clear in my opinion. Checking convexity by computing a Cholesky is not very robust for general semi-definite Q. Your results prove this.

    The conclusion also provide the solution. Indeed if Q had been a diagonal matrix then it would have been trivial to verify convexity. Now all convex QPs can be reformulated to have diagonal
    Q.

    My exprience is that the user almost always knows a factorization of Q i.e. a H so Q=HH'
    because that is the reason they know Q is PSD.
    Using H they can easily reformulate the QP to have a diagonal Q.

    In many cases this reformulation also is advantageous for efficiency reasons. See
    http://docs.mosek.com/whitepapers/qmodel.pdf for details.



    ReplyDelete
    Replies
    1. Indeed, I keep having to change the code in my quadratic form analyzer in CVX because of this problem. I use Cholesky as a first test, but ultimately resort to an eigenvalue decomposition if necessary. Of course, that's not necessarily going to be practical in many contexts, because using the eigenvalue decomposition will destroy sparsity (I need the eigenvectors to transform the problem properly). I'm still not satisfied with what I have now, and plan to improve how I compute the Cholesky so that it can handle a wider variety of semidefinite Q matrices while preserving sparsity.

      Delete
    2. It is a kind of a matrix balancing problem to reconcile data before use in the real model (which is a large and difficult NLP). Don't have a clue about the factors. However I am pretty sure the Q matrix is diagonal. It has a negative entry on one of the variables but that variable is constraint to be zero (the presolver can take it out).

      Delete
    3. MOSEK will require that the original problem before presolve is convex. Otherwise for instance the postsolve may go wrong.

      I would eliminate the nonconvex variable form the formulation.


      Delete