Function for checking boundedness

[schillic]

Add a function that checks if an HPolytope (and an AbstractHPolygon) is bounded.

An efficient but only necessary check is to look at the number of constraints. In n dimensions you need at least n+1 constraints.

A naive approach could be to ask for the support vector in the positive and negative unit directions.

[schillic]

We should add this function for all set types. Usually this will be a constant function (e.g., return false for HalfSpace and return true for Ball1).

[tomerarnon]

Has there been news on this by any chance? I could definitely still use such a function. No pressure 😉

In reference to the point about n+1 constraints, this is the minimum number of constraints, no? So seeing any number less than n+1 tells you the polytope is unbounded, but any number higher doesn't tell you anything.

[schillic]

this is the minimum number of constraints, no?

Yes, this is only a necessary and very weak (but also very efficient-to-check) condition.

Now that I think about it, I am wondering if we should allow this check to be performed for HPolytope (and HPolygon) at all because our running assumption is that they are bounded. It is somehow inconsistent if the answer false can be given.
We should definitely have this check for HPolyhedron. The way to use it then would be to perform this check with HPolyhedron (which has the same input as HPolytope) and if the answer is true you can create an HPolytope from the constraints. Would that be acceptable for you?
We could add a convenience function that performs these steps, given a list of constraints. I cannot think of a good name, though 😄

If you are not interested in efficiency, I can add the naive approach mentioned above (2n LP checks, where n is the dimension) in the next week. There might actually be no fundamentally better way (a quick internet search gave no result).

[tomerarnon]

Perhaps the boundedness function should be written for a vector of constraints rather than a set type, as you suggest. That way, it could both be used on HPolyhedron, and in a validation function like the one mentioned in #759.

If you are not interested in efficiency, I can add the naive approach mentioned above (2n LP checks, where n is the dimension) in the next week. There might actually be no fundamentally better way (a quick internet search gave no result).

Well, one is always interested in efficiency... but if there's no other way, then so be it!

As for naming, how about simply isbounded()?

Also, since we are using the word bounded so much, I couldn't help but think about this in the context of bounds checking. Now it occurs to me that perhaps you can have the best of both worlds: be able to check boundedness without sacrificing performance where boundedness should be assumed. You could write the check in to "risky" areas, decorating calls like: @boundscheck isbounded(P) ... and bypass the check with @inbounds if you know it to be true. This only just occurred to me, so I haven't yet thought of the ramifications, but I thought I would share anyway.

[schillic]

Perhaps the boundedness function should be written for a vector of constraints

👍

Well, one is always interested in efficiency... but if there's no other way, then so be it!

I simply do not know 😃
I anyway think that polyhedral computations in high dimensions are doomed to be not-so-efficient. Depends on what you are used to, I guess.

As for naming, how about simply isbounded()?

My question was about the convenience function (which takes a list of constraints and gives you the appropriate set type).

@boundscheck isbounded(P)

Hm, I would not hijack the existing macro because it serves a different purpose, but interesting idea!

[tomerarnon]

My question was about the convenience function (which takes a list of constraints and gives you the appropriate set type).

Ah I see, sorry. Rereading your previous comment, I'm not sure such a function is strictly necessary, especially since it is inherently type unstable. That said, the functionality could become part of a general polytope function like the one proposed in #875

[mforets]

In #956 @schillic added the isbounded function 🎉

We should note that isbounded(::HPolytope) returns true, since this is a running assumption on the type, while isbounded(::HPolyhedron) performs the necessary checks.

There is not yet the option to check that a new instance of HPolytope is indeed bounded; i think that it should (but for efficiency reasons one should be able to turn it off if needed). I've opened #964 for that purpose.

If one is not sure that the polyhedra being used are bounded, there are some alternatives:

• use HPolyhedron from the construction
• apply isbounded(HPolyhedron(P.constraints)), simplified with Check if polytope is bounded on construction #964 with a new kwarg check_boundedness on the constructor

[tomerarnon]

🎉🎉
Thanks a bunch for adding this! Just checked out the master branch to see it in action!
Having this for HPolyhedron makes my life a lot easier! 😄

A check_boundedness option would also be great, since at the moment isbounded(HPolytope()) == true, but I can certainly live with that for now.

[schillic]

A check_boundedness option would also be great

This option came in #978 (isbounded(P, false)).
(Note that the new constructor argument check_boundedness throws an error if validation fails, which may not be what you want.)

[mforets]

Examples in the construction:

julia> HPolytope()
HPolytope{Float64}(HalfSpace{Float64}[])

julia> HPolytope(Array{HalfSpace{Float64},1}(), check_boundedness=true)
ERROR: AssertionError: the polytope is not bounded
Stacktrace:
 [1] #call#40 at /Users/forets/.julia/dev/LazySets/src/HPolytope.jl:31 [inlined]
 [2] Type at ./none:0 [inlined]
 [3] #HPolytope#42 at /Users/forets/.julia/dev/LazySets/src/HPolytope.jl:39 [inlined]
 [4] (::getfield(Core, Symbol("#kw#Type")))(::NamedTuple{(:check_boundedness,),Tuple{Bool}}, ::Type{HPolytope}, ::Array{HalfSpace{Float64},1}) at ./none:0
 [5] top-level scope at none:0

Perhaps we could improve the error message suggesting to construct an HPolyhedron.

Example after construction:

julia> isbounded(HPolytope())
true

julia> isbounded(HPolytope(), false) # use kwarg use_type_assumption 
false