jump-dev
Make use of SCS-3.2.8 new features
- [x] complex PSD Cone (#311 #315)
- [ ] Direct solver on the GPU (through cuDSS_jll)
- requires compiling a new SCS_GPU-style library
- [x] The loget cone
- [x] the trace (or nuclear) norm cone
- [ ] ell1 norm cone (max of the sum of absolute column values)
- [ ] Ky Fan (or sum of the k largest eigenvalues) norm cone
I plan to add support for the new cuDSS library, as soon as #314 is resolved;
also, since we will need to release a new version with these changes, maybe it makes sense to switch to blastrampoline as well? (#296)
I don't know enough about GPUs to fix #314. I'm just playing whackamole. It surprises me that there aren't any compat bounds in SCS_GPU_jll?
requires recompiling SCS_jll with the new cones turned on
Why are they not on by default? Because it breaks the API like adding the complex PSD?
You'll have to ask @dance858 or @bodono. It doesn't break the C API so that's definitely not the reason.
They’re not enabled by default in the C build because we haven’t officially announced SCS support for those cones yet. @transurgeon is currently planning to work on integrating them into CVXPY. From what I understand, incorporating them isn’t straightforward. It requires solver-dependent canonicalization paths which CVXPY doesn’t currently implement (?).
If you decide to add support for them and want something to test with, there are a few examples in the spectral_examples folder of this repository: https://github.com/dance858/SpectralSCSExperiments
We also have a paper describing these examples in detail. It hasn’t been publicly released yet (it’s been stuck on a desk for a year), but I’d be happy to share a copy if you think it would be helpful.
I can't speak for CVXPY, but supporting them in JuMP is quite easy. MathOptInterface already has the nuclear norm cone and the logdet cone, so we'd just need to write the bridge to SCS's format. It would be helpful if you could tell us what the format is, though. Are you assuming that the matrices are symmetric, and using the same vectorization as in the PSD cone?
A bit more work would be to support the Ky Fan cone, because first that would need to be written, but still is not a lot of work, as it's mostly copy-pasting.
It doesn't break the C API so that's definitely not the reason.
Looks like it does to me:
https://github.com/cvxgrp/scs/blob/c8297172633bcb3a10d4781a19d4769ce5282d29/include/scs.h#L146-L163
This adds some new fields, and dsize, nucsize, ell1_size, and sl_size may not be initialised to 0 if we just pass in our existing
https://github.com/jump-dev/SCS.jl/blob/45f1507af0c19bc26b4da5310168b9c145d47037/src/c_wrapper.jl#L49-L65
It requires solver-dependent canonicalization paths which CVXPY doesn’t currently implement (?)
You may have already read it, but if not, see our paper on MathOptInterface https://arxiv.org/abs/2002.03447 :smile:
A bit more work would be to support the Ky Fan cone
Is it supported in any other solver? I guess we can first add it to SCS, and then add it to MOI if there is broader interest.
It definitely breaks our interface, but not the C API. If you call SCS from C you pass it a struct, and only define the fields you're interested in. SCS handles internally the undefined fields correctly.
It definitely breaks our interface, but not the C API
I guess we're arguing about a very subtle semantic difference. From my perspective, it breaks our interface, and we're calling the C API, so I regard it as a breaking change to the C API. The only non-breaking way to extend a public struct in C is to add new fields to the end, and only query their values if the caller explicitly opts in by setting some already existing field, or by calling a new function.
If there was ScsCone scs_new_cone(void); that we then got to set non-default fields, that would be non-breaking.
I've opened a PR to Yggdrasil to recompile: https://github.com/JuliaPackaging/Yggdrasil/pull/12314
Maybe it's time we changed to 300.200.900 version numbers?
I'm talking about this code here I wrote: https://github.com/cvxgrp/scs/blob/master/test/problems/complex_PSD.h
I just create a ScsCone, and set the fields I need. It doesn't matter which other fields exist, it works all the same. Not that it matters, we can't do that from Julia anyway.
As for the version numbers, isn't that why we have build numbers? Wouldn't it be nicer to do 3.2.9+1?
I just create a ScsCone, and set the fields I need
This requires the new header to know the correct size of ScsCone.
isn't that why we have build numbers? Wouldn't it be nicer to do 3.2.9+1?
No, because we already have 3.2.9, and if we tagged USE_SPECTRAL_CONES as 3.2.9+1 it would break our existing code. Hence, its a breaking change.
The compat bound is strict, SCS_jll = "=3.2.9". Would that allow an update to 3.2.9+1?
I see. Then I think the only sane alternatives are 300.200.900 or waiting for 3.2.10. If you want to add support for the new cones now then I'd go with the former, otherwise the latter.
Then I think the only sane alternatives are 300.200.900 or waiting for 3.2.10
Yes, exactly. Which is what I could have written explicitly instead of "Maybe it's time we changed..." 😆
Since there has now been a few times we're we've wanted to recompile things between SCS versions, I decided to use the offset: https://github.com/JuliaPackaging/Yggdrasil/pull/12314
We also have a paper describing these examples in detail. It hasn’t been publicly released yet (it’s been stuck on a desk for a year), but I’d be happy to share a copy if you think it would be helpful.
Yes, please! I can probably figure it out by looking at the source, but a proper definition of each of the cones would be helpful. There are lots of subtle differences, like variable ordering, and whether you scale the cones like PSD, etc.
Here are our conventions for the cones. For the log-determinant cone and the sum-of-k-largest eigenvalue cone, we use the same scale sqrt2-scaling as for the PSD cone. For the nuclear norm cone, we assume m >= n (if that's not the case it should be possible to just transpose the input to the nuclear norm). In the definition of the sum-of-k-largest eigenvalue cone, $\boldsymbol{\lambda}_i$ denotes the ith largest eigenvalue.
Thanks! So if one wants a trace norm cone specialized to Hermitian matrices one should just use the Ky Fan cone summing all eigenvalues, and it should be much faster, right?
Hmm. Is the trace norm cone for Hermitian matrices something like $\sum_{i=1}^n |\lambda_i(X)| \leq t$? If you use the Ky fan cone (which is what I refer to as sum-of-largest-eigenvalues cone, right?) you don't get the absolute value?
Oh, ok, so you're summing the k largest eigenvalues, not the k largest singular values. Nevermind then, this is not the Ky Fan cone, and it does not reduce to the trace norm.
Do you have a link or something to the Ky Fan cone? I haven't heard of it but it sounds super interesting.
Not really. You can find lots of things about the Ky Fan norm, and it is straightforward to make a cone for it.
For the nuclear norm cone, we assume m >= n (if that's not the case it should be possible to just transpose the input to the nuclear norm)
I need to think about this one. Why can't SCS internally transpose?
I have a bridge for transposing in #328, but it would be so much nicer if SCS just did this internally.
I think it would make sense for MOI to do the transposition, and so no bridge would be needed. It would also be useful for Hypatia, except that it is the other way around: it needs the number of columns to be >= the number of rows.
@dance858 They are useful in quantum information theory, see e.g. https://arxiv.org/abs/0909.3907
It would also be useful for Hypatia, except that it is the other way around: it needs the number of columns to be >= the number of rows.
This is an argument for not doing it in MOI; there is no standardized definition between solvers.