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; obj.. z =e= sqr(x1-1) - sqr(x2-2); model m/all/; | variables z,x1,x2; obj.. z =e= sqr(x1-1) - sqr(x2-2); model m/all/; |
| 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 Minimize | \ENCODING=ISO-8859-1 Minimize |
| Gurobi LP file | Minimize | Minimize |
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!
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.
ReplyDeleteFor 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.
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.
DeleteIt 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).
DeleteMOSEK will require that the original problem before presolve is convex. Otherwise for instance the postsolve may go wrong.
DeleteI would eliminate the nonconvex variable form the formulation.