Polyhedron in constraint representation (HPolyhedron)

HPolyhedron{N, VN<:AbstractVector{N}} <: AbstractPolyhedron{N}

Type that represents a convex polyhedron in constraint representation, that is, 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. The set $P$ may or may not be bounded (see also HPolytope, which assumes boundedness).

Fields

• constraints – vector of linear constraints

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{HPolyhedron}; [N]::Type{<:Real}=Float64, [dim]::Int=2,
     [rng]::AbstractRNG=GLOBAL_RNG, [seed]::Union{Int, Nothing}=nothing)

Algorithm

We first create a random polytope and then for each constraint randomly (50%) decide whether to include it.

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.