Interval

Interval{N, IN<:AbstractInterval{N}} <: AbstractHyperrectangle{N}

Type representing an interval on the real line. Mathematically, it is of the form

\[[a, b] := \{ a ≤ x ≤ b \} ⊆ \mathbb{R}.\]

Fields

• dat – data container for the given interval

Notes

This type relies on the IntervalArithmetic.jl library for representation of intervals and arithmetic operations.

Examples

Unidimensional intervals are symbolic representations of a real closed interval.

We can create intervals in different ways, the simpler way is to pass a pair of numbers:

julia> x = Interval(0.0, 1.0)
Interval{Float64,IntervalArithmetic.Interval{Float64}}([0, 1])

or a 2-vector:

julia> x = Interval([0.0, 1.0])
Interval{Float64,IntervalArithmetic.Interval{Float64}}([0, 1])

Note that if the package IntervalArithmetic is loaded in the current scope, you have to prepend LazySets. to the Interval type since there is a name conflict otherwise.

julia> using IntervalArithmetic
WARNING: using IntervalArithmetic.Interval in module Main conflicts with an existing identifier.

julia> x = Interval(IntervalArithmetic.Interval(0.0, 1.0))
Interval{Float64,IntervalArithmetic.Interval{Float64}}([0, 1])

julia> dim(x)
1

julia> center(x)
1-element Array{Float64,1}:
 0.5

This type is such that the usual pairwise arithmetic operators +, -, * trigger the corresponding interval arithmetic backend method, and return a new Interval object. For the symbolic Minkowksi sum, use MinkowskiSum or ⊕.

Interval of other numeric types can be created as well, eg. a rational interval:

julia> Interval(0//1, 2//1)
Interval{Rational{Int64},IntervalArithmetic.Interval{Rational{Int64}}}([0//1, 2//1])

dim(x::Interval)

Return the ambient dimension of an interval.

Input

• x – interval

Output

The integer 1.

σ(d::AbstractVector, x::Interval)

Return the support vector of an interval in a given direction.

Input

• d – direction
• x – interval

Output

Support vector in the given direction.

ρ(d::AbstractVector, x::Interval)

Evaluate the support function of an interval in a given direction.

Input

• d – direction
• x – interval

Output

Evaluation of the support function in the given direction.

∈(v::AbstractVector, x::Interval))

Return whether a vector is contained in the interval.

Input

• v – one-dimensional vector
• x – interval

Output

true iff x contains v's first component.

∈(v::N, x::Interval{N}) where {N}

Return whether a number is contained in the interval.

Input

• v – scalar
• x – interval

Output

true iff x contains v.

an_element(x::Interval)

Return some element of an interval.

Input

• x – interval

Output

The left border (min(x)) of the interval.

vertices_list(x::Interval)

Return the list of vertices of this interval.

Input

• x – interval

Output

The list of vertices of the interval represented as two one-dimensional vectors, or just one if the interval is degenerate (the endpoints match within the tolerance).

translate(x::Interval, v::AbstractVector)

Translate (i.e., shift) an interval by a given vector.

Input

• x – interval
• v – translation vector

Output

A translated interval.

Algorithm

We add the vector to the left and right of the interval.

center(x::Interval)

Return the interval's center.

Input

• x – interval

Output

The center, or midpoint, of $x$.

center(H::Interval, i::Int)

Return the center along a given dimension of a interval.

Input

• x – interval
• i – dimension of interest

Output

The center along a given dimension of the interval.

min(x::Interval)

Return the lower component of an interval.

Input

• x – interval

Output

The lower (lo) component of the interval.

max(x::Interval)

Return the higher or upper component of an interval.

Input

• x – interval

Output

The higher (hi) component of the interval.

low(x::Interval{N}) where {N}

Return the lower coordinate of an interval set.

Input

• x – interval

Output

A vector with the lower coordinate of the interval.

high(x::Interval{N}) where {N}

Return the higher coordinate of an interval set.

Input

• x – interval

Output

A vector with the higher coordinate of the interval.

radius_hyperrectangle(x::Interval)

Return the box radius of an interval in every dimension.

Input

• x – interval

Output

The box radius of the interval (a one-dimensional vector).

radius_hyperrectangle(x::Interval{N}, i::Int) where {N}

Return the box radius of an interval in a given dimension.

Input

• x – interval
• i – dimension index (must be 1)

Output

The box radius in the given dimension.

-(x::Interval, y::Interval)

Return the difference of the intervals.

Input

• x – interval
• y – interval

Output

The difference of the intervals as a new Interval set.

    *(x::Interval, y::Interval)

Return the product of the intervals.

Input

• x – interval
• y – interval

Output

The product of the intervals as a new Interval set.

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

Create a random interval.

Input

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

Output

A random interval.

Algorithm

All numbers are normally distributed with mean 0 and standard deviation 1.

isflat(I::Interval)

Determine whether an interval is flat, i.e. whether its extreme values coincide.

Input

• I – interval

Output

A boolean which is true if the interval is flat and false otherwise.

Notes

For robustness with respect to floating-point inputs, this function relies on the result of isapproxzero when applied to the diameter of the interval. Hence, this function depends on the absolute zero tolerance ABSZTOL.

plot_recipe(I::Interval{N}, [ε]=zero(N)) where {N}

Convert an interval to a pair (x, y) of points for plotting.

Input

• I – interval
• ε – (optional, default: 0) ignored, used for dispatch

Output

A pair (x, y) of two points that can be plotted.

Notes

We consider the interval as a line segment with y coordinate equal to zero.

linear_map(M::AbstractMatrix, x::Interval)

Concrete linear map of an interval.

Input

• M – matrix
• x – interval

Output

Either an interval or a zonotope, depending on the leading dimension (i.e. the number of rows) of M:

• If size(M, 1) == 1, the output is an interval obtained by scaling x by the matrix M.
• If size(M, 1) > 1, the output is a zonotope whose center is M * center(x) and it has the single generator, M * g, where g = (high(x)-low(x))/2.

scale(α::Real, x::Interval)

Concrete scaling of an interval.

Input

• α – scalar
• x – interval

Output

The interval obtained by applying the numerical scale to the given interval.

constraints_list(H::AbstractHyperrectangle{N}) where {N}

Return the list of constraints of an axis-aligned hyperrectangular set.

Input

• H – hyperrectangular set

Output

A list of linear constraints.

constraints_list(P::Ball1{N}) where {N}

Return the list of constraints defining a ball in the 1-norm.

Input

• B – ball in the 1-norm

Output

The list of constraints of the ball.

Algorithm

The constraints can be defined as $d_i^T (x-c) ≤ r$ for all $d_i$, where $d_i$ is a vector with elements $1$ or $-1$ in $n$ dimensions. To span all possible $d_i$, the function Iterators.product is used.

constraints_list(x::Interval{N}) where {N}

Return the list of constraints of the given interval.

Input

• x – interval

Output

The list of constraints of the interval represented as two one-dimensional half-spaces.

constraints_list(L::Line{N, VN}) where {N, VN}

Return the list of constraints of a line.

Input

• L – line

Output

A list containing 2n-2 half-spaces whose intersection is L, where n is the ambient dimension of L.

constraints_list(U::Universe{N}) where {N}

Return the list of constraints defining a universe.

Input

• U – universe

Output

The empty list of constraints, as the universe is unconstrained.

constraints_list(P::HParallelotope{N, VN}) where {N, VN}

Return the list of constraints of the given parallelotope.

Input

• P – parallelotope in constraint representation

Output

The list of constraints of P.

constraints_list(cpa::CartesianProductArray{N}) where {N}

Return the list of constraints of a (polyhedral) Cartesian product of a finite number of sets.

Input

• cpa – Cartesian product array

Output

A list of constraints.

constraints_list(ia::IntersectionArray{N}) where {N}

Return the list of constraints of an intersection of a finite number of (polyhedral) sets.

Input

• ia – intersection of a finite number of (polyhedral) sets

Output

The list of constraints of the intersection.

Notes

We assume that the underlying sets are polyhedral, i.e., offer a method constraints_list.

Algorithm

We create the polyhedron from the constraints_lists of the sets and remove redundant constraints.

constraints_list(rm::ResetMap{N}) where {N}

Return the list of constraints of a polytopic reset map.

Input

• rm – reset map of a polytope

Output

The list of constraints of the reset map.

Notes

We assume that the underlying set X is a polytope, i.e., is bounded and offers a method constraints_list(X).

Algorithm

We fall back to constraints_list of a LinearMap of the A-matrix in the affine-map view of a reset map. Each reset dimension $i$ is projected to zero, expressed by two constraints for each reset dimension. Then it remains to shift these constraints to the new value.

For instance, if the dimension $5$ was reset to $4$, then there will be constraints $x₅ ≤ 0$ and $-x₅ ≤ 0$. We then modify the right-hand side of these constraints to $x₅ ≤ 4$ and $-x₅ ≤ -4$, respectively.

constraints_list(rm::ResetMap{N, S}) where {N, S<:AbstractHyperrectangle}

Return the list of constraints of a hyperrectangular reset map.

Input

• rm – reset map of a hyperrectangular set

Output

The list of constraints of the reset map.

Algorithm

We iterate through all dimensions. If there is a reset, we construct the corresponding (flat) constraints. Otherwise, we construct the corresponding constraints of the underlying set.

rectify(x::Interval{N}) where {N}

Concrete rectification of an interval.

Input

• x – interval

Output

The Interval that corresponds to the rectification of x.

Notes

Note that the result is an Interval even if the set becomes a singleton (which is the case if the original interval was nonpositive).

diameter(x::Interval, [p]::Real=Inf)

Compute the diameter of an interval, defined as $\Vert b - a\Vert$ in the $p`-norm, where$a$(resp.$b``) are the minimum (resp. maximum) of the given interval.

Input

• x – interval
• p – (optional, default: Inf) norm

Output

A real number representing the diameter.

Notes

In one dimension all norms are the same.

split(x::Interval, k)

Partition an interval into k uniform sub-intervals.

Input

• x – interval
• k – number of sub-intervals, possibly wrapped in a vector of length 1

Output

A list of k Intervals.