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

update atom documentation - state required cone types #574

Open
rileyjmurray opened this issue Sep 1, 2018 · 13 comments
Open

update atom documentation - state required cone types #574

rileyjmurray opened this issue Sep 1, 2018 · 13 comments

Comments

@rileyjmurray
Copy link
Collaborator

rileyjmurray commented Sep 1, 2018

Consider the following SOCP (per @wkschwartz)

import cvxpy as cv
u = cv.Variable(2)
constr = [u[1] - u[0] <= 100, u[1] - u[0] >= 0]
prob1 = cv.Problem(cv.Minimize(cv.norm(u)), constr)

Clearly, we could equivalently formulate the problem as a QP

import numpy as np
prob2 = cv.Problem(cv.Minimize(cv.quad_form(u, np.eye(2))), constr)

Right now if a user tries to call prob1.solve(solver='OSQP'), they will get a solver error.
This is okay from a correctness standpoint, since an SOCP and a QP are different mathematical objects from a duality perspective. Also users have the recourse to manually reformulate as in prob2 if they really want the QP-only solver.

However it would be very nice if cvxpy automatically performed the reduction from SOCP to QP when a user specifies a QP-only solver.

@ghost
Copy link

ghost commented Sep 2, 2018

this is a long standing issue, and quite likely the reason why cvxpy has a sum_squares atom. i believe it is correct as it stands. if the user writes the problem in SOCP form, then they should get as SOCP. if they don't understand the difference, then inferring something in their stance is a bad idea.

i vote for closing this.

@ghost ghost added invalid and removed enhancement labels Sep 2, 2018
@rileyjmurray
Copy link
Collaborator Author

I also said that it is correct as stands; that is why I used the "enhancement" label.

This may be a "long standing issue", but it's one that shouldn't be too hard to resolve in the context of cvxpy 1.0's reduction system.

@wkschwartz
Copy link

If cvxpy's goal is to make convex optimization more accessible, then this is a good enhancement. Taking the position that norm shouldn't work with a quadratic programming solver is likely confusing to newcomers because they would assume it's just solving min ||u||^2 underneath, as this is how least squares is taught to undergraduates. Reformulating with the sum_squares atom is one option, but quad_form might be a bit obscure to newcomers. New users would expect cvxpy to perform whatever transformations are "best", and not want to second guess which atoms to use.

@ghost
Copy link

ghost commented Sep 15, 2018

this is stupid. you are arguing to introduce a small bug (which is not an issue per se), but it is one, because cvxpy has gotten too complicated (cc. @SteveDiamond). development effort should be spent where it matters.

for example, the cvxpy to solver interface has become a mess. (where the fuck have the dims dictionaries gone?) i fear i know the reason why, and i'm partially responsible for it (i wrote the first interface to mosec). at a minimum, you should put out (in another package) all the commercial software interfaces and let their salesmen maintain them. you should focus on keep things simple and modular!..

@SteveDiamond
Copy link
Collaborator

cvxpy has gotten complicated, it's true. It's more modular than it appears, but probably less accessible than before. The solver interfaces are more ad hoc now. Having one way of representing solver information wasn't working. I don't work personally on the commercial solver interfaces. Those are contributed by others, which is working fine for now. It would be well worth cleaning out all the legacy solver interfaces so the approach is clearer.

In terms of this issue, if we were to add SOCP to QP conversion I would not do it in an ad hoc way such as by catching norm2, converting it to sum_squares, but catching all possible cases. People in Boyd's group have looked at this and it's somewhat involved. I guess we can keep this issue open, but it's not something I see getting into cvxpy any time soon.

@ghost
Copy link

ghost commented Sep 16, 2018

thanks @SteveDiamond . i fear we can not succumb to complexity though. cvxpy 1.0 was meant as a notation cleanup (all the little .size and .shape), with the major addition of a branch in the conic canonicalizer that could catch quadratic forms, to support our shiny new QP open source solver, osqp. all the commercal crap should never have entered design choices.

to compile to QP form, me (and @moehle , and @takapoui ) had identified the changes necessary to @jaehyunp 's LS compiler. it was a couple of hundred of lines of changes. (i never understood that weird cs-theoretical thing you put in the paper, although i believe the thing uses my code stub).

so, why don't we just branch cvxpy 0.4 and make a cvxpy 2.0? without all that giant crapload of c++ (shouldn't that have gone to code garbage a few years ago), without support for imagenary numbers (i thought we had got over those), and without caring a gram of shit about the stupid commerical solvers!!!!

(btw, @rileyjmurray comment in another thread is right. we should use cython to speed up canonicalization, not c++!)

@rileyjmurray
Copy link
Collaborator Author

@enzobusseti the C++ code present in cvxpy 1.0 was already present in cvxpy 0.4, just under a different name (cvxcanon instead of cvxcore). The long-term plan is to remove the dependence on cvxcore and make a different high-speed backend designed only with cvxpy in mind. However for now, it is simply not possible to "branch cvxpy 0.4 and make cvxpy 2.0 without C++".

