Need a help with the suboptimal solution obtained with the barrier-method ?
AnsweredHi there,
I am using Gurobi as the solver to solve a QCP problem and here is an extract from the log file.
Academic license - for non-commercial use only
Optimize a model with 100 rows, 92 columns and 386 nonzeros
Model has 8 quadratic constraints
Coefficient statistics:
Matrix range [1e-03, 2e+00]
QMatrix range [1e+00, 1e+00]
Objective range [1e+00, 1e+00]
Bounds range [0e+00, 0e+00]
RHS range [2e-03, 8e+02]
Presolve removed 12 rows and 0 columns
Presolve time: 0.00s
Presolved: 88 rows, 92 columns, 368 nonzeros
Presolved model has 8 second-order cone constraints
Ordering time: 0.00s
Barrier statistics:
Dense cols : 3
AA' NZ : 8.160e+02
Factor NZ : 9.100e+02
Factor Ops : 1.015e+04 (less than 1 second per iteration)
Threads : 1
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 -8.46577998e+02 -1.57437522e+03 1.05e+02 4.15e-01 1.38e+01 0s
1 -1.39949798e+03 -1.52859693e+03 1.88e+01 2.43e-02 2.16e+00 0s
2 -1.32423063e+03 -1.30922833e+03 6.92e+00 2.06e-03 9.52e-01 0s
3 -1.15782307e+03 -1.18788049e+03 6.37e+00 5.76e-09 2.11e+00 0s
4 -9.64425722e+02 -1.01413752e+03 3.87e+00 7.64e-11 2.97e+00 0s
5 -8.02374350e+02 -6.82516543e+02 2.13e+00 1.74e-11 2.31e+00 0s
6 -3.63752087e+02 -4.49477966e+02 5.71e-01 2.49e-10 4.00e+00 0s
7 1.02164374e+02 -1.82160585e+02 8.95e-07 1.55e-09 4.66e+00 0s
8 1.62852330e+01 -3.98582461e+01 4.05e-08 7.68e-10 6.19e-01 0s
9 1.39947843e+00 -1.07112348e+00 1.29e-08 1.59e-08 2.62e-02 0s
10 6.30790779e-01 3.93874941e-01 1.72e-07 6.80e-07 2.52e-03 0s
11 6.69621595e-01 5.60940610e-01 6.44e-06 4.04e-07 1.13e-03 0s
12 5.93039123e-01 5.93053159e-01 3.21e-04 1.52e-03 1.68e-04 0s
13 6.01396622e-01 6.01519689e-01 4.49e-05 1.40e-03 1.33e-05 0s
14 6.01670379e-01 6.01672936e-01 1.82e-02 3.40e-01 1.20e-06 0s
15 6.01683230e-01 6.01685441e-01 2.08e-02 1.56e+00 2.61e-07 0s
16 6.01697308e-01 6.01698105e-01 2.99e-02 6.95e-01 3.70e-09 0s
17 6.00736660e-01 6.01203234e-01 4.80e-01 9.44e+01 1.03e-08 0s
18 6.01153212e-01 6.01197384e-01 5.99e-01 3.53e+01 6.48e-09 0s
19 6.01117675e-01 6.01189894e-01 1.42e+01 3.50e+01 1.07e-07 0s
20 6.01156410e-01 6.01235258e-01 1.42e+01 3.50e+01 1.06e-07 0s
21 6.01156479e-01 6.01235336e-01 1.44e+01 3.50e+01 1.06e-07 0s
22 6.00191182e-01 6.01013148e-01 3.65e+00 3.05e+01 5.37e-08 0s
23 6.01007675e-01 6.01013358e-01 3.05e+00 3.97e+00 8.56e-10 0s
24 6.01012274e-01 6.01012278e-01 4.81e+00 4.01e+02 1.40e-11 0s
25 6.01012716e-01 6.01012279e-01 5.57e+02 7.29e+02 1.25e-09 0s
26 6.01012632e-01 6.01012206e-01 5.50e+02 2.63e+03 1.37e-07 0s
27 6.01012628e-01 6.01012199e-01 5.46e+02 2.87e+03 1.42e-07 0s
28 6.01012578e-01 6.01012198e-01 1.43e+03 2.89e+03 1.35e-07 0s
29 6.01012553e-01 6.01012193e-01 1.27e+03 6.12e+03 2.41e-07 0s
30 6.01012534e-01 6.01012181e-01 7.45e+03 7.00e+03 6.16e-08 0s
31 6.01005237e-01 6.01011301e-01 1.30e+05 8.01e+03 6.23e-07 0s
32 6.01005626e-01 6.01041132e-01 1.19e+05 2.67e+05 1.01e-05 0s
33 6.01001439e-01 6.01002121e-01 1.06e+05 2.46e+06 4.75e-05 0s
34 6.00992379e-01 6.00203239e-01 5.83e+04 3.22e+07 5.64e-04 0s
35 6.00838757e-01 5.99549769e-01 3.20e+04 1.42e+08 2.20e-03 0s
36 5.99297000e-01 5.99512160e-01 1.75e+04 7.81e+07 2.34e-02 0s
37 5.99261491e-01 5.99512068e-01 1.75e+04 7.81e+07 2.34e-02 0s
38 5.99010339e-01 5.99484381e-01 1.75e+04 7.82e+07 2.31e-02 0s
39 5.83341766e-01 5.93684192e-01 1.69e+04 1.03e+08 3.23e-03 0s
40 6.13252349e-01 5.99673749e-01 4.65e+05 2.55e+08 1.74e-02 0s
41 6.14734580e-01 6.12315164e-01 5.12e+05 3.95e+08 9.86e-02 0s
42 6.16108808e-01 5.91858039e-01 3.94e+05 3.83e+09 1.33e+00 0s
43 5.51667285e-01 5.78813309e-01 6.30e+05 4.60e+09 1.91e+00 0s
44 6.59529288e-01 5.81310583e-01 5.30e+05 5.47e+09 3.54e+00 0s
45 6.49683270e-01 4.99397707e-01 3.57e+05 2.24e+10 9.32e+00 0s
46 1.04657199e+00 5.14489538e-01 1.79e+06 2.31e+10 1.64e+01 0s
47 1.22874784e+00 5.01640577e-01 2.64e+06 1.38e+10 3.94e+01 0s
48 9.69607430e-01 4.21418471e-01 2.78e+06 1.42e+10 4.17e+01 0s
49 9.68320353e-01 2.57016980e-01 2.79e+06 1.68e+10 4.94e+01 0s
50 7.07204551e-01 2.75881202e-01 1.47e+06 7.19e+09 1.30e+01 0s
51 6.88526451e-01 -1.40550752e-01 1.61e+06 1.65e+10 3.08e+01 0s
52 7.67940047e-01 -2.28118046e-01 6.45e+06 2.46e+10 4.56e+01 0s
Barrier performed 52 iterations in 0.01 seconds
Sub-optimal termination - objective 6.01396622e-01
In this problem, I have set BarHomogeneous=1, because in a previous attempt, I ended up getting an error message saying that the model is unbounded or infeasible, which is impossible for this problem as far as I understand. Hence, I decided to set the above parameter after reading the article on "Numerical Issues in Gurobi". Furthrermoe, I understood that the barrier method is the only possible choice for QCP problems.
However, still I am in doubt whether the sub-optimal termination is correct, because I see a significant oscillation in the primal and dual residuals for close values of the primal objective ?
Can anyone please share your opinion on this ?
In addition to that, I would really appreciate if anyone could share their ideas for me to improve the accuracy of the sub-optimal termination in this problem.
Thanks in advance.
-
Hi Gayan,
It seems that your model is on the edge of (in)feasibility. This can happen even if the coefficient ranges are OK, e.g., if the feasible region is extremely small. You can see this behavior by the primal and dual residuals suddenly increasing by a lot.
Sub-optimal termination is printed when the barrier algorithm does not make any (or only very small) progress in the solution value and cannot decrease the dual residual, meaning that although the final convergence criterion is met, the dual infeasibility cannot be reduced. In your case, the residuals increase rapidly and Gurobi reports the last good enough solution. This is often the case for shaky numerics.
You can try to overcome this issue by either reformulating your problem and/or experimenting with the following parameters:
- set NumericFocus to 2 or 3
- experiment with the value of BarCorrectors, e.g., set it to 10 or 1000
- turn off Presolve
- decrease the tolerances BarConvTol, BarQCPConvTol, FeasibilityTolBest regards,
Jaromił0
Please sign in to leave a comment.
Comments
1 comment