Polytope in constraint representation (HPolytope)

HPolytope{N, VN<:AbstractVector{N}} <: AbstractPolytope{N}

Type that represents a convex polytope in constraint representation, i.e., a bounded set characterized by a finite intersection of half-spaces,

\[P = ⋂_{i = 1}^m H_i,\]

where each $H_i = \{x ∈ ℝ^n : a_i^T x ≤ b_i \}$ is a half-space, $a_i ∈ ℝ^n$ is the normal vector of the $i$-th half-space and $b_i$ is the displacement. It is assumed that $P$ is bounded (see also LazySets.HPolyhedron, which does not make such an assumption).

Fields

• constraints – vector of linear constraints
• check_boundedness – (optional, default: false) flag for checking if the constraints make the polytope bounded; (boundedness is a running assumption for this type)

Notes

A polytope is a bounded polyhedron.

Boundedness is a running assumption for this type. For performance reasons, boundedness is not checked in the constructor by default. We also exploit this assumption, so a boundedness check may not return the answer you would expect.

julia> P = HPolytope([HalfSpace([1.0], 1.0)]);  # x <= 1

julia> isbounded(P)  # uses the type assumption and does not actually check
true

julia> isbounded(P, false)  # performs a real boundedness check
false

isbounded(P::HPolytope, [use_type_assumption]::Bool=true)

Determine whether a polytope in constraint representation is bounded.

Input

• P – polytope in constraint representation
• use_type_assumption – (optional, default: true) flag for ignoring the type assumption that polytopes are bounded

Output

true if use_type_assumption is activated. Otherwise, true iff P is bounded.

rand(T::Type{<:LazySet}; [N]::Type{<:Real}=Float64, [dim]::Int=2,
     [rng]::AbstractRNG=GLOBAL_RNG, [seed]::Union{Int, Nothing}=nothing
    )

Create a random set of the given set type.

Input

• T – set type
• N – (optional, default: Float64) numeric type
• dim – (optional, default: 2) dimension
• rng – (optional, default: GLOBAL_RNG) random number generator
• seed – (optional, default: nothing) seed for reseeding

Output

A random set of the given set type.

Extended help

rand(::Type{HPolytope}; [N]::Type{<:Real}=Float64, [dim]::Int=2,
     [rng]::AbstractRNG=GLOBAL_RNG, [seed]::Union{Int, Nothing}=nothing)

Input

• num_vertices – (optional, default: -1) upper bound on the number of vertices of the polytope (see comment below)

Algorithm

If num_vertices == 0, we create a fixed infeasible polytope (corresponding to the EmptySet).

If num_vertices == 1, we create a random Singleton and convert it.

If dim == 1, we create a random Interval and convert it.

If dim == 2, we create a random VPolygon and convert it.

Otherwise, we create a random VPolytope and convert it (hence also the argument num_vertices). See rand(::Type{VPolytope}).

vertices_list(P::HPolytope; [backend]=nothing, [prune]::Bool=true)

Return a list of the vertices of a polytope in constraint representation.

Input

• P – polytope in constraint representation
• backend – (optional, default: nothing) the backend for polyhedral computations
• prune – (optional, default: true) flag to remove redundant vertices

Output

A list of the vertices.

Algorithm

If the polytope is one-dimensional (resp. two-dimensional), it is converted to an interval (resp. polygon in constraint representation) and then the respective optimized vertices_list implementation is used.

It is possible to use the Polyhedra backend in the one- and two-dimensional case as well by passing a backend.

If the polytope is not two-dimensional, the concrete polyhedra-manipulation library Polyhedra is used. The actual computation is performed by a given backend; for the default backend used in LazySets see default_polyhedra_backend(P). For further information on the supported backends see Polyhedra's documentation.

dim(X::LazySet)

Compute the ambient dimension of a set.

Input

• X – set

Output

The ambient dimension of the set.

Extended help

dim(P::HPoly)

Output

If P has no constraints, the result is $-1$.

normalize(P::HPoly{N}, p::Real=N(2)) where {N}

Normalize a polyhedron in constraint representation.

Input

• P – polyhedron in constraint representation
• p – (optional, default: 2) norm

Output

A new polyhedron in constraint representation whose normal directions $a_i$ are normalized, i.e., such that $‖a_i‖_p = 1$ holds.

remove_redundant_constraints(P::HPoly{N}; [backend]=nothing) where {N}

