Hyperplane

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

Type that represents a hyperplane of the form $a⋅x = b$.

Fields

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

Examples

The line $y = 0$ in 2D:

julia> Hyperplane([0, 1.], 0.)
Hyperplane{Float64, Vector{Float64}}([0.0, 1.0], 0.0)

convert(::Type{Hyperplane{N}}, expr::Expr; vars=Vector{Basic}=Basic[]) where {N}

Return a LazySet.Hyperplane given a symbolic expression that represents a hyperplane.

Input

• expr – a symbolic expression
• vars – (optional, default: Basic[]): set of variables with respect to which the gradient is taken; if empty, we take the free symbols in the given expression

Output

A Hyperplane, in the form ax = b.

Examples

julia> convert(Hyperplane, :(x1 = -0.03))
Hyperplane{Float64, Vector{Float64}}([1.0], -0.03)

julia> convert(Hyperplane, :(x1 + 0.03 = 0))
Hyperplane{Float64, Vector{Float64}}([1.0], -0.03)

julia> convert(Hyperplane, :(x1 + x2 = 2*x4 + 6))
Hyperplane{Float64, Vector{Float64}}([1.0, 1.0, -2.0], 6.0)

You can also specify the set of "ambient" variables in the hyperplane, even if not all of them appear:

julia> using SymEngine: Basic

julia> convert(Hyperplane, :(x1 + x2 = 2*x4 + 6), vars=Basic[:x1, :x2, :x3, :x4])
Hyperplane{Float64, Vector{Float64}}([1.0, 1.0, 0.0, -2.0], 6.0)

an_element(X::LazySet)

Return some element of a nonempty set.

Input

• X – set

Output

An element of X unless X is empty.

Extended help

an_element(H::Hyperplane)

Algorithm

We compute a point on the hyperplane $a⋅x = b$ as follows:

• We first find a nonzero entry of $a$ in dimension, say, $i$.
• We set $x[i] = b / a[i]$.
• We set $x[j] = 0$ for all $j ≠ i$.

constrained_dimensions(H::Hyperplane)

Return the dimensions in which a hyperplane is constrained.

Input

• H – hyperplane

Output

A vector of ascending indices i such that the hyperplane is constrained in dimension i.

Examples

A 2D hyperplane with constraint $x_1 = 0$ is constrained in dimension 1 only.

isbounded(X::LazySet)

Check whether a set is bounded.

Input

• X – set

Output

true iff the set is bounded.

Notes

See also isboundedtype(::Type{<:LazySet}).

Extended help

isbounded(H::Hyperplane)

Algorithm

The result is true iff H is one-dimensional.

isuniversal(X::LazySet, witness::Bool=false)

Check whether a set is universal.

Input

• X – set
• witness – (optional, default: false) compute a witness if activated

Output

• If the witness option is deactivated: true iff $X = ℝ^n$
• If the witness option is activated:
  • (true, []) iff $X = ℝ^n$
  • (false, v) iff $X ≠ ℝ^n$ for some $v ∉ X$

Extended help

isuniversal(H::Hyperplane, [witness]::Bool=false)

Algorithm

A witness is produced by adding the normal vector to an element on the hyperplane.

normalize(H::Hyperplane{N}, p::Real=N(2)) where {N}

Normalize a hyperplane.

Input

• H – hyperplane
• p – (optional, default: 2) norm

Output

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

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

Create a random set of the given set type.

Input

• T – set type
• 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 set of the given set type.

Extended help

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

Algorithm

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

in(x::AbstractVector, X::LazySet)

Check whether a point lies in a set.

Input

• x – point/vector
• X – set

Output

true iff $x ∈ X$.

Extended help

in(x::AbstractVector, H::Hyperplane)

Algorithm

We just check whether $x$ satisfies $a⋅x = b$.

project(x::AbstractVector, H::Hyperplane)

Project a point onto a hyperplane.

Input

• x – point
• H – hyperplane

Output

The projection of x onto H.

Algorithm

