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

add syntax for more general set inclusion constraints #715

Closed
chriscoey opened this issue Mar 24, 2016 · 28 comments
Closed

add syntax for more general set inclusion constraints #715

chriscoey opened this issue Mar 24, 2016 · 28 comments
Milestone

Comments

@chriscoey
Copy link
Contributor

No description provided.

@chriscoey
Copy link
Contributor Author

na na na na na na na na POWER CONE!

@joehuchette
Copy link
Contributor

What would nice syntax for this look like?

@chriscoey
Copy link
Contributor Author

chriscoey commented Apr 14, 2016

Maybe we should sit down and discuss this in the broader context of conic modeling in JuMP.

@emreyamangil
Copy link
Contributor

+1

@mlubin
Copy link
Member

mlubin commented Mar 28, 2017

Possible syntax idea:

@constraint(m, A*x <= b, cone = XXX)

would constrain b - A*x to be in cone XXX. As in @SDconstraint, arguments would be vectors by default, no .<= needed.

@chriscoey
Copy link
Contributor Author

it's a little weird but i guess it lines up somewhat with the Ax \leq_{\mathcal{K}} b syntax that Boyd's group uses?

the thing here is that very often you would be writing something like (t,x) \in SOC or (x,y,z) \in Exp, or (1, b-Ax) \in SOC etc. that seems to me the most common way of using these cones

@chriscoey
Copy link
Contributor Author

as an example, let's use this little convex.jl model from pajarito tests

P = minimize(-3x - y,
    x >= 1,
    y >= -2,
    3x + 2y <= 30,
    exp(y^2) + x <= 7)

I guess in JuMP it would be nice (for now) to write:

@variable(m, x >= 1)
@variable(m, y >= -2)
@constraint(m, 3x+2y <= 30)
@variable(m, w)
@constraint(m, w + x <= 7)
@variable(m, u)
@constraint(m, (1, w, u) in :Exp)        # :Exp is (a,b,c): cl(b >= a*exp(c/a), a > 0)
@constraint(m, (1/2, u, y) in :Sqr)      # :Sqr is (a,b,c): cl(b >= a*(c/a)^2/2 = c^2/(2a), a > 0)

or to cut out w:

@variable(m, x >= 1)
@variable(m, y >= -2)
@constraint(m, 3x+2y <= 30)
@variable(m, u)
@constraint(m, (1, 7-x, u) in :Exp)   
@constraint(m, (1/2, u, y) in :Sqr)     

@chriscoey
Copy link
Contributor Author

also, those cones would be n-dimensional rather than 3-dimensional, and would just automatically detect the number of indices of the "argument" (in this case u or y).

however we also need to be able to parametrize some possible cones, like norm cones and product of power cones, and that may not work with the Symbol syntax eg :Norm(p)

@chriscoey
Copy link
Contributor Author

chriscoey commented Mar 29, 2017

Per discussion with @mlubin today, I suggest using a tuple of vectors. Parameters for parametrized cones should not go with the variables.

@constraint(m, (1, 7-x, u) in Exp())     # 7-x >= 1*exp(u/1)
@constraint(m, (1, u, y) in PowSum(2))     # u >= 1*(y/u)^2

Typically, for homogeneous functions, there will be a 2-tuple of epi/hypo-graph variable and argument vector (no perspective variable needed), eg: (t, x) in Norm(2), where x is a vector, or (a*t+b, C*x+d) in Geomean(), or (t, [x[i]*c[i] for i in my_set]) in Norm(). Cones can have default parameters, eg norm may have default 2. Some cones may be shorthand for others, eg Geomean() can mean the same as PowProd(ones(n)) where n is the length of the argument vector x.

For non-homogeneous functions, there may be a 3-tuple, as we want a perspective variable, eg: (p, q, x) in LogSumExp() is q >= p*log(sum(exp.(x./p))), or (p, q, x) in PowSum(alpha) is q >= p*sum((x./p).^alpha) etc. Exp cone naturally becomes n-dimensional.

For the PSD cone, in PSD() is shorthand for a slice of the lambda_min cone (which is concave homogeneous, so has a 2-tuple): X in PSD() iff (0, X) in LambdaMin() iff 0 <= lambda_min(X).

I would be interested to see a specific example of a cone that modelers would find useful that doesn't fit nicely into this abstraction.

@joehuchette
Copy link
Contributor

Why

@constraint(m, (t, x) in Norm(2))

instead of

@constraint(m, [t, x] in Norm(2))

? Or

@constraint(m, [t, x...] in Norm(2))

?

@chriscoey chriscoey changed the title add syntax for creating exponential cone constraints add syntax for more general conic constraints Mar 30, 2017
@chriscoey
Copy link
Contributor Author

chriscoey commented Mar 30, 2017

It's a good question and we should discuss it more. My reasoning for wanting a tuple in cone is that it can help prevent mistakes by the modeler.

Say for example the modeler is using an n+2 dimensional exponential cone (not homogeneous, is convex, so it has an epigraph, a perspective, and an n dimensional argument x). They should write:
@constraint(m, (p, q, x) in Exp())
where p (perspective) and q (epigraph) are variables, and x (argument) is an n dimensional vector of variables. This creates a n+2 dimensional exp cone. But what if the modeler forgot the perspective variable, or thought it wasn't needed. Easy mistake, given that it's not usually very useful in the modeling, and other cones like Norm(p) don't have one (homogeneous). Then they might write:
@constraint(m, (q, x) in Exp())
but because this is a tuple, we know that a mistake has been made after we parse the Exp(), because an exp cone has 3 pieces - epigraph, perspective, argument.

If we had used the syntax:
@constraint(m, [p, q, x] in Exp())
then sure it's probably still OK, but given that there will always be 3 elements in the vector, you may as well just use a tuple. But if we had used the syntax
@constraint(m, [p, q, x...] in Exp())
then if the modeler leaves off the p perspective by accident, there will be no error, as we will think they wanted an n+1 dimensional exp cone, and their epigraph will incorrectly become the perspective, and the first dimension of x will become the epigraph.

So I see it as both slightly more elegant to write, but more importantly, more resistant to errors by the modeler.

@mlubin
Copy link
Member

mlubin commented Mar 30, 2017

For SOC, however, you'd want a tuple with 2 elements. For extensibility, we wouldn't want JuMP's parsing of the constraint to depend on knowing anything about the particular cone, so I'm having trouble seeing how we can catch the error for the Exp cone, besides giving two scalar elements when the minimum possible dimension is 3.

@chriscoey
Copy link
Contributor Author

chriscoey commented Mar 30, 2017

For extensibility, we wouldn't want JuMP's parsing of the constraint to depend on knowing anything about the particular cone

This is not something I understand. I would like to learn why this is a problem and try to think of a way around it that preserves the mistake-detecting ability (and IMO, elegance) of the syntax above. We can talk offline if that's easier.

@chriscoey
Copy link
Contributor Author

Yes the dimension of the tuple depends on the cone. See what I was saying earlier about non-homogeneous (3) vs homogeneous (2) vs slices like PSD cone (1).

@chriscoey
Copy link
Contributor Author

Alternatively, maybe we don't want shortcuts - everything could be 3 dimensions. Perspectives of homogeneous functions could be dummy _. The PSD cone could always be written as (_,0,X) in LambdaMin(). This is temporary syntax there for the sake of allowing us to construct conic models, after all. It is not supposed to be as easy to use as Convex.jl.

@chriscoey
Copy link
Contributor Author

Actually unless someone can suggest a useful nonlinearity where that (perspective, epi/hypograph, argument) in cone syntax is insufficient, I am in favor of always using a 3-tuple.

@mlubin
Copy link
Member

mlubin commented Mar 30, 2017

I have little desire to discuss this further before my thesis defense is completed.

@chriscoey
Copy link
Contributor Author

If you go with the perspective + epi/hypo-graph + argument abstraction for cones, it may not be much more work to just directly parse functions into conic form.

@chriscoey
Copy link
Contributor Author

chriscoey commented Mar 30, 2017 via email

@blegat
Copy link
Member

blegat commented Mar 31, 2017

I really like the idea of having a more generic conic constraint syntax. In fact, I would like to be even more ambitious.
Namely, suppose we want to say that x is in the set S(param=1) we would have 3 equivalent syntax

@constraint m,  x >= 0, cone=:S, param=1
@constraint m, x >= 0, cone=S(param=1)
@constraint m, x in S(param=1)

While the two first ones only make sense if S is a cone, the last one also makes sense if S is a set.
In any case, JuMP would compute s = S(param=1) (in the first case it will distinguish between the argument he understands and the rest which it will give for the constructor of S).
Then it would call addconstraint(m, x, s).
The type of x could be anything. Tuple makes sense for the SOC cone, polynomial makes sense for the SOS cone, matrix makes sense for the SDP cone, and so on...
Any Julia package could define addconstraint(::JuMP.Model, ::..., ::CustomType) and that would enable an insanely convenient syntax for simple extension of JuMP.
This could be used in PolyJuMP to avoid to define a new macro @polyconstraint. In this case, param would be e.g. domain.
This could be used in Polyhedra where s is a polyhedron, or EntropicCone where s is an approximation of the entropic cone. In this case, in addconstraint, the package will simply build linear or sdp constraints under the hood.
I know this is ambitious but it has been some time I am thinking about it, I think it is worth it ! If I can think of 3 applications with only the packages I am working on, I am sure there are plenty more :)

@mlubin
Copy link
Member

mlubin commented Apr 3, 2017

Ok, the extension argument is convincing. Would it be sufficient for what you're thinking to support only affine expressions belonging to these sets?

@odow
Copy link
Member

odow commented Apr 3, 2017

Bonus points for unifying this with a new variable syntax ala https://github.com/JuliaOpt/JuMP.jl/issues/692#issuecomment-251718478]

@mlubin
Copy link
Member

mlubin commented Apr 3, 2017

Oh man

@blegat
Copy link
Member

blegat commented Apr 3, 2017

Affine Expression would already be very useful. Quadratic expression might also come handy for, e.g. modeling BMIs with PolyJuMP.

@chriscoey chriscoey changed the title add syntax for more general conic constraints add syntax for more general set inclusion constraints May 30, 2017
@chriscoey
Copy link
Contributor Author

I think we should resurrect this discussion as it may be relevant to JuliaOpt/MathProgBase.jl#164 and to jump-dev/PolyJuMP.jl#10

first of all, what should these "set objects" look like? will there be an extensible library of them? cones will be a subset, but should they get special treatment or not?

also, maybe, how should we think about primal-dual "set inclusion" problems? geometrically a dual on a set constraint might define a supporting hyperplane to the set. maybe this is a useful way to think that is more general than conic duality

@joehuchette
Copy link
Contributor

first of all, what should these "set objects" look like?

Why not just something like:

immutable SOC end
@constraint(model, x in SOC())

@mlubin
Copy link
Member

mlubin commented Nov 25, 2017

I consider this resolved now with MOI.

@mlubin mlubin closed this as completed Nov 25, 2017
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Development

No branches or pull requests

6 participants