On a second note- It's not clear to me how or where commercial solvers entered the design process for cvxpy 1.0. Certainly cvxpy 1.0 was not written in a way that made it easy for me to write the 1.0 MOSEK interface, and the CPLEX interface is currently a 1.0 wrapper around an old 0.4-style interface. It is true that cvxpy 1.0 is written with a less-specific canonical form in mind (relative to 0.4), but that generality has nothing to do with any one solver. YALMIP similarly has flexible problem representations and supports a huge range of commercial and open-source solvers.

@rileyjmurray
Copy link
Collaborator Author

rileyjmurray commented Sep 17, 2018

All the above said, I have done more thinking about SOCP to QP conversion and I realize now where the problem lies.

Here's one way to look at it: It can be shown that supporting the second-order cone is equivalent to supporting constraints of the form y.T * Q * y <= 0 where Q is a fixed matrix with at most one negative eigenvalue. QP solvers support constraints like x.T * A * x + 2 * b.T * x + c <= 0, for PSD A. This can be written in block-form as [[x], [1]].T * [ [A, b], [b.T, c] ] * [ [x], [1] ] <= 0. The block matrix [[A, b], [b.T, c]] indeed has at most one negative eigenvalue, but the block vector [[x], [1]] necessarily has the final entry fixed to 1. There isn't a way for a QP-only solver to allow that 1 in the block vector to take on the range of values needed for an SOCP.

Here is another way to look at it: start with the scalar function x ** 2. The sub-level sets of the perspective of this function are { (x,y,z) : x ** 2 <= y * z, y >= 0 }. This set is precisely the "rotated second order cone" in R^3. We cannot expect a QP solver to accommodate perspective functions of x ** 2, any more than we can expect a solver supporting log(x) to accommodate the relative entropy function (which is essentially the perspective of the negative logarithm).

This is all to say: an SOCP with nontrivial linear term (a-la || A * x || + b.T * x + c <= 0 with b != 0) cannot be modeled solely in terms of linear (in)equalities, and sublevel sets of PSD quadratic forms. And as a result, SOCPs with nontrivial linear terms cannot be parsed into equivalent problems for QP-only solvers.

In view of these fundamental obstacles, I am now open to closing this issue.

  • It would make sense to re-open the issue if there was a "QP" solver that supported constraints of the form y.T * Q * y <= 0 when Q has at most one negative eigenvalue, but until someone writes such a solver, there is nothing to be done on cvxpy's end.
  • For now, it simply might make sense to update the documentation for OSQP with cvxpy, to make sure that people use the sum_squares atom instead of norm when working with OSQP. (I think this is worth doing, since users might otherwise fall back on quad_form, which is far less efficient than sum_squares).

@bstellato
Copy link
Contributor

@rileyjmurray I agree with the last point. Also, an easy solution could be to write a more descriptive error when the user tries to solve with OSQP a problem with norm(u) in the objective mentioning that it could be rewritten with sum_squares.

@ghost
Copy link

ghost commented Sep 19, 2018

@rileyjmurray you're right, it's more complicated than it first looks. we had figured out that the QP-representable problems have inequality constraints involving quadratic-of-piecewise-affine functions. (let me know if you want to write a paper about it.)
and @SteveDiamond, i'm sorry, didn't mean to say anything bad about cvxpy or its leadership. i know you guys are doing the best job (given the limited resources). cvxpy is amazing software. (also i have nothing against the people that develop proprietary solvers.) I wasn't being serious.

@rileyjmurray
Copy link
Collaborator Author

rileyjmurray commented Oct 1, 2018

I'm reworking the documentation a bit. Rather than saying "use quad_form when working with OSQP" (which is very specific and didn't really have a natural place to mention), I added a column on the Atomic Functions table indicating the solver capabilities needed for the constraint. See here for the updated page.

For example, log_det clearly states that the domain is PSD matrices, but it omits the fact that the solver also needs the exponential cone. In other cases, the Frobenius norm of a matrix is SOCP-representable, while the nuclear norm requires an SDP. The issue discussed in this thread is resolved by marking the vector-norm as an SOCP representable atom, and sum_squares as an SOCP or QP representable atom.

I did use the facts that (1) all LPs are compatible with SOCP, QP, and EXP solvers, and (2) all SOCPs are compatible with SDP solvers.

@wkschwartz
Copy link

The new column in the documentation helps a lot I think. Might also be good for newcomers to see at the top of the table your facts (1) and (2), possibly in the form of containment: LP <= QP <= SOCP etc

@rileyjmurray rileyjmurray changed the title add reduction transforming SOCPs to QPs update atom documentation - state required cone types Oct 4, 2018
@SteveDiamond
Copy link
Collaborator

@rileyjmurray I missed your update to the atoms table. This makes a lot of sense, and is similar to the Convex.jl documentation. I guess I left it out before because we only had cone programs, and I didn't think users would understand.

@enzobusseti thanks for clarifying. cvxpy can always be improved, substantially in some ways, but I don't have the time and energy that I used to have for such large alterations.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
Status: No status
Development

No branches or pull requests

4 participants