Polyhedron in constraint representation (HPolyhedron)

LazySets.HPolyhedronType
HPolyhedron{N, VN<:AbstractVector{N}} <: AbstractPolyhedron{N}

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

Fields

  • constraints – vector of linear constraints
source

The following methods are shared between HPolytope and HPolyhedron.

LazySets.dimMethod
dim(P::HPoly)

Return the dimension of a polyhedron in H-representation.

Input

  • P – polyhedron in H-representation

Output

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

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

Evaluate the support function of a polyhedron (in H-representation) in a given direction.

Input

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

Output

The support function of 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.σMethod
σ(d::AbstractVector{M}, P::HPoly{N};
  solver=default_lp_solver(M, N) where {M, N}

Return the support vector of a polyhedron (in H-representation) in a given direction.

Input

  • d – direction
  • P – polyhedron in H-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.

source
LazySets.addconstraint!Method
addconstraint!(P::HPoly, constraint::LinearConstraint)

Add a linear constraint to a polyhedron in H-representation.

Input

  • P – polyhedron in H-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.constraints_listMethod
constraints_list(P::HPoly)

Return the list of constraints defining a polyhedron in H-representation.

Input

  • P – polyhedron in H-representation

Output

The list of constraints of the polyhedron.

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 polyhedron in H-representation to a polytope in V-representation.

Input

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

Output

The VPolytope which is the vertex representation of the given polyhedron 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
LinearAlgebra.normalizeMethod
normalize(P::HPoly{N}, p=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
Base.isemptyMethod
isempty(P::HPoly{N}, witness::Bool=false;
        [use_polyhedra_interface]::Bool=false, [solver]=nothing,
        [backend]=nothing) where {N}

Determine whether a polyhedron is empty.

Input

  • P – polyhedron
  • witness – (optional, default: false) compute a witness if activated
  • use_polyhedra_interface – (optional, default: false) if true, we use the Polyhedra interface for the emptiness test
  • solver – (optional, default: nothing) LP-solver backend, uses default_lp_solver(N) if it is not provided
  • backend – (optional, default: nothing) backend for polyhedral computations in Polyhedra, uses default_polyhedra_backend(P) if it is not provided

Output

  • If witness option is deactivated: true iff $P = ∅$
  • If witness option is activated:
    • (true, []) iff $P = ∅$
    • (false, v) iff $P ≠ ∅$ and $v ∈ P$

Notes

The default value of the backend is set internally and depends on whether the use_polyhedra_interface option is set or not. If the option is set, we use default_polyhedra_backend(P).

Witness production is not supported if use_polyhedra_interface is true.

Algorithm

The algorithm sets up a feasibility LP for the constraints of P. If use_polyhedra_interface is true, we call Polyhedra.isempty. Otherwise, we set up the LP internally.

source
LazySets.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
Polyhedra.polyhedronMethod
polyhedron(P::HPoly; [backend]=default_polyhedra_backend(P))

Return an HRep polyhedron from Polyhedra.jl given a polytope in H-representation.

Input

  • P – polytope
  • backend – (optional, default: call default_polyhedra_backend(P)) the polyhedral computations backend

Output

An HRep polyhedron.

Notes

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

source
LazySets.remove_redundant_constraintsMethod
remove_redundant_constraints(P::HPoly{N};
                             backend=nothing) where {N}

Remove the redundant constraints in a polyhedron in H-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 in a polyhedron in H-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._isbounded_stiemkeMethod
_isbounded_stiemke(P::HPolyhedron{N}; solver=LazySets.default_lp_solver(N),
                   check_nonempty::Bool=true) where {N}

Determine whether a polyhedron is bounded using Stiemke's theorem of alternatives.

Input

  • P – polyhedron
  • backend – (optional, default: default_lp_solver(N)) the backend used to solve the linear program
  • check_nonempty – (optional, default: true) if true, check the precondition to this algorithm that P is non-empty

Output

true iff the polyhedron is bounded

Notes

The algorithm internally calls isempty to check whether the polyhedron is empty. This computation can be avoided using the check_nonempty flag.

Algorithm

The algorithm is based on Stiemke's theorem of alternatives, see e.g. [1].

Let the polyhedron $P$ be given in constraint form $Ax ≤ b$. We assume that the polyhedron is not empty.

Proposition 1. If $\ker(A)≠\{0\}$, then $P$ is unbounded.

Proposition 2. Assume that $ker(A)={0}$ and $P$ is non-empty. Then $P$ is bounded if and only if the following linear program admits a feasible solution: $\min∥y∥_1$ subject to $A^Ty=0$ and $y≥1$.

[1] Mangasarian, Olvi L. Nonlinear programming. Society for Industrial and Applied Mathematics, 1994.

source

Inherited from ConvexSet:

Inherited from AbstractPolyhedron:

  • [constrained_dimensions](@ref constrained_dimensions(::AbstractPolyhedron)
  • linear_map

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 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 polyhedron.

Algorithm

We first create a random polytope and then randomly remove some of the constraints.

source
LazySets.isboundedMethod
isbounded(S::ConvexSet)

Determine whether a set is bounded.

Input

  • S – set
  • algorithm – (optional, default: "support_function") algorithm choice, possible options are "support_function" and "stiemke"

Output

true iff the set is bounded.

Algorithm

See the documentation of _isbounded_unit_dimensions or _isbounded_stiemke for details.

source
isbounded(P::AbstractPolyhedron{N}; [solver]=default_lp_solver(N)) where {N}

Determine whether a polyhedron is bounded.

Input

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

Output

true iff the polyhedron is bounded

Algorithm

We first check if the polyhedron has more than max(dim(P), 1) constraints, which is a necessary condition for boundedness.

If so, we check boundedness via _isbounded_stiemke.

source
isbounded(r::Rectification{N}) where {N}

Determine whether a rectification is bounded.

Input

  • r – rectification

Output

true iff the rectification is bounded.

Algorithm

Let $X$ be the set wrapped by rectification $r$. We first check whether $X$ is bounded (because then $r$ is bounded). Otherwise, we check unboundedness of $X$ in direction $(1, 1, …, 1)$, which is sufficient for unboundedness of $r$; this step is not necessary but rather a heuristics. Otherwise, we check boundedness of $X$ in every positive unit direction, which is sufficient and necessary for boundedness of $r$.

source

Inherited from AbstractPolyhedron: