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 = \bigcap_{i = 1}^m H_i,\]

where each $H_i = \{x \in \mathbb{R}^n : a_i^T x \leq b_i \}$ is a half-space, $a_i \in \mathbb{R}^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 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

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

Create a random polytope in constraint representation.

Input

• HPolytope – type for dispatch
• 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
• num_vertices – (optional, default: -1) upper bound on the number of vertices of the polytope (see comment below)

Output

A random polytope in constraint representation.

Algorithm

We create a random polytope in vertex representation and convert it to constraint representation (hence 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 two-dimensional, the polytope is converted to a polygon in constraint representation and then its vertices_list implementation is used. This ensures that, by default, the optimized two-dimensional methods are used.

It is possible to use the Polyhedra backend in two-dimensions 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.

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.