Gurobi "Objective Q not PSD " for Convex quadratic problem

I got this error when using Gurobi 9.0.1 in Julia 1.3.1: Gurobi.GurobiError(10020, "Objective Q not PSD (diagonal adjustment of 5.8e-01 would be required)")
However, I’m sure that my problem is convex, as you can see from the code below:

@show minimum(F.values)

which gives a positive minimum eigenvalue of my 50 by 50 matrix testM, minimum(F.values) = 0.01262644537861781.

Now the following code produces the “not PSD” error:

psdm = Model(solver=GurobiSolver(OutputFlag=0))
@variable(psdm, t[1:50] )
@objective(psdm, Min, dot(t,testM*t))
@constraint(psdm, dot(t,t) <= 1)
status = solve(psdm)

As you can see, the problem is a convex quadratic problem. Why is Gurobi saying it is not PSD?

Thank you!

The matrix testM is given below:

50×50 Array{Float64,2}:
  2.59448e11  -8.8763e11   -5.8729e11   …   3.03758e11  -5.82268e11
 -8.8763e11    3.03678e12   2.00926e12     -1.03922e12   1.99207e12
 -5.8729e11    2.00926e12   1.3294e12      -6.87592e11   1.31803e12
 -1.55914e12   5.33416e12   3.52929e12     -1.82542e12   3.4991e12 
 -6.05552e10   2.07173e11   1.37074e11     -7.08972e10   1.35901e11
 -1.8582e12    6.35734e12   4.20627e12  …  -2.17556e12   4.17029e12
  2.74024e11  -9.37498e11  -6.20285e11      3.20823e11  -6.14981e11
  5.94194e11  -2.03287e12  -1.34503e12      6.95675e11  -1.33353e12
 -1.58152e12   5.41076e12   3.57997e12     -1.85163e12   3.54935e12
  9.69765e10  -3.31779e11  -2.19518e11      1.13539e11  -2.1764e11 
  9.56474e10  -3.27232e11  -2.16509e11  …   1.11983e11  -2.14658e11
  5.00434e11  -1.7121e12   -1.13279e12      5.85901e11  -1.1231e12 
 -1.57677e10   5.39448e10   3.5692e10      -1.84606e10   3.53867e10
  ⋮                                     ⋱                          
  2.19594e12  -7.51281e12  -4.97077e12      2.57097e12  -4.92825e12
  8.05208e11  -2.7548e12   -1.82268e12      9.42727e11  -1.8071e12 
  2.92622e12  -1.00113e13  -6.62384e12  …   3.42598e12  -6.56719e12
  1.05624e12  -3.61362e12  -2.39091e12      1.23663e12  -2.37047e12
  1.67725e12  -5.73824e12  -3.79664e12      1.9637e12   -3.76417e12
 -7.68743e11   2.63004e12   1.74014e12     -9.00034e11   1.72526e12
  8.41691e11  -2.87962e12  -1.90527e12      9.85441e11  -1.88897e12
 -2.26199e12   7.73879e12   5.12028e12  …  -2.64831e12   5.07649e12
 -9.90114e11   3.38741e12   2.24124e12     -1.15921e12   2.22207e12
 -6.62424e11   2.2663e12    1.49947e12     -7.75557e11   1.48665e12
  3.03758e11  -1.03922e12  -6.87592e11      3.55636e11  -6.81711e11
 -5.82268e11   1.99207e12   1.31803e12     -6.81711e11   1.30676e12

I also post this issue here:

Your matrix M contains very big coefficients. It’s asking for a diagonal adjustment of 0.58, when the terms are 10^11.

Take a read of the following and try rescaling your problem to smaller coefficient values.


Thank you! The article is very helpful. Is there a way to scale the coefficients if the range of the values in the matrix are large? For example, the maximum of the values in the matrix M is 10^10 while the minimum is 10^-7.

The article handles this issue by rescaling some variables. But this trick only works for the case where M is in some linear constraints Mx <= b where the variables are separable. If we have min x'Mx, there will be many cross terms of variables. For example, we might have the term 10^10*x_1*x_2 + 10^(-7)*(x_1)^2 +... , then we have to scale down x_1 and scale up x_2 to keep the coefficients at similar magnitude. However, the issue is there are so many such terms, especially when we have a large number of variables. It’s almost impossible to do it as the only way I can think of is to look at the terms one by one and see which variables are involved. Is there a more efficient way to handle this issue?

The point really is that if you have a term 10^10 * x1 * x2 and a term 10^-7 * x1^2, then the second term can effectively be ignored and removed.

For perspective, the difference between these two terms is like measuring the distance to the sun in microns…

A rule of thumb I use is to put all your variables into units where you have ~5 significant figures of accuracy. For example, we measure the distance to the sun in million kilometers, not microns.

1 Like

If you believe your matrix is PSD, you should be able to find a decomposition of the form Q = A^TA. If that’s the case, add extra variables equal to y = Ax and minimize y^Ty = (Ax)^T(Ax) = x^TQx. In this case Gurobi cannot complain that the objective is not PSD.

You’ll still be affected by numerical issues if you have variables and coefficients on wildly different scales.


Thank you both for the nice solutions! To have similar units and avoid the numerical issues, is it a good idea to let B = M/maximum(abs.(M)), then set all small elements (e.g. elements whose absolute value <10^-8) of B to 0, and min x'Bx?