Model contains large quadratic objective coefficient range.
Hi,
I am trying to solve a QP problem. However, I get in my log file a warning that the model contains a large quadratic objective coefficient range. Consider reformulating model or setting NumericFocus parameter
to avoid numerical issues.
Due to the large range for the quadratic objective coefficient, the solving time is quite large. Is there a solution to fix this warning? Furthermore, I get a suboptimal solution (see log file beneath).
I tried already the following:  Scaling the inequality constraints by a factor 1e4 (so multiplying model.A and model.rhs with 1e4). If I do this, I get a optimal objective. However, the solution seems to change a tiny bit in comparison to the suboptimal solution, where I would expect a bigger difference. Furthermore, is it allowed to multiply your inequality constraint with a specific factor? The second thing, I tried is by using a NumericFocus = 1. The warning about numerical issues is then not visible anymore in the log file. The result does not change then either and the solving time remains about the same.
Does anyone have another solution which I could try or knows what is exactly wrong (the result seems to converge too quickly)?
Thanks in advance!
Gurobi Optimizer version 9.0.0 build v9.0.0rc2 (win64)
Optimize a model with 1800 rows, 900 columns and 293640 nonzeros
Model fingerprint: 0x5b816b45
Model has 405358 quadratic objective terms
Coefficient statistics:
Matrix range [2e09, 6e+01]
Objective range [8e04, 5e+03]
QObjective range [2e09, 1e+05]
Bounds range [0e+00, 0e+00]
RHS range [1e+01, 1e+01]
Warning: Model contains large quadratic objective coefficient range
Consider reformulating model or setting NumericFocus parameter
to avoid numerical issues.
Presolve removed 1428 rows and 0 columns
Presolve time: 0.16s
Presolved: 372 rows, 1272 columns, 146664 nonzeros
Presolved model has 405358 quadratic objective terms
Ordering time: 0.01s
Barrier statistics:
Free vars : 899
AA' NZ : 8.059e+05
Factor NZ : 8.084e+05 (roughly 8 MBytes of memory)
Factor Ops : 6.852e+08 (less than 1 second per iteration)
Threads : 4
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 1.82862120e+09 2.24144781e+06 1.04e+05 4.40e+02 1.00e+06 1s
1 9.47293849e+07 3.88370152e+06 5.43e+03 4.83e+01 5.93e+04 1s
2 1.58312380e+07 2.95939340e+06 9.01e+02 8.64e+00 1.21e+04 1s
3 3.88967159e+06 2.01547634e+06 2.20e+02 2.01e+00 3.57e+03 1s
4 9.73768926e+05 1.23614068e+06 5.23e+01 5.02e01 1.37e+03 1s
5 3.95343773e+05 6.89353016e+05 1.92e+01 1.77e01 6.07e+02 1s
6 1.66432690e+05 3.55566137e+05 6.17e+00 5.94e02 2.55e+02 1s
7 9.20578170e+04 2.09691804e+05 1.66e+00 1.54e02 1.05e+02 2s
8 6.74517981e+04 1.12550992e+05 4.13e05 7.08e09 2.08e+01 2s
9 7.48550002e+04 8.48427537e+04 2.33e06 1.69e10 4.60e+00 2s
10 7.70695104e+04 8.07656538e+04 2.76e07 2.10e11 1.70e+00 2s
11 7.80862121e+04 7.85630450e+04 1.51e08 2.89e11 2.20e01 2s
12 7.82261866e+04 7.83132205e+04 1.72e09 3.67e11 4.01e02 2s
13 7.82592114e+04 7.82633547e+04 1.42e09 2.00e11 1.91e03 2s
14 7.82620134e+04 7.82609388e+04 2.34e03 2.02e11 7.71e05 3s
15 7.82533352e+04 7.82609371e+04 2.81e03 1.92e11 7.58e05 3s
16 7.82516986e+04 7.82609287e+04 3.02e03 1.96e11 6.55e05 3s
17 7.82675915e+04 7.82609147e+04 4.04e03 1.75e11 4.54e05 3s
18 7.82876758e+04 7.82609153e+04 5.45e03 1.62e11 3.50e05 3s
19 7.82878447e+04 7.82609590e+04 1.09e02 1.82e11 2.95e05 3s
20 7.82818420e+04 7.82609597e+04 1.93e02 1.34e11 2.71e05 3s
21 7.82802284e+04 7.82611320e+04 1.90e02 1.80e11 2.55e05 3s
22 7.83425297e+04 7.82612689e+04 2.79e02 1.71e11 2.40e05 4s
23 7.84600816e+04 7.82614475e+04 5.72e02 1.93e11 2.37e05 4s
24 7.82014689e+04 7.82615088e+04 6.32e02 2.11e11 1.88e05 4s
25 7.81786827e+04 7.82640655e+04 6.51e02 2.20e11 1.43e05 4s
26 7.77791677e+04 7.82649782e+04 2.03e01 3.16e11 1.38e05 4s
27 7.81202228e+04 7.82650596e+04 2.48e01 3.34e11 1.38e05 4s
28 7.79205906e+04 7.82724055e+04 2.67e01 5.74e11 1.44e05 4s
29 7.89814984e+04 7.82824883e+04 2.40e01 5.71e11 2.49e04 4s
30 7.98835651e+04 7.82868436e+04 5.75e01 2.23e11 2.95e04 5s
31 7.99041124e+04 7.82837040e+04 5.42e01 3.50e11 2.22e04 5s
32 7.96828224e+04 7.82831925e+04 5.25e01 1.92e11 2.21e04 5s
33 7.92742409e+04 7.83089355e+04 5.00e01 3.73e11 1.99e04 5s
34 7.90700830e+04 7.83172952e+04 4.40e01 1.03e10 1.83e04 5s
35 7.92446939e+04 7.83689350e+04 3.90e01 9.11e11 3.79e05 5s
36 8.03006893e+04 7.83679067e+04 8.99e01 7.60e11 5.19e05 5s
37 8.02647319e+04 7.83818041e+04 8.60e01 1.15e10 7.54e05 5s
38 8.02057803e+04 7.83933746e+04 8.91e01 3.86e11 8.62e05 6s
39 8.08051444e+04 7.84078069e+04 8.60e01 3.38e11 7.04e05 6s
40 7.90421229e+04 7.84001782e+04 1.96e+00 1.39e10 1.59e04 6s
41 7.88354416e+04 7.84324308e+04 1.89e+00 1.50e10 1.42e04 6s
42 6.93112964e+04 7.84522870e+04 3.55e+00 1.31e10 5.87e04 6s
43 7.36234701e+04 7.84627270e+04 3.98e+00 1.78e10 5.31e04 6s
44 7.38552647e+04 7.84757577e+04 4.52e+00 2.06e10 4.91e04 6s
45 7.40079626e+04 7.85031759e+04 4.28e+00 8.87e11 1.28e03 7s
46 7.39126053e+04 7.84981948e+04 4.22e+00 6.97e11 1.24e03 7s
47 7.39760296e+04 7.85010903e+04 4.19e+00 2.07e11 1.23e03 7s
48 7.38244694e+04 7.85590213e+04 4.16e+00 3.65e11 3.43e03 7s
49 7.38287097e+04 7.85584892e+04 4.15e+00 2.05e11 3.43e03 7s
50 7.40238112e+04 7.85785264e+04 4.12e+00 3.55e11 4.43e03 7s
51 7.44612792e+04 7.85757060e+04 3.53e+00 4.52e11 7.89e03 7s
Barrier performed 51 iterations in 7.32 seconds
Suboptimal termination  objective 7.82592114e+04

You should really consider reformulating your model, as the reported ranges, especially for the quadratic,
> Matrix range [2e09, 6e+01]
> Objective range [8e04, 5e+03]
> QObjective range [2e09, 1e+05]borderline with the roundoff error in doubleprecision arithmetic (think on any "standard" PC if you try this logical compassion, (1 + 1e16 == 1), you will get TRUE). This subject is covered in details in our online doc,
https://www.gurobi.com/documentation/8.1/refman/numerics_gurobi_guidelines.html
and as a first thing one can try, even a simple rescaling of the variables often helps. For instance, to avoid large quadratic entries on the (I,i) diagonal you can change the meaning of your variable where the respective x_i would count things not in units, but in thousand of units. For more details, please read through the above manual online.
Hope this helps,

Hello Yuriry,
Does the QObjective range specify the range of the elements in the Hessian? Is is somewhat the same as the condition number of the Hessian?
The righthand side of the inequality constraint is a vector which contains the values 0 and 10, which represents the bounds of the values the decision variables can take. So, I think the right units are chosen to express the variables and constraints.
Furthermore, I don't really understand the proposed possible solution: '' to avoid large quadratic entries on the (I,i) diagonal you can change the meaning of your variable where the respective x_i would count things not in units, but in thousand of units''.
I have read the manual, but I cannot really find this back. What do you mean with (l,i) diagonal and x_i for example?
Regards

