# 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:

``````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

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 Likes

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.

2 Likes

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`?