jump-dev / Convex.jl

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

`lieb_ando` reformulation doesn't propogate DCP information correctly #683

Closed ericphanson closed 4 months ago

ericphanson commented 4 months ago
julia> using Convex

julia> A = Variable(2,2)
Variable
size: (2, 2)
sign: real
vexity: affine
id: 406…508

julia> B = Variable(2,2)
Variable
size: (2, 2)
sign: real
vexity: affine
id: 169…045

julia> K = rand(2,2)
2×2 Matrix{Float64}:
 0.388952  0.227043
 0.64608   0.220724

julia> lieb_ando(A, B, K, 1//1)
real (affine; real)
└─ sum (affine; real)
   └─ diag (affine; real)
      └─ * (affine; real)
         ├─ …
         └─ …

julia> lieb_ando(A, B, K, -1//2)
real (affine; real)
└─ sum (affine; real)
   └─ diag (affine; real)
      └─ * (affine; real)
         ├─ …
         └─ …

help?> lieb_ando
search: lieb_ando

  Returns LinearAlgebra.tr(K' * A^{1-t} * K * B^t) where A and B are positive
  semidefinite matrices and K is an arbitrary matrix (possibly rectangular).

  Disciplined convex programming information: lieb_ando(A,B,K,t) is concave in
  (A,B) for t in [0,1], and convex in (A,B) for t in [-1,0] or [1,2]. K is a
  fixed matrix.

Seems like these should be concave/convex, not affine. The issue is similar to https://github.com/jump-dev/Convex.jl/issues/682#issuecomment-2122446577: extended formulations typically must be atoms to propagate DCP information correctly. Here, we add constraints to a new variable we create here and here.

I didn't see any other extended formulations in src/reformulations luckily; the other reformulations there simply compose operations without adding new variables or constraints.

We should also update the dev docs to mention this. I for one didn't fully realize this issue until today.