The projection of $x$ onto the hyperplane of the form $a⋅x = b$ is

\[ x - \dfrac{a (a⋅x - b)}{‖a‖²}\]

reflect(x::AbstractVector, H::Hyperplane)

Reflect (mirror) a vector in a hyperplane.

Input

• x – point/vector
• H – hyperplane

Output

The reflection of x in H.

Algorithm

The reflection of a point $x$ in the hyperplane $a ⋅ x = b$ is

\[ x − 2 \frac{x ⋅ a − b}{a ⋅ a} a\]

where $u · v$ denotes the dot product.

ρ(d::AbstractVector, X::LazySet)

Evaluate the support function of a set in a given direction.

Input

• d – direction
• X – set

Output

The evaluation of the support function of X in direction d.

Notes

The convenience alias support_function is also available.

We have the following identity based on the support vector $σ$:

\[ ρ(d, X) = d ⋅ σ(d, X)\]

Extended help

ρ(d::AbstractVector, H::Hyperplane)

Output

If the set is unbounded in the given direction, the result is Inf.

σ(d::AbstractVector, X::LazySet)

Compute a support vector of a set in a given direction.

Input

• d – direction
• X – set

Output

A support vector of X in direction d.

Notes

The convenience alias support_vector is also available.

Extended help

σ(d::AbstractVector, H::Hyperplane)

Output

A 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 hyperplane's normal direction or its opposite direction.

In all cases, any point on the hyperplane is a solution. Otherwise this function throws an error.

    _σ_hyperplane_halfspace(d::AbstractVector, a, b;
                            [error_unbounded]::Bool=true,
                            [halfspace]::Bool=false)

Return a support vector of a hyperplane $a⋅x = b$ in direction d.

Input

• d – direction
• a – normal direction
• b – constraint
• error_unbounded – (optional, default: true) true if an error should be thrown whenever the set is unbounded in the given direction
• halfspace – (optional, default: false) true if the support vector should be computed for a half-space

Output

A pair (v, f) where v is a vector and f is a Boolean flag.

The flag f is false in one of the following cases:

1. The direction has norm zero.
2. The direction is (a multiple of) the hyperplane's normal direction.
3. The direction is (a multiple of) the opposite of the hyperplane's normal

direction and halfspace is false. In all these cases, v is any point on the hyperplane.

Otherwise, the flag f is true, the set is unbounded in the given direction, and v is any vector.

If error_unbounded is true and the set is unbounded in the given direction, this function throws an error instead of returning.

Notes

For correctness, consider the weak duality of LPs: If the primal is unbounded, then the dual is infeasible. Since there is only a single constraint, the feasible set of the dual problem is $a ⋅ y == d$, $y ≥ 0$ (with objective function $b ⋅ y$). It is easy to see that this problem is infeasible whenever $a$ is not parallel to $d$.

translate(X::LazySet, v::AbstractVector)

Compute the translation of a set with a vector.

Input

• X – set
• v – vector

Output

A set representing $X + \{v\}$.

Extended help

translate(H::Hyperplane, v::AbstractVector; share::Bool=false)

Notes

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

Algorithm

A hyperplane $a⋅x = b$ is transformed to the hyperplane $a⋅x = b + a⋅v$. In other words, we add the dot product $a⋅v$ to $b$.

_ishyperplanar(expr::Expr)

Determine whether the given expression corresponds to a hyperplane.

Input

• expr – a symbolic expression

Output

true if expr corresponds to a half-space or false otherwise.

Examples

julia> using LazySets: _ishyperplanar

julia> _ishyperplanar(:(x1 = 0))
true

julia> _ishyperplanar(:(x1 <= 0))
false

julia> _ishyperplanar(:(2*x1 = 4))
true

julia> _ishyperplanar(:(6.1 = 5.3*f - 0.1*g))
true

julia> _ishyperplanar(:(2*x1^2 = 4))
false

julia> _ishyperplanar(:(x1^2 = 4*x2 - x3))
false

julia> _ishyperplanar(:(x1 = 4*x2 - x3))
true