Polyhedron in constraint representation (HPolyhedron)

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

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

ρ(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.

σ(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.

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.

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.

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

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.

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.

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.

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.

remove_redundant_constraints(constraints::AbstractVector{<:LinearConstraint{N}};
                             backend=default_lp_solver(N)) where {N}

Remove the redundant constraints of a given list of linear constraints.

Input

• constraints – list of constraints
• backend – (optional, default: default_lp_solver(N)) the backend used to solve the linear program

Output

The list of constraints with the redundant ones removed, or an empty set if the constraints are infeasible.

Algorithm

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

remove_redundant_constraints(P::HPoly{N};
                             backend=default_lp_solver(N)) where {N}

Remove the redundant constraints in a polyhedron in H-representation.

Input

• P – polyhedron
• backend – (optional, default: default_lp_solver(N)) 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.

Algorithm

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

remove_redundant_constraints!(constraints::AbstractVector{<:LinearConstraint{N}};
                              backend=default_lp_solver(N)) where {N}

Remove the redundant constraints of a given list of linear constraints; the list is updated in-place.

Input

• constraints – list of constraints
• backend – (optional, default: default_lp_solver(N)) the backend used to solve the linear program

Output

true if the function was successful and the list of constraints constraints is modified by removing the redundant constraints, and false only if the constraints are infeasible.

Notes

Note that the result may be true even if the constraints are infeasible. For example, $x ≤ 0 && x ≥ 1$ will return true without removing any constraint. To check if the constraints are infeasible, use isempty(HPolyhedron(constraints)).

Algorithm

If there are m constraints in n dimensions, this function checks one by one if each of the m constraints is implied by the remaining ones.

To check if the k-th constraint is redundant, an LP is formulated using the constraints that have not yet being removed. If, at an intermediate step, it is detected that a subgroup of the constraints is infeasible, this function returns false. If the calculation finished successfully, this function returns true.

For details, see Fukuda's Polyhedra FAQ.

remove_redundant_constraints!(P::HPoly{N};
                              backend=default_lp_solver(N)) where {N}

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

Input

• P – polyhedron
• backend – (optional, default: default_lp_solver(N)) 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.

Algorithm

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

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

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.

isbounded(S::LazySet)

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.

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.

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