Polyhedron in constraint representation (HPolyhedron)

LazySets.HPolyhedron — Type.

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

Type that represents a convex polyhedron in H-representation.

Fields

constraints – vector of linear constraints

source

The following methods are shared between HPolytope and HPolyhedron.

LazySets.dim — Method.

dim(P::HPoly{N}) where {N<:Real}

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{N}, P::HPoly{N};
  solver=default_lp_solver(N)) where {N<:Real}

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(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{N}, P::HPoly{N}; solver=default_lp_solver(N)
 ) where {N<:Real}

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(N)) the backend used to solve the linear program

Output

The support vector in the given direction.

source

LazySets.addconstraint! — Method.

addconstraint!(P::HPoly{N}, constraint::LinearConstraint{N}) where {N<:Real}

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_list — Method.

constraints_list(P::HPoly{N}) where {N<:Real}

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.tohrep — Method.

tohrep(P::HPoly{N}) where {N<:Real}

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.tovrep — Method.

tovrep(P::HPoly{N};
      [backend]=default_polyhedra_backend(P, N)) where {N<:Real}

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, N)) 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.normalize — Method.

normalize(P::HPoly{N}, p=N(2)) where {N<:Real}

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.isempty — Method.

isempty(P::HPoly{N}, witness::Bool=false; [usepolyhedrainterface]::Bool=false, [solver]=defaultlpsolver(N), [backend]=nothing) where {N<:Real}

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: default_lp_solver(N)) LP-solver backend
backend – (optional, default: nothing) backend for polyhedral computations in Polyhedra; its value is set internally (see the Notes below for details)

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, N).

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.translate — Method.

translate(P::HPoly{N}, v::AbstractVector{N}; share::Bool=false
         ) where {N<:Real}

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

polyhedron(P::HPoly{N};
           [backend]=default_polyhedra_backend(P, N)) where {N<:Real}

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

Input

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

Output

An HRep polyhedron.

Notes

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

source

LazySets.remove_redundant_constraints — Method.

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

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.

source

LazySets.remove_redundant_constraints! — Method.

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

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.

source

Inherited from LazySet:

Inherited from AbstractPolyhedron:

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

The following methods are specific to HPolyhedron.

Base.rand — Method.

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.isbounded — Method.

isbounded(P::HPolyhedron)

Determine whether a polyhedron in constraint representation is bounded.

Input

P – polyhedron in constraint representation

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

source

LazySets.vertices_list — Method.

vertices_list(P::HPolyhedron{N}) where {N<:Real}

Return the list of vertices of a polyhedron in constraint representation.

Input

P – polyhedron in constraint representation

Output

This function returns an error because the polyhedron is possibly unbounded. If P is known to be bounded, try converting to HPolytope first:

julia> P = HPolyhedron([HalfSpace([1.0, 0.0], 1.0),
                        HalfSpace([0.0, 1.0], 1.0),
                        HalfSpace([-1.0, 0.0], 1.0),
                        HalfSpace([0.0, -1.0], 1.0)]);

julia> P_as_polytope = convert(HPolytope, P);

source

LazySets.singleton_list — Method.

singleton_list(P::HPolyhedron{N}) where {N<:Real}

Return the vertices of a polyhedron in H-representation as a list of singletons.

Input

P – polytope in constraint representation

Output

This function returns an error because the polyhedron is possibly unbounded. If P is known to be bounded, try converting to HPolytope first.

source

Inherited from AbstractPolyhedron:

isuniversal