Half-space (HalfSpace)

HalfSpace{N, VN<:AbstractVector{N}} <: AbstractPolyhedron{N}

Type that represents a (closed) half-space of the form $a⋅x ≤ b$.

Fields

• a – normal direction (non-zero)
• b – constraint

Examples

The half-space $x + 2y - z ≤ 3$:

julia> HalfSpace([1, 2, -1.], 3.)
HalfSpace{Float64,Array{Float64,1}}([1.0, 2.0, -1.0], 3.0)

To represent the set $y ≥ 0$ in the plane, we have to rearrange the expression as $0x - y ≤ 0$:

julia> HalfSpace([0, -1.], 0.)
HalfSpace{Float64,Array{Float64,1}}([0.0, -1.0], 0.0)

LinearConstraint

Alias for HalfSpace

dim(hs::HalfSpace)

Return the dimension of a half-space.

Input

• hs – half-space

Output

The ambient dimension of the half-space.

ρ(d::AbstractVector, hs::HalfSpace)

Evaluate the support function of a half-space in a given direction.

Input

• d – direction
• hs – half-space

Output

The support function of the half-space. If the set is unbounded in the given direction, the result is Inf.

σ(d::AbstractVector, hs::HalfSpace)

Return the support vector of a half-space.

Input

• d – direction
• hs – half-space

Output

The support vector in the given direction, which is only defined in the following two cases:

1. The direction has norm zero.
2. The direction is the half-space's normal direction.

In both cases the result is any point on the boundary (the defining hyperplane). Otherwise this function throws an error.

∈(x::AbstractVector, hs::HalfSpace)

Check whether a given point is contained in a half-space.

Input

• x – point/vector
• hs – half-space

Output

true iff $x ∈ hs$.

Algorithm

We just check if $x$ satisfies $a⋅x ≤ b$.

an_element(hs::HalfSpace)

Return some element of a half-space.

Input

• hs – half-space

Output

An element on the defining hyperplane.

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

Create a random half-space.

Input

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

Output

A random half-space.

Algorithm

All numbers are normally distributed with mean 0 and standard deviation 1. Additionally, the constraint a is nonzero.

normalize(hs::HalfSpace{N}, p=N(2)) where {N}

Normalize a half-space.

Input

• hs – half-space
• p – (optional, default: 2) norm

Output

A new half-space whose normal direction $a$ is normalized, i.e., such that $‖a‖_p = 1$ holds.

isbounded(hs::HalfSpace)

Determine whether a half-space is bounded.

Input

• hs – half-space

Output

false.

isuniversal(hs::HalfSpace, [witness]::Bool=false)

Check whether a half-space is universal.

Input

• P – half-space
• witness – (optional, default: false) compute a witness if activated

Output

• If witness option is deactivated: false
• If witness option is activated: (false, v) where $v ∉ P$

Algorithm

Witness production falls back to isuniversal(::Hyperplane).

isempty(hs::HalfSpace)

Return if a half-space is empty or not.

Input

• hs – half-space

Output

false.

constraints_list(hs::HalfSpace)

Return the list of constraints of a half-space.

Input

• hs – half-space

Output

A singleton list containing the half-space.

constraints_list(A::AbstractMatrix{N}, b::AbstractVector)

Convert a matrix-vector representation to a linear-constraint representation.

Input

• A – matrix
• b – vector

Output

A list of linear constraints.

constrained_dimensions(hs::HalfSpace)

Return the indices in which a half-space is constrained.

Input

• hs – half-space

Output

A vector of ascending indices i such that the half-space is constrained in dimension i.

Examples

A 2D half-space with constraint $x1 ≥ 0$ is constrained in dimension 1 only.

translate(hs::HalfSpace, v::AbstractVector; [share]::Bool=false)

Translate (i.e., shift) a half-space by a given vector.

Input

• hs – half-space
• v – translation vector
• share – (optional, default: false) flag for sharing unmodified parts of the original set representation

Output

A translated half-space.

Notes

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

Algorithm

A half-space $a⋅x ≤ b$ is transformed to the half-space $a⋅x ≤ b + a⋅v$. In other words, we add the dot product $a⋅v$ to $b$.

halfspace_left(p::AbstractVector, q::AbstractVector)

Return a half-space describing the 'left' of a two-dimensional line segment through two points.

Input

• p – first point
• q – second point

Output

The half-space whose boundary goes through the two points p and q and which describes the left-hand side of the directed line segment pq.

Algorithm

The implementation is simple: the half-space $a⋅x ≤ b$ is calculated as a = [dy, -dx], where $d = (dx, dy)$ denotes the line segment pq, that is, $\vec{d} = \vec{p} - \vec{q}$, and b = dot(p, a).