Remove the redundant constraints in a polyhedron in constraint representation.

Input

• P – polyhedron
• backend – (optional, default: nothing) the backend used to solve the linear program

Output

A polyhedron equivalent to P but with no redundant constraints, or an empty set if P is detected to be empty, which may happen if the constraints are infeasible.

Notes

If backend is nothing, it defaults to default_lp_solver(N).

Algorithm

See remove_redundant_constraints!(::AbstractVector{<:HalfSpace}) for details.

remove_redundant_constraints!(P::HPoly{N}; [backend]=nothing) where {N}

Remove the redundant constraints of a polyhedron in constraint representation; the polyhedron is updated in-place.

Input

• P – polyhedron
• backend – (optional, default: nothing) the backend used to solve the linear program

Output

true if the method was successful and the polyhedron P is modified by removing its redundant constraints, and false if P is detected to be empty, which may happen if the constraints are infeasible.

Notes

If backend is nothing, it defaults to default_lp_solver(N).

Algorithm

See remove_redundant_constraints!(::AbstractVector{<:HalfSpace}) for details.

tohrep(P::HPoly)

Return a constraint representation of the given polyhedron in constraint representation (no-op).

Input

• P – polyhedron in constraint representation

Output

The same polyhedron instance.

tovrep(P::HPoly; [backend]=default_polyhedra_backend(P))

Transform a polytope in constraint representation to a polytope in vertex representation.

Input

• P – polytope in constraint representation
• backend – (optional, default: default_polyhedra_backend(P)) the backend for polyhedral computations

Output

A VPolytope which is a vertex representation of the given polytope in constraint representation.

Notes

The conversion may not preserve the numeric type (e.g., with N == Float32) depending on the backend. For further information on the supported backends see Polyhedra's documentation.

addconstraint!(P::HPoly, constraint::HalfSpace)

Add a linear constraint to a polyhedron in constraint representation.

Input

• P – polyhedron in constraint representation
• constraint – linear constraint to add

Notes

It is left to the user to guarantee that the dimension of all linear constraints is the same.

ρ(d::AbstractVector, X::LazySet)

Evaluate the support function of a set in a given direction.

Input

• d – direction
• X – set

Output

The evaluation of the support function of X in direction d.

Notes

A convenience alias support_function is also available.

We have the following identity based on the support vector $σ$:

\[ ρ(d, X) = d ⋅ σ(d, X)\]

Extended help

ρ(d::AbstractVector{M}, P::HPoly{N};
  solver=default_lp_solver(M, N)) where {M, N}

Input

• solver – (optional, default: default_lp_solver(M, N)) the backend used to solve the linear program

Output

If P is unbounded in the given direction, there are two cases:

• If P is an HPolytope, we throw an error.
• If P is an HPolyedron, the result is Inf.

σ(d::AbstractVector, X::LazySet)

Compute a support vector of a set in a given direction.

Input

• d – direction
• X – set

Output

A support vector of X in direction d.

Notes

A convenience alias support_vector is also available.

Extended help

σ(d::AbstractVector{M}, P::HPoly{N};
  solver=default_lp_solver(M, N) where {M, N}

Input

• solver – (optional, default: default_lp_solver(M, N)) the backend used to solve the linear program

Output

If P is unbounded in the given direction, there are two cases:

• If P is an HPolytope, we throw an error.
• If P is an HPolyedron, the result contains ±Inf entries.

translate(X::LazySet, v::AbstractVector)

Compute the translation of a set with a vector.

Input

• X – set
• v – vector

Output

A set representing $X + \{v\}$.

Extended help

translate(P::HPoly, v::AbstractVector; [share]::Bool=false)

Input

• share – (optional, default: false) flag for sharing unmodified parts of the original set representation

Notes

The normal vectors of the constraints (vector a in a⋅x ≤ b) are shared with the original constraints if share == true.

convex_hull(P1::HPoly, P2::HPoly;
           [backend]=default_polyhedra_backend(P1))

Compute the convex hull of the set union of two polyhedra in constraint representation.

Input

• P1 – polyhedron
• P2 – polyhedron
• backend – (optional, default: default_polyhedra_backend(P1)) the backend for polyhedral computations

Output

The HPolyhedron (resp. HPolytope) obtained by the concrete convex hull of P1 and P2.

Notes

For performance reasons, it is suggested to use the CDDLib.Library() backend for the convex_hull.

For further information on the supported backends see Polyhedra's documentation.