Objective Q not PSD (diagonal adjustment would be required)

[Hasan]

Hi,

I have a MIQP with the following objective function

Obj_quad = LinExpr()
    for i in I:
        for k in J:
            Obj_quad += (x[i, k] - quicksum(Beta[j, k] * x[i, j] for j in G.neighbors(k))) * (
            x[i, k] - quicksum(Beta[j, k] * x[i, j] for j in G.neighbors(k)))


where x's are parameters (input) and beta's are decision variables. All my constraints are linear. 

I can run this model for small instances with no issues. However, when I increase the size of my instances, I get this error "Objective Q not PSD (diagonal adjustment would be required)".

I believe my objective function is quadratic and convex. In addition, I do not have any quadratic constraints in my model. Further, my model has a feasible solution. Can anyone give shed light on why I get this error?

Thank you!

[Daniel Espinoza]

Hi Hasan,

I can only guess that the Q matrix may be borderline non PSD, have you tried to compute yourself the eigenvalues for it? you could try 

https://docs.scipy.org/doc/numpy/reference/generated/numpy.linalg.eig.html

Have you tried running your model with `Presolve=0`? Let me know if that makes the problem go away.

Best,

Daniel

[Hasan]

Thanks for your comment, Daniel.
I set m.params.Presolve=0 . It still gives the error "Objective Q not PSD (diagonal adjustment of 7.2e+05 would be required)".
 
I'll compute the eigenvalues myself to see if there exists any anomalies. It is somewhat confusing, however, what is happening because I can run my model for all small and medium range instance, but for large scale instances I get this error. Maybe I need to rescale my parameters.

[Hasan]

Thanks, Daniel for your comment. I shall add that I get this error when my graph is dense in graphs with large number of nodes. I was listening to this Gurobi seminar at http://www.gurobi.com/resources/seminars-and-videos/gurobi-quadratic-constraints-webinar and in minute 22 Dr. Rothberg discusses the numerical difficulties of Gurobi to handle MIQCP. In this case, would it be possible that it is a numerical issue? My objective function is evidently convex. Thank you!    

On Wednesday, April 18, 2018 at 3:02:24 AM UTC-7, Daniel Espinoza wrote:

[Daniel Espinoza]

Hi Hasan,

Such a large adjustment seem to be too big (for it to be a numerical issue), and since you said that smaller problems are solved up to a point and then you get the non-PSD, this sounds a bit strange. Maybe you could share two models that can be solved and two where it can not so that I can take a look? If so, write to me to espinoza at gurobi dot com

Best,

Daniel

[Hasan]

Thanks Daniel. I figured it out. It seems that when my graph is dense and large, some of my parameters become too big, in the order of billion, while others are too small, say 0.01. I think that is the root of the problem. Thanks for your comment!  

[Daniel Espinoza]

Glad to hear that,

Best,

Daniel