[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Support for complex PSD cone #290

Open
araujoms opened this issue Sep 29, 2024 · 4 comments
Open

Support for complex PSD cone #290

araujoms opened this issue Sep 29, 2024 · 4 comments

Comments

@araujoms
Copy link

Are you interested in adding support for the complex PSD cone? It shows up all the time in quantum information problems, and is much more efficient than mapping the problem to the real PSD cone via

$$A \mapsto \begin{pmatrix}\Re(A) & \Im(A)\\ -\Im(A) & \Re(A)\end{pmatrix}$$

I just did it for another ADMM solver, COSMO: oxfordcontrol/COSMO.jl#194

If you're interested I volunteer to do it for SCS as well. I would need help with the interface, though.

@bodono
Copy link
Member
bodono commented Oct 1, 2024

Sure, that would be very interesting! I'm happy to help with the interface. If you get something working we can run some tests in python to see the advantage the approach has over converting into a regular PSD cone, I guess it should be something like 4x faster?

@araujoms
Copy link
Author
araujoms commented Oct 1, 2024

I'm glad you're interested! Naïvely I would expect a 8x speedup, as the complexity in ADMM is dominated by diagonalization, which is roughly $d^3$ complexity, and we're dividing dimension by two. This is roughly what I observed when benchmarking COSMO.

My proposal is that I take care of core functions like set_up_sd_cone_work_space and proj_semi_definite_cone, and you connect that to the rest of SCS so that they can actually be used. In Julia I used some metaprogramming to avoid code duplication, but for C that's a dubious proposition, so I'd just accept the inelegance.

A design choice that needs to made now is how to vectorize the complex matrix. I'd use the same vectorization as Hypatia, adapted to the lower triangular for consistency with your real psd cone. That means, x[0,0], real(x[1,0]), imag(x[1,0]), x[1,1], real(x[2,0]), imag(x[2,0]), etc. Is that fine?

Also, is there any particular reason why you're using syev instead of syevr? The latter is significantly faster.

@bodono
Copy link
Member
bodono commented Oct 4, 2024

Great, thanks for the explanation! That vectorization seems fine, though do you need to scale the diagonals by sqrt(2)? See details here for why it's necessary for the usual sdp cone: https://www.cvxgrp.org/scs/api/cones.html#semidefinite-cones

I switched from syevr to syev a while back, I think for robustness issues, though perhaps syevr is better:
e07d5ab#diff-3ff078d764f5668dad6750cc5905768ecdfb80e76f67d3e8fa2f6e66fd1c2bc9R562

@araujoms
Copy link
Author
araujoms commented Oct 4, 2024

Great, I'll use this vectorization then, together with syevr. I know one needs to scale the off-diagonals by sqrt(2), I just didn't feel it was worth mentioning.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants