jump-dev / Convex.jl

A Julia package for disciplined convex programming
https://jump.dev/Convex.jl/stable/
Other
557 stars 119 forks source link

Add quantum conditional entropy example #671

Closed ericphanson closed 1 month ago

ericphanson commented 1 month ago

this is the second example from https://github.com/jump-dev/Convex.jl/pull/418#issuecomment-832190560

I thought it could be nice to have some examples using some of the CVXQUAD functionality. I put in a lot of quantum information theory preliminaries, but maybe we could trim some back if it's too much.

This example originally had 23s of formulation time and 4s solve time. I profiled and found permutedims_matrix was very slow and allocating (and it gets used a lot, since it is used for transpose and thus for vcat). I was able to optimize it by constructing the sparse matrix directly (in COO format). Now we have 3s formulation time and the same 4s solve time, which seems much more acceptable (maybe a little slow still, but I didn't see any other low hanging fruit).

BTW, here the reformulations and bridges really blow up the problem size:

julia> problem
Problem statistics
  problem is DCP         : true
  number of variables    : 1 (32 scalar elements)
  number of constraints  : 3 (67 scalar elements)
  number of coefficients : 31
  number of atoms        : 29
  ...

julia> get_info(problem.model)
(n_variables = 1639, n_constraints = 16, n_elements = 18259, n_constants = 43103)

using

julia> function get_info(model)
           n_constraints = 0
           n_elements = 0
           n_variables = MOI.get(model, MOI.NumberOfVariables())
           n_constants = 0
           for (F, S) in MOI.get(model, MOI.ListOfConstraintTypesPresent())
               n_constraints += MOI.get(problem.model, MOI.NumberOfConstraints{F,S}())

               for inds in MOI.get(model, MOI.ListOfConstraintIndices{F,S}())
                   set = MOI.get(model, MOI.ConstraintSet(), inds)
                   n_elements += MOI.dimension(set)
                   f = MOI.get(model, MOI.ConstraintFunction(), inds)
                   n_constants += count_size(f)
               end
           end
           return (; n_variables, n_constraints, n_elements, n_constants)
       end
get_info (generic function with 1 method)

julia> function count_size(f::MOI.VectorAffineFunction)
           return length(f.terms) + length(f.constants)
       end
count_size (generic function with 1 method)

I think Hypatia can be used to avoid some of the reformulations; I guess to hook everything up, we would need to move the sets to MOI and update Hypatia to support them directly (?).

codecov[bot] commented 1 month ago

Codecov Report

All modified and coverable lines are covered by tests :white_check_mark:

Project coverage is 98.09%. Comparing base (d19955e) to head (7b10c27).

Additional details and impacted files ```diff @@ Coverage Diff @@ ## master #671 +/- ## ======================================= Coverage 98.09% 98.09% ======================================= Files 89 89 Lines 5150 5152 +2 ======================================= + Hits 5052 5054 +2 Misses 98 98 ```

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

ericphanson commented 1 month ago

https://jump.dev/Convex.jl/previews/PR671/examples/optimization_with_complex_variables/quantum_conditional_entropy/

odow commented 1 month ago

I guess to hook everything up, we would need to move the sets to MOI and update Hypatia to support them directly

Yes, I think @blegat has a plan for this.