Mosek interior point stopping criterion and basis identification

Specific Domains Optimization (Mathematical)
,
1

Hi!

I have noticed a weird behaviour of Mosek: when solving a linear program with the interior-point optimizer, the primal and dual feasibility tolerances do not seem to be taken into account when basis identification is turned on.

using JuMP
using Mosek
using MosekTools

model = Model(Mosek.Optimizer)

set_attribute(model, "MSK_IPAR_OPTIMIZER", Mosek.MSK_OPTIMIZER_INTPNT)
# set_attribute(model, "MSK_IPAR_INTPNT_BASIS", Mosek.MSK_BI_NEVER)

set_attribute(model, "MSK_DPAR_INTPNT_TOL_PFEAS", 1e-14)
set_attribute(model, "MSK_DPAR_INTPNT_TOL_DFEAS", 1e-14)

@variable(model, x >= 0.0)
@variable(model, y >= 0.0)
@objective(model, Min, -x)

@constraint(model, x + y <= 1)
@constraint(model, x + 2*y >= 1)

optimize!(model)

The code above produces the following output.

ITE PFEAS    DFEAS    GFEAS    PRSTATUS   POBJ              DOBJ              MU       TIME  
0   5.0e-01  2.0e-01  5.8e-02  0.00e+00   -1.000000000e+00  -9.000000000e-01  1.9e-01  0.00  
1   2.2e-03  8.9e-04  2.6e-04  1.05e+00   -9.998086636e-01  -9.991418684e-01  8.4e-04  0.00  
2   2.2e-07  8.9e-08  2.6e-08  1.00e+00   -9.999999809e-01  -9.999999141e-01  8.4e-08  0.00  
3   2.2e-11  8.9e-12  2.6e-12  1.00e+00   -1.000000000e+00  -1.000000000e+00  8.4e-12  0.00  
Basis identification started.
Primal basis identification phase started.
Primal basis identification phase terminated. Time: 0.00
Dual basis identification phase started.
Dual basis identification phase terminated. Time: 0.00
Basis identification terminated. Time: 0.00
Optimizer terminated. Time: 0.00

The solver says that the model is solved and feasible but the primal feasibility report shows that the first constraint is only satisfied up to a tolerance of approximately 10^{-11}.

Switching off basis indentification by uncommenting the proper line in the above code results in the following output.

ITE PFEAS    DFEAS    GFEAS    PRSTATUS   POBJ              DOBJ              MU       TIME  
0   5.0e-01  2.0e-01  5.8e-02  0.00e+00   -1.000000000e+00  -9.000000000e-01  1.9e-01  0.00  
1   2.2e-03  8.9e-04  2.6e-04  1.05e+00   -9.998086636e-01  -9.991418684e-01  8.4e-04  0.00  
2   2.2e-07  8.9e-08  2.6e-08  1.00e+00   -9.999999809e-01  -9.999999141e-01  8.4e-08  0.00  
3   2.2e-11  8.9e-12  2.6e-12  1.00e+00   -1.000000000e+00  -1.000000000e+00  8.4e-12  0.00  
4   2.7e-15  6.7e-16  5.4e-15  1.00e+00   -1.000000000e+00  -1.000000000e+00  8.4e-16  0.00  
Optimizer terminated. Time: 0.00

The primal feasbility report now says that the second constraint is only satisfied up to a tolerance of 10^{-15}.

Does someone have an idea of what is happening there? Thanks in advance!

1 Like
2

Hi @rpetit,

Take a read of Tolerances and numerical issues · JuMP

You cannot reasonably expect Mosek to find a solution to a tolerance of 1e-14. Is there anything earlier in the log warning about the tolerances being too tight?

You might also be interested in https://www.blogger.com/blogger.g?blogID=2124323532937076865#overview The MOSEK blog: Should Mosek optimizer parameters be tweaked?

3

If you really need such a high precision you cannot use Float64 as your data type. You need to use Double64 (from DoubleFloats), Float128 (from Quadmath), or BigFloat (from the standard library).

You need of course solvers that can handle these higher precision types, currently there exist two: Hypatia and Clarabel.

1 Like
4

Hi,

Thanks a lot for the two links! I naively thought I could get improved precision by tweaking a bit the solver’s parameters. There are no warnings in the log about the tolerances. Looking at Mosek’s documentation these values seem to be allowed.

1 Like
5

Thanks a lot, I’ll definitely have a look at Hypatia and Clarabel!

1 Like