Polyhedron in constraint representation (HPolyhedron)

LazySets.HPolyhedronModule.HPolyhedronType
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
source

Conversion

Base.convertMethod
convert(::Type{HPolyhedron}, X::LazySet)

Convert a polyhedral set to a polyhedron in constraint representation.

Input

  • HPolyhedron – target type
  • X – polyhedral set

Output

The given set represented as a polyhedron in constraint representation.

Algorithm

This method uses constraints_list.

source
Base.convertMethod
 convert(::Type{HPolyhedron}, P::HRep)

Convert an HRep polyhedron from Polyhedra.jl to a polyhedron in constraint representation .

Input

  • HPolyhedron – target type
  • PHRep polyhedron

Output

An HPolyhedron.

source

Operations

The following methods are shared between HPolytope and HPolyhedron.

LazySets.API.constraints_listMethod
constraints_list(P::HPoly)

Return the list of constraints defining a polyhedron in constraint representation.

Input

  • P – polyhedron in constraint representation

Output

The list of constraints of the polyhedron.

source
LazySets.API.dimMethod
dim(P::HPoly)

Return the dimension of a polyhedron in constraint representation.

Input

  • P – polyhedron in constraint representation

Output

The ambient dimension of the polyhedron in constraint representation. If it has no constraints, the result is $-1$.

source
LinearAlgebra.normalizeMethod
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.

source
LazySets.remove_redundant_constraintsMethod
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.

source
LazySets.remove_redundant_constraints!Method
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.

source
LazySets.tohrepMethod
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.

source
LazySets.tovrepMethod
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.

source
LazySets.addconstraint!Method
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.

source
LazySets.API.ρMethod
ρ(d::AbstractVector{M}, P::HPoly{N};
  solver=default_lp_solver(M, N)) where {M, N}

Evaluate the support function of a polyhedron in constraint representation in a given direction.

Input

  • d – direction
  • P – polyhedron in constraint representation
  • solver – (optional, default: default_lp_solver(M, N)) the backend used to solve the linear program

Output

The evaluation of the support function for the polyhedron. If a polytope is unbounded in the given direction, we throw an error. If a polyhedron is unbounded in the given direction, the result is Inf.

source
LazySets.API.σMethod
σ(d::AbstractVector{M}, P::HPoly{N};
  solver=default_lp_solver(M, N) where {M, N}

Return a support vector of a polyhedron in constraint representation in a given direction.

Input

  • d – direction
  • P – polyhedron in constraint representation
  • solver – (optional, default: default_lp_solver(M, N)) the backend used to solve the linear program

Output

The support vector in the given direction. If a polytope is unbounded in the given direction, we throw an error. If a polyhedron is unbounded in the given direction, the result contains ±Inf entries.

source
LazySets.API.translateMethod
translate(P::HPoly, v::AbstractVector; [share]::Bool=false)

Translate (i.e., shift) a polyhedron in constraint representation by a given vector.

Input

  • P – polyhedron in constraint representation
  • v – translation vector
  • share – (optional, default: false) flag for sharing unmodified parts of the original set representation

Output

A translated polyhedron in constraint representation.

Notes

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

Algorithm

We translate every constraint.

source

The following methods are specific to HPolyhedron.

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

Create a random polyhedron.

Input

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

Output

A random polyhedron.

Algorithm

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

source

Inherited from LazySet:

Inherited from AbstractPolyhedron: