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 sub-optimal 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 sub-optimal 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 [2e-09, 6e+01]
Objective range [8e-04, 5e+03]
QObjective range [2e-09, 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.02e-01 1.37e+03 1s
5 -3.95343773e+05 -6.89353016e+05 1.92e+01 1.77e-01 6.07e+02 1s
6 -1.66432690e+05 -3.55566137e+05 6.17e+00 5.94e-02 2.55e+02 1s
7 -9.20578170e+04 -2.09691804e+05 1.66e+00 1.54e-02 1.05e+02 2s
8 -6.74517981e+04 -1.12550992e+05 4.13e-05 7.08e-09 2.08e+01 2s
9 -7.48550002e+04 -8.48427537e+04 2.33e-06 1.69e-10 4.60e+00 2s
10 -7.70695104e+04 -8.07656538e+04 2.76e-07 2.10e-11 1.70e+00 2s
11 -7.80862121e+04 -7.85630450e+04 1.51e-08 2.89e-11 2.20e-01 2s
12 -7.82261866e+04 -7.83132205e+04 1.72e-09 3.67e-11 4.01e-02 2s
13 -7.82592114e+04 -7.82633547e+04 1.42e-09 2.00e-11 1.91e-03 2s
14 -7.82620134e+04 -7.82609388e+04 2.34e-03 2.02e-11 7.71e-05 3s
15 -7.82533352e+04 -7.82609371e+04 2.81e-03 1.92e-11 7.58e-05 3s
16 -7.82516986e+04 -7.82609287e+04 3.02e-03 1.96e-11 6.55e-05 3s
17 -7.82675915e+04 -7.82609147e+04 4.04e-03 1.75e-11 4.54e-05 3s
18 -7.82876758e+04 -7.82609153e+04 5.45e-03 1.62e-11 3.50e-05 3s
19 -7.82878447e+04 -7.82609590e+04 1.09e-02 1.82e-11 2.95e-05 3s
20 -7.82818420e+04 -7.82609597e+04 1.93e-02 1.34e-11 2.71e-05 3s
21 -7.82802284e+04 -7.82611320e+04 1.90e-02 1.80e-11 2.55e-05 3s
22 -7.83425297e+04 -7.82612689e+04 2.79e-02 1.71e-11 2.40e-05 4s
23 -7.84600816e+04 -7.82614475e+04 5.72e-02 1.93e-11 2.37e-05 4s
24 -7.82014689e+04 -7.82615088e+04 6.32e-02 2.11e-11 1.88e-05 4s
25 -7.81786827e+04 -7.82640655e+04 6.51e-02 2.20e-11 1.43e-05 4s
26 -7.77791677e+04 -7.82649782e+04 2.03e-01 3.16e-11 1.38e-05 4s
27 -7.81202228e+04 -7.82650596e+04 2.48e-01 3.34e-11 1.38e-05 4s
28 -7.79205906e+04 -7.82724055e+04 2.67e-01 5.74e-11 1.44e-05 4s
29 -7.89814984e+04 -7.82824883e+04 2.40e-01 5.71e-11 2.49e-04 4s
30 -7.98835651e+04 -7.82868436e+04 5.75e-01 2.23e-11 2.95e-04 5s
31 -7.99041124e+04 -7.82837040e+04 5.42e-01 3.50e-11 2.22e-04 5s
32 -7.96828224e+04 -7.82831925e+04 5.25e-01 1.92e-11 2.21e-04 5s
33 -7.92742409e+04 -7.83089355e+04 5.00e-01 3.73e-11 1.99e-04 5s
34 -7.90700830e+04 -7.83172952e+04 4.40e-01 1.03e-10 1.83e-04 5s
35 -7.92446939e+04 -7.83689350e+04 3.90e-01 9.11e-11 3.79e-05 5s
36 -8.03006893e+04 -7.83679067e+04 8.99e-01 7.60e-11 5.19e-05 5s
37 -8.02647319e+04 -7.83818041e+04 8.60e-01 1.15e-10 7.54e-05 5s
38 -8.02057803e+04 -7.83933746e+04 8.91e-01 3.86e-11 8.62e-05 6s
39 -8.08051444e+04 -7.84078069e+04 8.60e-01 3.38e-11 7.04e-05 6s
40 -7.90421229e+04 -7.84001782e+04 1.96e+00 1.39e-10 1.59e-04 6s
41 -7.88354416e+04 -7.84324308e+04 1.89e+00 1.50e-10 1.42e-04 6s
42 -6.93112964e+04 -7.84522870e+04 3.55e+00 1.31e-10 5.87e-04 6s
43 -7.36234701e+04 -7.84627270e+04 3.98e+00 1.78e-10 5.31e-04 6s
44 -7.38552647e+04 -7.84757577e+04 4.52e+00 2.06e-10 4.91e-04 6s
45 -7.40079626e+04 -7.85031759e+04 4.28e+00 8.87e-11 1.28e-03 7s
46 -7.39126053e+04 -7.84981948e+04 4.22e+00 6.97e-11 1.24e-03 7s
47 -7.39760296e+04 -7.85010903e+04 4.19e+00 2.07e-11 1.23e-03 7s
48 -7.38244694e+04 -7.85590213e+04 4.16e+00 3.65e-11 3.43e-03 7s
49 -7.38287097e+04 -7.85584892e+04 4.15e+00 2.05e-11 3.43e-03 7s
50 -7.40238112e+04 -7.85785264e+04 4.12e+00 3.55e-11 4.43e-03 7s
51 -7.44612792e+04 -7.85757060e+04 3.53e+00 4.52e-11 7.89e-03 7s
Barrier performed 51 iterations in 7.32 seconds
Sub-optimal termination - objective -7.82592114e+04
-
You should really consider re-formulating your model, as the reported ranges, especially for the quadratic,
> Matrix range [2e-09, 6e+01]
> Objective range [8e-04, 5e+03]
> QObjective range [2e-09, 1e+05]border-line with the round-off error in double-precision arithmetic (think on any "standard" PC if you try this logical compassion, (1 + 1e-16 == 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 re-scaling 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,
0 -
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 right-hand 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
0 -
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 re-writing 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.
0 -
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 zi|k = H*xi|k, ui|k the predicted inputs, xi|k 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.0 -
Part 2:
In more detail, after some substitution the quadritic part of the optimization problem looks like:
with Z a banded null-space 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 re-scaling 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
0 -
Thanks for providing more details, and yes, I would try the re-scaling 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 less-aggressive scaling as well.
More information can be found in our numerical guidelines online.
Cheers,
0 -
Hi,
I have re-scaled 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: border-line with the round-off error in double-precision arithmetic (think on any "standard" PC if you try this logical compassion, (1 + 1e-16 == 1), you will get TRUE)?
That Matlab makes round-off 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/interior-point method.
Kind regards,
0 -
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 doble-check the answers as part of post-processing the solution, to make sure the solution is feasible etc.
Hope this helps.
0 -
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? Large-scale systems or small-scale 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?
0
Please sign in to leave a comment.
Comments
9 comments