# Polyhedron in constraint representation (HPolyhedron)

`LazySets.HPolyhedron`

— Type`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

The following methods are shared between `HPolytope`

and `HPolyhedron`

.

`LazySets.dim`

— Method`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$.

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

.

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

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

`LazySets.constraints_list`

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

`LazySets.tohrep`

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

`LazySets.tovrep`

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

`LinearAlgebra.normalize`

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

`Base.isempty`

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

`LazySets.translate`

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

`Polyhedra.polyhedron`

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

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

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

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

`LazySets._isbounded_stiemke`

— Method```
_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.

Inherited from `ConvexSet`

:

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.

`LazySets.isbounded`

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

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

Inherited from `AbstractPolyhedron`

: