Gurobi "Objective Q not PSD " for Convex quadratic problem

Specific Domains Optimization (Mathematical)
1

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:

F=eigen(testM)
@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: https://github.com/jump-dev/Gurobi.jl/issues/338

2

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.

3

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?

4

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.

5

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.

6

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?