Examples

The left half-space of the "east" and "west" directions in two-dimensions are the upper and lower half-spaces:

julia> using LazySets: halfspace_left

julia> halfspace_left([0.0, 0.0], [1.0, 0.0])
HalfSpace{Float64,Array{Float64,1}}([0.0, -1.0], 0.0)

julia> halfspace_left([0.0, 0.0], [-1.0, 0.0])
HalfSpace{Float64,Array{Float64,1}}([0.0, 1.0], 0.0)

We create a box from the sequence of line segments that describe its edges:

julia> H1 = halfspace_left([-1.0, -1.0], [1.0, -1.0]);

julia> H2 = halfspace_left([1.0, -1.0], [1.0, 1.0]);

julia> H3 = halfspace_left([1.0, 1.0], [-1.0, 1.0]);

julia> H4 = halfspace_left([-1.0, 1.0], [-1.0, -1.0]);

julia> H = HPolygon([H1, H2, H3, H4]);

julia> B = BallInf([0.0, 0.0], 1.0);

julia> B ⊆ H && H ⊆ B
true

halfspace_right(p::AbstractVector, q::AbstractVector)

Return a half-space describing the 'right' of a two-dimensional line segment through two points.

Input

• p – first point
• q – second point

Output

The half-space whose boundary goes through the two points p and q and which describes the right-hand side of the directed line segment pq.

Algorithm

See the documentation of halfspace_left.

tosimplehrep(constraints::AbstractVector{LC}) where {N, LC<:LinearConstraint{N}}

Return the simple H-representation $Ax ≤ b$ from a list of linear constraints.

Input

• constraints – a list of linear constraints

Output

The tuple (A, b) where A is the matrix of normal directions and b is the vector of offsets.

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::AbstractHPolygon)

Remove all redundant constraints of a polygon in constraint representation.

Input

• P – polygon in constraint representation

Output

The same polygon with all redundant constraints removed.

Notes

Since we only consider bounded polygons and a polygon needs at least three constraints to be bounded, we stop removing redundant constraints if there are three or less constraints left. This means that for non-bounded polygons the result may be unexpected.

Algorithm

We go through all consecutive triples of constraints and check if the one in the middle is redundant. For this we assume that the constraints are sorted.

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.

complement(H::HalfSpace)

Return the complement of a half-space.

Input

• H – halfspace

Output

The halfspace that is complementary to H. If $H: \langle a, x \rangle ≤ b$, then this function returns the halfspace $H′: \langle a, x \rangle ≥ b$. (Note that complementarity is understood in a relaxed sense, since the intersection of $H$ and $H′$ is non-empty).

project(H::HalfSpace, block::AbstractVector{Int}; [kwargs...])

Concrete projection of a half-space.

Input

• H – set
• block – block structure, a vector with the dimensions of interest

Output

A set representing the projection of the half-space H on the dimensions specified by block.

Algorithm

If the unconstrained dimensions of H are a subset of the block variables, the projection is applied to the normal direction of H. Otherwise, the projection results in the universal set.

The latter can be seen as follows. Without loss of generality consider a projection onto a single and constrained dimension $xₖ$ (projections in multiple dimensions can be modeled as repeated one-dimensional projections). We can write the projection as an existentially quantified linear constraint:

\[ ∃xₖ: a₁x₁ + … + aₖxₖ + … + aₙxₙ ≤ b\]

Since $aₖ ≠ 0$, there is always a value for $xₖ$ that satisfies the constraint for any valuation of the other variables.

Examples

Consider the half-space $x + y + 0⋅z ≤ 1$, whose ambient dimension is 3. The (trivial) projection in the three dimensions is achieved letting the block of variables to be [1, 2, 3]:

julia> H = HalfSpace([1.0, 1.0, 0.0], 1.0)
HalfSpace{Float64,Array{Float64,1}}([1.0, 1.0, 0.0], 1.0)

julia> project(H, [1, 2, 3])
HalfSpace{Float64,Array{Float64,1}}([1.0, 1.0, 0.0], 1.0)

Projecting along dimensions 1 and 2 only:

julia> project(H, [1, 2])
HalfSpace{Float64,Array{Float64,1}}([1.0, 1.0], 1.0)

In general, use the call syntax project(H, constrained_dimensions(H)) to return the half-space projected on the dimensions where it is constrained only:

julia> project(H, constrained_dimensions(H))
HalfSpace{Float64,Array{Float64,1}}([1.0, 1.0], 1.0)

If a constrained dimension is projected, we get the universal set of the dimension corresponding to the projection.

julia> project(H, [1, 3])
Universe{Float64}(2)

julia> project(H, [1])
Universe{Float64}(1)