-
Notifications
You must be signed in to change notification settings - Fork 134
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
Bug in SCS SDP solver #40
Comments
This has confused me many times, and I had to try and un-confuse myself all over again when I saw this issue. The README is definitely lacking on this, so I have to update that too. I think the basic idea is the following: The question here is how do we define the semi-definite cone of parameter This all means if we want to have the objective In other words you first have to perform this rescaling on the input data, pass it to SCS, then SCS will return More info from MOSEK and CVXOPT: I'll rework the example you gave too, see how it turns out with the scaling. |
I should say that I'm open to changing how SCS does it if it can be done better. The thing that doesn't make sense is to pass in |
I clobbered my python install, so here is your example in matlab, with all the rescaling:
scaling function:
stuffing the matrix
|
This is what the above script ends up with in
|
I see. That is kind of confusing. For the moment I'll change cvxpy so it passes in scaled data. I just tried this and everything works fine. It would be helpful too if you could clarify all of this in the documentation, as you mentioned. But longer term this seems more like an internal SCS issue than something the modeling framework should know about. Could you change the operations involving PSD variables in SCS to use the scaling, so that cvxpy doesn't need to do the scaling? Or could you rescale the data in the Python interface? Another solution would be to have a higher level interface like mathprogbase that handles all the details of going from cvxpy's idea of a cone program to what SCS (or any other cone solver) expects. |
Agreed that from the modeling perspective, I'd consider the rescaling as an internal solver detail. |
thanks @bodono. I'm inclined to think that scaling is an internal solver detail, and not something I should handle at the Convex.jl layer. Probably it should live in SCS.jl. But I'd encourage you to think of the lower triangular encoding as being just an encoding: the matrices really are in S^n. When you say you're taking inner products, I assume (as a modeler) you're taking the standard inner product in S^n, which does not require me to scale the off diagonal entries by sqrt(2). If you buy that the input format is just an input format, and not the "real" representation of the problem, I'd say the scaling should live in SCS proper. |
I would argue that it is actually a modeling layer issue, since all data preparation is a modeling layer issue, and this is just another step in data preparation. The contract that SCS is agreeing to is that it will find a point that satisfies the KKT conditions:
where the inner products are the standard ones in R^n, no special cases. The cone S^n cannot be represented as simply stuffing the lower triangular entries into the upper triangle, because then the standard inner-product and the projection method will break. So, we define the cone to be the set of vectors that when scaled and stuffed into the upper triangle form a matrix that is PSD. That means, in many cases the user will want to scale the input data and the solution, but that's not something SCS cares about, since it has found a point that satisfies the KKT conditions, as it agreed to. The example at the top of the page was passed in and SCS solved it, it's entirely a modeling issue whether or not that represents the SDP that the user wants solved. Scaling the data so that it corresponds to a real-world problem is no different that converting some atom into a convex cone representable problem. For example, we could say that the cone What you're really saying is that it would be nice if SCS handled the scaling. But it would also be nice if SCS automatically converted the cone |
Ok, if it makes sense the most sense for the SCS math/implementation for the PSD cone to be defined as |
Yeah, it is an odd definition, but unfortunately it's the only one that works in the space |
I ran into an issue with SDPs when trying to update cvxpy to interface with SCS 1.1.0. Either I don't understand the interface, or something is wrong in SCS.
Here's a script that returns the wrong answer:
The value of the last primal variable should be 2, but instead it's sqrt(2). Also, the values of
s
corresponding to the PSD constraint aren't PSD.The text was updated successfully, but these errors were encountered: