# Complexity JuMP constraints

Hello there
I have a SDP problem with a SemiDefinite matrix M of size n \times n. I have a number c of constraints. There is a time of preparation, then the problem is given to the SDP solver (for example Hypatia). The solver repeats an iteration. Each iteration has a time of complexity :

c * n^3 + c^2 * n^2 + c^3 # for each iteration

What I need is the time complexity (or an approximation of it) of the preparation of the constraints made by JuMP, before the problem is given to Hypatia. This the most costly step of the program. Could anyone help ? Thanks !

By interest, what is made by JuMP at this moment ? I think it cancels some constraints, and gets the dual problem. But is there any more operations ?

Maybe I am wrong, and the preparation of the constraints are made by Hypatia. Could anyone tell me ?

Thanks a lot, for any help !
Gustave

The time of the preparation should be negligible. If itâ€™s not the it usually means the symbolic manipulation of the JuMP expression is not done efficiently. Could you share a piece of could so that we can identify the issue ?

Here is the code. Everything is done very fast, but when I launch optimize!(model) it takes a long time before beginning the computations (the iterations). I think this â€śpreparationâ€ť is done by JuMP ? Thanks for any answer â€¦

function get_problem_JuMP(calcul_lindbladien,n_modes::Int , max_degree::Int64 ,Obs::QuExpr,mode , T = Hypatia)
GC.gc()

println("=== Initialisation : max_degre = $max_degree, n_mode =$n_modes ===")
println("=== get_problem_JuMP_primal ===")

mList = MonomialList(n_modes,max_degree)
mDict = List_to_Dict(mList)
mList_2n = MonomialList(n_modes,max_degree * 2)

N = length(mDict)
Obs = QuantumAlgebra.normal_form(Obs)
index_one = mDict[ExprToTerm(one(Obs))]

if mode == "imprecise"
model = Model(T.Optimizer)
else
model = GenericModel{BigFloat}(T.Optimizer{BigFloat})
end

@variable( model , H[1:N, 1:N] in HermitianPSDCone() )

println("===== debut des contraintes =====")
# matrice SDP
for i1 in eachindex(mList)
for i2 in 1:i1
m1 = ExprToTerm(TermToExpr(mList[i1])')
m2 = mList[i2]
X = normal_form(TermToExpr(m1) * TermToExpr(m2))

@constraint( model , expectation(mDict,m1,m2,H) == expectation(mDict, X , H ) )
end
end

for m in mList_2n
if isrepresentable(mDict,lind) && (lind â‰  zero(lind))
@constraint( model ,  expectation(mDict,lind,H) == 0 )
end
end

# trace
@constraint( model , H[index_one,index_one] == 1)

# la minimisation
@objective( model , Min , real(expectation(mDict,Obs,H)))
println("===== fin des contraintes =====")

if mode == "imprecise"
if T == Clarabel
set_attribute(model, "tol_feas", tol_)
else
if T != SCS
set_attribute(model, "tol_inconsistent", tol_)
end
end
end

optimize!(model)

println("===== fin du probleme =====")

return objective_value(model)
end


after optimize(model) there is a wait, then it says â€ś60 conntraints out of 600 are equivalentâ€ť, then it after an other wait it begins the computations

Do you get this with SCS or Clarabel ? JuMP shouldnâ€™t print "60 contraints out of 600 are equivalentâ€ť, itâ€™s not doing any presolve so I would guess this is done by the solver. You can use @profview to see what is taking all this time: Profiler Â· Julia in VS Code

1 Like

I am using Hypatia !

Itâ€™s not a problem to wait, but I would like to know how long I have to wait, so that I need the complexity.

I gonna watch your link, thanks !
Gustave

PS : Indeed only Hypatia shows this message. but I merely need the complexity of this phase of the program !

1 Like

I have used @profview to spy the Hypatia algorithm. Apparently it uses a QR decomposition on an AbstractMatrix, using the LAPACK stdlib library. I still donâ€™t know the complexity, but I am near the answer ! thanks a lot !

1 Like