QObjective range specifies the range of the matrix in the quadratic objective, and you can think of it as the Hessian of the objective as well. The right hand side of the constraints is not necessarily the best reference point  it is much more important to keep the ranges of 'matrices' (objective and constraint coefficients) in check.
"To avoid large quadratic entries on the (i,i) diagonal you can change the meaning of your variable where the respective x_i would count things not in units, but in thousand of units''.
Suppose your objective has a term
a(i,i) * x(i)^2
where a(i,i) is very small, say on the order of 10^(9). Then by changing the respective x(i) to represent 10^(4)*x(i) units, say rewriting the model in terms of y(i) = 10^(4) x(i), you can replace the
a(i,i) * x(i)^2
term by
(a(i,i) * 10^8) * y(i)^2
effectively scaling the diagonal entry of your quadratic objective matrix by 10^8 (so the new coefficient will be on the order of 10^(1)).
Hope this helps.

Hi,
Thanks for the clarification.
I forgot to give you more information.
Part 1:
The optimization problem I am solving could be seen below:
with zik = H*xik, uik the predicted inputs, xik the predicted states
In this optimal control problem Q and R are both symmetric positive definite matrices, with Q a diagonal matrix (all diagonal entries have the value 100) and R a diagonal matrix (all diagonal entries have the value 0.1). Furthermore, the mean of the vector of z_r is around 5 and the mean of the vector u_r is around 0.1. 
Part 2:
In more detail, after some substitution the quadritic part of the optimization problem looks like:
with Z a banded nullspace matrix, Omega a diagonal matrix with transpose(H)*Q*H and R on the diagonal entries.
The condition number of Z is 1e7. Therefore, I think the problem lays in the Z matrix.
Is it for example possible to use your example of rescaling for the term transpose(Z)*Omega*Z? If yes, what should be done with the linear objective term which is not displayed above? Or is there in this case a better possible solution?
Regards

Thanks for providing more details, and yes, I would try the rescaling that was described earlier to see what happens. For the linear term, I would apply the same change of variable and not worry (at least at first) about the effect on the linear term; usually the quadratic is the one causing numerical problems. If you see that the linear part becomes problematic, you can consider using a lessaggressive scaling as well.
More information can be found in our numerical guidelines online.
Cheers,

Hi,
I have rescaled the model, but the numerical issues are still present.
Do you have any other options I could try?
What did you by the way mean with: borderline with the roundoff error in doubleprecision arithmetic (think on any "standard" PC if you try this logical compassion, (1 + 1e16 == 1), you will get TRUE)?
That Matlab makes roundoff errors due to floating point errors?
And do you have maybe a possible explanation why the numerical issues for Gurobi occur and not for Matlabs quadprog function (or at least for very large matrices)? Both are making use of the barrier/interiorpoint method.
Kind regards,

This subject is covered in details in our online doc,
https://www.gurobi.com/documentation/8.1/refman/numerics_gurobi_guidelines.html
Regarding your other question
> .. floating point errors?
yes, flowing point arithmetic errors will be persistent on any platform, and not limited to Matlab.
I cannot tell what is going on in Matlab quadprog, but it is possible that some issues are circumvented there, and it is also possible that these things are simply not reported and ignored. I would certainly doblecheck the answers as part of postprocessing the solution, to make sure the solution is feasible etc.
Hope this helps.

Hi,
Thanks for your response. Still one general question about Gurobi (you maybe know from experience).
I have some general questions about the barrier algoritm that Gurobi uses to solve a QP.
For which type of problems does the algorithm work the best? Largescale systems or smallscale systems?
Do dense matrices work the best for the barrier algorithm or sparse matrices? What are the causes of that? Or works a combination better?
For example small, the fastest for small, dense problems and large, sparse problems.
Does the algorithm need a lot of iterations to converge or less iterations, but each iteration is more expensive, in general?
I found a Powerpoint about Gurobi and this was the only thing I found of the above subject, but I don't exactly know what they mean with:
Dozens of expensive iterations: Why many iterations and expensive at both time
Much denser matrices: Why denser matrices? I thought Gurobi could handle sparse matrices better?
Lots of opportunities to exploit parallelism: What is parallelism?
Please sign in to leave a comment.
Comments
9 comments