Originally posted by: chintasunny

We recently upgraded our application to CPLEX 12.4  from CPLEX 12.1; We noticed that some instances are failing due to the error "CPLEX Error 5002: Q in objective is not positive semi-definite." However, these instances were successfully optimized in CPLEX 12.1. We also noticed that failures are occurring from CPLEX 12.3 and above. From the release notes, we further observed that some enhancements were made around QP semi-definite side. Our application uses MIQP model. What could be reasons for this failure and the ways to resolve the same?

Additionally we also tried to run diagnostics using qpindef.c/qpdiag.c; Both of them did not yield any positive results.

We would like to understand reasons for difference in behavior across the verisions? Also is there any quick fix like parameter tuning, etc which can be used as a workaround?

Ps: We also raised a ticket with CPLEX on the same. However, no luck so far!

Thanks in advance

Sunil

Have you verified that the Q matrices really are all p.s.d.? Is it possible that either (a) some are not p.s.d. but earlier versions of CPLEX did not detect this or (b) they are all p.s.d. but some are ill-conditioned, and on the ill-conditioned ones CPLEX has changed its tune?

Paul

Originally posted by: chintasunny

Thanks for the response Paul. Theoretically, our formulation is PSD. However, some ill conditioned data could trigger this issue which we have to analyze further. We are in a catch-22 situation as something that worked previously is failing after migrating to a newer cplex version. Unless we give a strong reasoning, client will not accept and he attributes it to CPLEX migration. Assume that this is not a bug and there is a valid reason for this behavior, we still have an issue as we have to enhance our model to fix these ill-data conditions :)

Sunil

If Q is ill-conditioned, one possible culprit might be poor scaling (mix of large and small values). Changing units of measure for some of the underlying variables might mitigate the ill-conditioning in a relatively painless way.

Another possibility is to perturb Q by adding a small positive constant to all diagonal entries, choosing the constant just large enough to make Q psd. With a bit of luck, the new "optimal solution" might actually be close enough to the true optimum to satisfy the client.

Paul

Originally posted by: chintasunny

Thanks Paul. Using the perturbation constant of 1e-8 solved our issue. I have the following follow-up queries:

• Decreasing perturbation constant is resolving the issue while increasing it is behaving in the opposite way; For instance, 1e-08 or 1e-20 or 1e-20... resolved the issue while 1e-7 was still throwing matrix as non PSD. My understanding is that if X perturbation constant resolves issue, then any number >X should also resolve. Is this not the case? (or) It has to do with signs of coefficients in Q matrix?
• If we have to embed this perturbation into our code, is there any parameter through which we can achieve it? (or) do we have to explicitly modify diagonal coefficients of our model?
• Scaling model or modifying unit of measure is an alternative; but is bit costly for us. I found another thread which talks about heuristically perturbing with different constants until Q becomes PSD. For the heuristic approach we need to define a range of perturbation constants. I am assuming one has to perform experimentation and decide that range. I am curious to understand if there any other better alternative to the heuristic approach?

 Thanks

Sunil

First question: I agree that if perturbation by X makes Q psd, perturbation by X' > X should (must!) also make it psd. So what you are observing suggests either something odd in the way CPLEX determines whether Q is psd, or possibly something odd about presolve reductions (?), which might change due to the perturbation.

Second question: I don't have much experience with QPs in CPLEX, but I suspect that there is no parameter to do this (or anything equivalent) for you. You might try turning on the numerical emphasis parameter. I don't know if that affects preprocessing, but if so, it might eliminate the need for the perturbation.

Third question: Beats me. If you have the Q matrix explicitly in memory (as a matrix), you might try computing its minimum (most negative) eigenvalue. Using the absolute value of that eigenvalue (or maybe the absolute value plus a tiny bit more) all along the diagonal should do the trick. If Q is very large, though, you may not want to pay the computational cost of computing the eigenvalues.

Paul

Does it work any better if you disable presolve?

Originally posted by: chintasunny

We tried with disabling presolve also; That also has not resolved the issue

Could you share a model (a SAV file) that was accepted in 12.1 but is rejected as non-PSD in 12.4?

If not in public, then you could send it directly to daniel(dot)junglas(at)de(dot)ibm(dot)com.

Originally posted by: chintasunny

Thanks Daniel. I had sent the .lp and .sav files to your mail id

Regards

Sunil

Originally posted by: Christian Bliek

Hi Sunil,

we made a change in the tolerances based on which we reject non-psd matrices. We found that if we were too lenient wrt this our qp simplex solver could run into numerical difficulties. So now we use stricter tolerance on all solves that involve the qp simplex solver; qp simplex, miqp and also barrier with crossover. However, we kept the old tolerance for the barrier solver as it can deal with it better than the simplex solver.

Christian.