Complexity JuMP constraints

Specific Domains Optimization (Mathematical)
1

Hello there :slight_smile:
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

2

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 ?

3

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

    # Add Lindblad constraint 
    for m in mList_2n
        lind = calcul_lindbladien(TermToExpr(m))
        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

4

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
5

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
6

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