Adding objective to JuMP model changes feasibility?

I have written a function that is supposed to output whether the problem is feasible and the Gram matrix.

using DynamicPolynomials
using JuMP
using MosekTools
using SumOfSquares
@polyvar var1 var2
Solve the max log det problem for a polynomial.
Returns (isfeasible, Gram matrix)
function get_max_log_det(p)
    d = 2 # The degree can be inferred from p
    model = SOSModel()
    set_optimizer(model, () -> Mosek.Optimizer())
    @variable(model, Q[1:d÷2+1, 1:d÷2+1] in PSDCone())
    @variable(model, t)
    mons = monomials([var1, var2], d÷2)
    @constraint(model, mons' * Q * mons == p)
    vecQ = [Q[i, j] for j in 1:d÷2+1 for i in 1:j] # triangular portion only
    @constraint(model, vcat(t, 1, vecQ) in MOI.LogDetConeTriangle(d÷2+1))
    @objective(model, Max, t)
    return primal_status(model) == FEASIBLE_POINT, value.(Q)

When I run

get_max_log_det((var1 + var2)^2)

this returns infeasible. If I remove the line

@objective(model, Max, t)

it returns feasible on the same input. What is going on?

1 Like

That’s a weird one! I don’t have Mosek so I can’t reproduce this, but do you have the full log of the solver? What is termination_status(model)?

cc @blegat

Here is the log:

Name :
Objective sense : max
Type : CONIC (conic optimization problem)
Constraints : 20
Cones : 2
Scalar variables : 12
Matrix variables : 2
Integer variables : 0

Optimizer started.
Presolve started.
Linear dependency checker started.
Linear dependency checker terminated.
Eliminator started.
Freed constraints in eliminator : 0
Eliminator terminated.
Eliminator - tries : 1 time : 0.00
Lin. dep. - tries : 1 time : 0.00
Lin. dep. - number : 0
Presolve terminated. Time: 0.00
Name :
Objective sense : max
Type : CONIC (conic optimization problem)
Constraints : 20
Cones : 2
Scalar variables : 12
Matrix variables : 2
Integer variables : 0

Optimizer - threads : 8
Optimizer - solved problem : the primal
Optimizer - Constraints : 13
Optimizer - Cones : 4
Optimizer - Scalar variables : 11 conic : 11
Optimizer - Semi-definite variables: 1 scalarized : 10
Factor - setup time : 0.00 dense det. time : 0.00
Factor - ML order time : 0.00 GP order time : 0.00
Factor - nonzeros before factor : 70 after factor : 70
Factor - dense dim. : 0 flops : 1.00e+03
0 1.3e+00 1.3e+00 4.3e+00 0.00e+00 -1.655676798e+00 1.610204003e+00 1.0e+00 0.00
1 3.7e-01 3.7e-01 8.9e-01 9.45e-02 -5.818507280e-01 5.773961726e-01 2.8e-01 0.00
2 1.4e-01 1.4e-01 2.7e-01 3.93e-01 -1.146083946e+00 -6.447706664e-01 1.1e-01 0.00
3 3.7e-02 3.7e-02 7.0e-02 3.26e-01 -1.717438140e+00 -1.641594153e+00 2.8e-02 0.00
4 1.0e-02 1.0e-02 1.3e-02 5.01e-01 -2.457131191e+00 -2.453081417e+00 8.1e-03 0.00
5 3.4e-03 3.4e-03 5.2e-03 1.22e-01 -3.087023328e+00 -3.192220839e+00 2.7e-03 0.00
6 8.5e-04 8.5e-04 8.8e-04 4.47e-01 -3.825171346e+00 -3.888582424e+00 6.6e-04 0.00
7 2.0e-04 2.0e-04 2.5e-04 1.39e-01 -4.564521994e+00 -4.689373051e+00 1.6e-04 0.00
8 6.4e-05 6.4e-05 6.2e-05 4.00e-01 -5.129370172e+00 -5.204952416e+00 5.0e-05 0.00
9 2.4e-05 2.4e-05 3.7e-05 3.98e-03 -5.598022046e+00 -5.808490690e+00 1.8e-05 0.00
10 4.2e-06 4.2e-06 4.2e-06 3.59e-01 -6.530696534e+00 -6.619495875e+00 3.3e-06 0.00
11 1.0e-06 1.0e-06 1.0e-06 1.46e-01 -7.174227786e+00 -7.262701538e+00 8.1e-07 0.00
12 3.1e-07 3.1e-07 4.5e-07 -1.03e-01 -7.811188148e+00 -8.004204592e+00 2.4e-07 0.00
13 6.4e-08 6.4e-08 6.3e-08 3.47e-01 -8.633751855e+00 -8.723814347e+00 4.9e-08 0.00
14 1.4e-08 1.4e-08 1.5e-08 1.25e-01 -9.358929499e+00 -9.464805567e+00 1.0e-08 0.00
15 3.6e-09 3.6e-09 4.8e-09 2.15e-02 -1.004516842e+01 -1.020221703e+01 2.8e-09 0.00
16 1.1e-09 1.1e-09 1.1e-09 3.79e-01 -1.064022593e+01 -1.072692037e+01 8.6e-10 0.00
17 3.6e-10 3.6e-10 5.4e-10 2.15e-02 -1.120347431e+01 -1.140423976e+01 2.8e-10 0.00
18 7.2e-11 7.2e-11 7.2e-11 3.58e-01 -1.203693766e+01 -1.212827943e+01 5.6e-11 0.01
19 1.6e-11 1.6e-11 1.7e-11 1.44e-01 -1.271725663e+01 -1.281794434e+01 1.3e-11 0.01
20 4.8e-12 2.3e-10 6.7e-12 -3.30e-02 -1.336859284e+01 -1.354660764e+01 3.7e-12 0.01
21 1.2e-12 5.7e-11 1.2e-12 3.63e-01 -1.407159531e+01 -1.416122865e+01 9.2e-13 0.01
22 2.7e-13 1.4e-12 3.4e-13 8.62e-02 -1.483331174e+01 -1.497947492e+01 2.1e-13 0.01
23 8.4e-14 3.1e-12 8.0e-14 3.78e-01 -1.539141667e+01 -1.547649678e+01 6.5e-14 0.01
24 2.9e-14 3.5e-11 4.4e-14 1.99e-03 -1.591986591e+01 -1.613892969e+01 2.2e-14 0.01
25 5.2e-15 6.7e-12 5.4e-15 3.52e-01 -1.681342524e+01 -1.690765686e+01 4.0e-15 0.01
26 1.3e-15 2.1e-12 1.3e-15 1.55e-01 -1.744180270e+01 -1.753437229e+01 1.0e-15 0.01
27 3.9e-16 2.9e-12 6.4e-16 -1.03e-01 -1.807392806e+01 -1.827764523e+01 3.1e-16 0.01
28 8.0e-17 6.8e-13 1.9e-17 3.46e-01 -1.889427670e+01 -1.898777838e+01 6.2e-17 0.01
29 1.7e-17 4.0e-12 7.1e-17 1.26e-01 -1.960156319e+01 -1.970777971e+01 1.4e-17 0.01
30 4.8e-18 6.6e-11 5.6e-17 -2.88e-03 -2.027999009e+01 -2.044716454e+01 3.8e-18 0.01
31 1.4e-18 1.7e-11 6.9e-18 3.72e-01 -2.090872078e+01 -2.099786509e+01 1.1e-18 0.01
32 3.9e-19 1.3e-11 9.4e-18 5.22e-02 -2.156006526e+01 -2.173914036e+01 3.1e-19 0.01
33 3.9e-19 1.3e-11 9.4e-18 3.68e-01 -2.156006526e+01 -2.173914036e+01 3.1e-19 0.01
34 3.9e-19 1.3e-11 9.4e-18 3.68e-01 -2.156006526e+01 -2.173914036e+01 3.1e-19 0.01
Optimizer terminated. Time: 0.01

Maybe I shouldn’t have said “infeasible” above. It is only “not FEASIBLE_POINT.”

julia> primal_status(model)

julia> termination_status(model)
SLOW_PROGRESS::TerminationStatusCode = 19

I didn’t think about changing the solver until you mentioned it. With SCS I get the expected outcome, so I suppose this is a Mosek specific problem.

I thought one explanation may be that the interior point method of Mosek doesn’t quite work here because the only feasible point for this problem is on the constraint boundary. But that isn’t consistent with how Mosek can detect feasibility when there is no objective.

1 Like

The problem is that without the objective, Mosek can stop when it finds any primal and dual feasible solution.

With the objective, it has to find the best primal solution, and it stalls when trying to do that. You could try different Mosek settings, but otherwise @blegat may have some suggestions for how to reformulate this into something a bit nicer for Mosek to solve.

The two most common explanations for Mosek running into slow progress / numerical issues are:

  • Bad scaling of the original problem, e.g., some coefficients are very large and some are very small.
    This can lead to numerical/rounding issues and cause the optimizer to stall
  • Lack of strong duality / constraint qualification. The typical example is a problem with a bounded objective value but the optimum is not reached, e.g., minimize 1/x for x > 0. Mosek has other examples in their modeling cookbook (see Example 8.6, for instance).

It’s not impossible that the objective you provide causes it to loose strong duality and run into numerical issues.

1 Like