Common Set Operations

CartesianProduct{N<:Real, S1<:LazySet{N}, S2<:LazySet{N}} <: LazySet{N}

Type that represents a Cartesian product of two convex sets.

Fields

• X – first convex set
• Y – second convex set

Notes

The Cartesian product of three elements is obtained recursively. See also CartesianProductArray for an implementation of a Cartesian product of many sets without recursion, instead using an array.

The EmptySet is the absorbing element for CartesianProduct.

Constructors:

• CartesianProduct{N<:Real, S1<:LazySet{N}, S2<:LazySet{N}}(X1::S1, X2::S2) – default constructor

• CartesianProduct(Xarr::Vector{S}) where {S<:LazySet} – constructor from an array of convex sets

×

Alias for the binary Cartesian product.

    *(X::LazySet, Y::LazySet)

Alias for the binary Cartesian product.

swap(cp::CartesianProduct)

Return a new CartesianProduct object with the arguments swapped.

Input

• cp – Cartesian product of two convex sets

Output

A new CartesianProduct object with the arguments swapped.

dim(cp::CartesianProduct)::Int

Return the dimension of a Cartesian product.

Input

• cp – Cartesian product

Output

The ambient dimension of the Cartesian product.

ρ(d::AbstractVector{N}, cp::CartesianProduct{N}) where {N<:Real}

Return the support function of a Cartesian product.

Input

• d – direction
• cp – Cartesian product

Output

The support function in the given direction. If the direction has norm zero, the result depends on the wrapped sets.

σ(d::AbstractVector{N}, cp::CartesianProduct{N}) where {N<:Real}

Return the support vector of a Cartesian product.

Input

• d – direction
• cp – Cartesian product

Output

The support vector in the given direction. If the direction has norm zero, the result depends on the wrapped sets.

isbounded(cp::CartesianProduct)::Bool

Determine whether a Cartesian product is bounded.

Input

• cp – Cartesian product

Output

true iff both wrapped sets are bounded.

∈(x::AbstractVector{N}, cp::CartesianProduct{N})::Bool where {N<:Real}

Check whether a given point is contained in a Cartesian product.

Input

• x – point/vector
• cp – Cartesian product

Output

true iff $x ∈ cp$.

isempty(cp::CartesianProduct)::Bool

Return if a Cartesian product is empty or not.

Input

• cp – Cartesian product

Output

true iff any of the sub-blocks is empty.

constraints_list(cp::CartesianProduct{N}) where {N<:Real}

Return the list of constraints of a (polytopic) Cartesian product.

Input

• cp – Cartesian product

Output

A list of constraints.

vertices_list(cp::CartesianProduct{N})::Vector{Vector{N}} where {N<:Real}

Return the list of vertices of a (polytopic) Cartesian product.

Input

• cp – Cartesian product

Output

A list of vertices.

Algorithm

We assume that the underlying sets are polytopic. Then the high-dimensional set of vertices is just the Cartesian product of the low-dimensional sets of vertices.

CartesianProductArray{N<:Real, S<:LazySet{N}} <: LazySet{N}

Type that represents the Cartesian product of a finite number of convex sets.

Fields

• array – array of sets

Notes

The EmptySet is the absorbing element for CartesianProductArray.

Constructors:

• CartesianProductArray(array::Vector{<:LazySet}) – default constructor

• CartesianProductArray([n]::Int=0, [N]::Type=Float64) – constructor for an empty product with optional size hint and numeric type

dim(cpa::CartesianProductArray)::Int

Return the dimension of a Cartesian product of a finite number of convex sets.

Input

• cpa – Cartesian product array

Output

The ambient dimension of the Cartesian product of a finite number of convex sets.

ρ(d::AbstractVector{N}, cp::CartesianProductArray{N}) where {N<:Real}

Return the support function of a Cartesian product array.

Input

• d – direction
• cpa – Cartesian product array

Output

The support function in the given direction. If the direction has norm zero, the result depends on the wrapped sets.

σ(d::AbstractVector{N}, cpa::CartesianProductArray{N}) where {N<:Real}

Support vector of a Cartesian product array.

Input

• d – direction
• cpa – Cartesian product array

Output

The support vector in the given direction. If the direction has norm zero, the result depends on the product sets.

isbounded(cpa::CartesianProductArray)::Bool

Determine whether a Cartesian product of a finite number of convex sets is bounded.

Input

• cpa – Cartesian product of a finite number of convex sets

Output

true iff all wrapped sets are bounded.

∈(x::AbstractVector{N}, cpa::CartesianProductArray{N}
 )::Bool where {N<:Real}

Check whether a given point is contained in a Cartesian product of a finite number of sets.

Input

• x – point/vector
• cpa – Cartesian product array

Output

true iff $x ∈ \text{cpa}$.

isempty(cpa::CartesianProductArray)::Bool

Return if a Cartesian product is empty or not.

Input

• cp – Cartesian product

Output

true iff any of the sub-blocks is empty.

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

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

Input

• cpa – Cartesian product array

Output

A list of constraints.

vertices_list(cpa::CartesianProductArray{N}
             )::Vector{Vector{N}} where {N<:Real}

Return the list of vertices of a (polytopic) Cartesian product of a finite number of sets.

Input

• cpa – Cartesian product array

Output

A list of vertices.

Algorithm

We assume that the underlying sets are polytopic. Then the high-dimensional set of vertices is just the Cartesian product of the low-dimensional sets of vertices.

array(cpa::CartesianProductArray{N, S}
     )::Vector{S} where {N<:Real, S<:LazySet{N}}

Return the array of a Cartesian product of a finite number of convex sets.

Input

• cpa – Cartesian product array

Output

The array of a Cartesian product of a finite number of convex sets.

array(cha::ConvexHullArray{N, S})::Vector{S} where {N<:Real, S<:LazySet{N}}

Return the array of a convex hull of a finite number of convex sets.

Input

• cha – convex hull array

Output

The array of a convex hull of a finite number of convex sets.

array(ia::IntersectionArray{N, S})::Vector{S} where {N<:Real, S<:LazySet{N}}

Return the array of an intersection of a finite number of convex sets.

Input

• ia – intersection of a finite number of convex sets

Output

The array of an intersection of a finite number of convex sets.

array(msa::MinkowskiSumArray{N, S})::Vector{S} where {N<:Real, S<:LazySet{N}}

Return the array of a Minkowski sum of a finite number of convex sets.

Input

• msa – Minkowski sum array

Output

The array of a Minkowski sum of a finite number of convex sets.

array(cms::CacheMinkowskiSum{N, S})::Vector{S} where {N<:Real, S<:LazySet{N}}

Return the array of a caching Minkowski sum.

Input

• cms – caching Minkowski sum

Output

The array of a caching Minkowski sum.

array(cup::UnionSetArray{N, S})::Vector{S} where {N<:Real, S<:LazySet{N}}

Return the array of a union of a finite number of convex sets.

Input

• cup – union of a finite number of convex sets

Output

The array that holds the union of a finite number of convex sets.

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

Returns an array containing the dimension ranges of each block in a CartesianProductArray.

Input

• cpa – Cartesian product array

Output

A vector of ranges

Example

julia> using LazySets: block_structure

julia> cpa = CartesianProductArray([BallInf(zeros(n), 1.0) for n in [3, 1, 2]]);

julia> block_structure(cpa)
3-element Array{UnitRange{Int64},1}:
 1:3
 4:4
 5:6

block_to_dimension_indices(cpa::CartesianProductArray{N}, vars::Vector{Int}) where {N}

Returns a vector mapping block index i to tuple (f, l) such that either f = l = -1 or f is the first dimension index and l is the last dimension index of the i-th block, depending on whether one of the block's dimension indices is specified in vars.

Input

• cpa – Cartesian product array
• vars – list containing the variables of interest, sorted in ascending order

Output

(i) A vector of tuples, where values in tuple relate to range of dimensions in the i-th block. (ii) Number of constrained blocks

Example

julia> using LazySets: block_to_dimension_indices

julia> cpa = CartesianProductArray([BallInf(zeros(n), 1.0) for n in [1, 3, 2, 3]]);

julia> block_to_dimension_indices(cpa, [2, 4, 8])
(Tuple{Int64,Int64}[(-1, -1), (2, 4), (-1, -1), (7, 9)], 2)

This vector represents the mapping "second block from dimension 2 to dimension 4, fourth block from dimension 7 to dimension 9." These blocks contain the dimensions specified in [2, 4, 8]. Number of constrained variables here is 2 (2nd and 4th blocks)

substitute_blocks(low_dim_cpa::CartesianProductArray{N},
                     orig_cpa::CartesianProductArray{N},
                       blocks::Vector{Tuple{Int,Int}}) where {N}

Return merged Cartesian Product Array between original CPA and some low-dimensional CPA, which represents updated subset of variables in specified blocks.

Input

• low_dim_cpa – low-dimensional cartesian product array
• orig_cpa – original high-dimensional Cartesian product array
• blocks – index of the first variable in each block of orig_cpa

Output

Merged cartesian product array

ConvexHull{N<:Real, S1<:LazySet{N}, S2<:LazySet{N}} <: LazySet{N}

Type that represents the convex hull of the union of two convex sets.

Fields

• X – convex set
• Y – convex set

Notes

The EmptySet is the neutral element for ConvexHull.

Examples

Convex hull of two 100-dimensional Euclidean balls:

julia> b1, b2 = Ball2(zeros(100), 0.1), Ball2(4*ones(100), 0.2);

julia> c = ConvexHull(b1, b2);

julia> typeof(c)
ConvexHull{Float64,Ball2{Float64},Ball2{Float64}}

CH

Alias for ConvexHull.

swap(ch::ConvexHull)

Return a new ConvexHull object with the arguments swapped.

Input

• ch – convex hull of two convex sets

Output

A new ConvexHull object with the arguments swapped.

dim(ch::ConvexHull)::Int

Return the dimension of a convex hull of two convex sets.

Input

• ch – convex hull of two convex sets

Output

The ambient dimension of the convex hull of two convex sets.

ρ(d::AbstractVector{N}, ch::ConvexHull{N}) where {N<:Real}

Return the support function of a convex hull of two convex sets in a given direction.

Input

• d – direction
• ch – convex hull of two convex sets

Output

The support function of the convex hull in the given direction.

σ(d::AbstractVector{N}, ch::ConvexHull{N}) where {N<:Real}

Return the support vector of a convex hull of two convex sets in a given direction.

Input

• d – direction
• ch – convex hull of two convex sets

Output

The support vector of the convex hull in the given direction.

isbounded(ch::ConvexHull)::Bool

Determine whether a convex hull of two convex sets is bounded.

Input

• ch – convex hull of two convex sets

Output

true iff both wrapped sets are bounded.

isempty(ch::ConvexHull)::Bool

Return if a convex hull of two convex sets is empty or not.

Input

• ch – convex hull

Output

true iff both wrapped sets are empty.

ConvexHullArray{N<:Real, S<:LazySet{N}} <: LazySet{N}

Type that represents the symbolic convex hull of a finite number of convex sets.

Fields

• array – array of sets

Notes

The EmptySet is the neutral element for ConvexHullArray.

Constructors:

• ConvexHullArray(array::Vector{<:LazySet}) – default constructor

• ConvexHullArray([n]::Int=0, [N]::Type=Float64) – constructor for an empty hull with optional size hint and numeric type

Examples

Convex hull of 100 two-dimensional balls whose centers follows a sinusoidal:

julia> b = [Ball2([2*pi*i/100, sin(2*pi*i/100)], 0.05) for i in 1:100];

julia> c = ConvexHullArray(b);

CHArray

Alias for ConvexHullArray.

dim(cha::ConvexHullArray)::Int

Return the dimension of the convex hull of a finite number of convex sets.

Input

• cha – convex hull array

Output

The ambient dimension of the convex hull of a finite number of convex sets.

ρ(d::AbstractVector{N}, cha::ConvexHullArray{N}) where {N<:Real}

Return the support function of a convex hull array in a given direction.

Input

• d – direction
• cha – convex hull array

Output

The support function of the convex hull array in the given direction.

Algorithm

This algorihm calculates the maximum over all $ρ(d, X_i)$ where the $X_1, …, X_k$ are the sets in the array cha.

σ(d::AbstractVector{N}, cha::ConvexHullArray{N}) where {N<:Real}

Return the support vector of a convex hull array in a given direction.

Input

• d – direction
• cha – convex hull array

isbounded(cha::ConvexHullArray)::Bool

Determine whether a convex hull of a finite number of convex sets is bounded.

Input

• cha – convex hull of a finite number of convex sets

Output

true iff all wrapped sets are bounded.

array(cpa::CartesianProductArray{N, S}
     )::Vector{S} where {N<:Real, S<:LazySet{N}}

Return the array of a Cartesian product of a finite number of convex sets.

Input

• cpa – Cartesian product array

Output

The array of a Cartesian product of a finite number of convex sets.

array(cha::ConvexHullArray{N, S})::Vector{S} where {N<:Real, S<:LazySet{N}}

Return the array of a convex hull of a finite number of convex sets.

Input

• cha – convex hull array

Output

The array of a convex hull of a finite number of convex sets.

array(ia::IntersectionArray{N, S})::Vector{S} where {N<:Real, S<:LazySet{N}}

Return the array of an intersection of a finite number of convex sets.

Input

• ia – intersection of a finite number of convex sets

Output

The array of an intersection of a finite number of convex sets.

array(msa::MinkowskiSumArray{N, S})::Vector{S} where {N<:Real, S<:LazySet{N}}

Return the array of a Minkowski sum of a finite number of convex sets.

Input

• msa – Minkowski sum array

Output

The array of a Minkowski sum of a finite number of convex sets.

array(cms::CacheMinkowskiSum{N, S})::Vector{S} where {N<:Real, S<:LazySet{N}}

Return the array of a caching Minkowski sum.

Input

• cms – caching Minkowski sum

Output

The array of a caching Minkowski sum.

array(cup::UnionSetArray{N, S})::Vector{S} where {N<:Real, S<:LazySet{N}}

Return the array of a union of a finite number of convex sets.

Input

• cup – union of a finite number of convex sets

Output

The array that holds the union of a finite number of convex sets.

isempty(cha::ConvexHullArray)::Bool

Return if a convex hull array is empty or not.

Input

• cha – convex hull array

Output

true iff all wrapped sets are empty.

convex_hull(points::Vector{VN};
            [algorithm]=default_convex_hull_algorithm(points),
            [backend]=nothing,
            [solver]=nothing
            )::Vector{VN} where {N<:Real, VN<:AbstractVector{N}}

Compute the convex hull of the given points.

Input

• points – list of vectors
• algorithm – (optional, default: depends on the dimension) the convex hull algorithm, see valid options below
• backend – (optional, default: "nothing") polyhedral computation backend for higher-dimensional point sets
• solver – (optional, default: "nothing") the linear programming solver used in the backend

Output

The convex hull as a list of vectors with the coordinates of the points.

Algorithm

A pre-processing step treats the cases with up to two points for one dimension and up to four points for two dimensions. For more points in one resp. two dimensions, we use more general algorithms.

For the one-dimensional case we return the minimum and maximum points, in that order.

The two-dimensional case is handled with a planar convex hull algorithm. The following algorithms are available:

• "monotone_chain" – compute the convex hull of points in the plane using Andrew's monotone chain method
• "monotone_chain_sorted" – the same as "monotone_chain" but assuming that the points are already sorted in counter-clockwise fashion

See the reference docstring of each of those algorithms for details.

The higher dimensional case is treated using the concrete polyhedra library Polyhedra, that gives access to libraries such as CDDLib and ConvexHull.jl. These libraries can be chosen from the backend argument.

Notes

For the in-place version use convex_hull! instead of convex_hull.

Examples

Compute the convex hull of a random set of points:

julia> points = [randn(2) for i in 1:30]; # 30 random points in 2D

julia> hull = convex_hull(points);

julia> typeof(hull)
Array{Array{Float64,1},1}

Plot both the random points and the computed convex hull polygon:

julia> using Plots;

julia> plot([Tuple(pi) for pi in points], seriestype=:scatter);

julia> plot!(VPolygon(hull), alpha=0.2);

monotone_chain!(points::Vector{VN}; sort::Bool=true
               )::Vector{VN} where {N<:Real, VN<:AbstractVector{N}}

Compute the convex hull of points in the plane using Andrew's monotone chain method.

Input

• points – list of 2D vectors; is sorted in-place inside this function
• sort – (optional, default: true) flag for sorting the vertices lexicographically; sortedness is required for correctness

Output

List of vectors containing the 2D coordinates of the corner points of the convex hull.

Notes

For large sets of points, it is convenient to use static vectors to get maximum performance. For information on how to convert usual vectors into static vectors, see the type SVector provided by the StaticArrays package.

Algorithm

This function implements Andrew's monotone chain convex hull algorithm to construct the convex hull of a set of $n$ points in the plane in $O(n \log n)$ time. For further details see Monotone chain

Intersection{N<:Real, S1<:LazySet{N}, S2<:LazySet{N}} <: LazySet{N}

Type that represents the intersection of two convex sets.

Fields

• X – convex set
• Y – convex set
• cache – internal cache for avoiding recomputation; see IntersectionCache

Examples

Create an expression, $Z$, which lazily represents the intersection of two squares $X$ and $Y$:

julia> X, Y = BallInf([0,0.], 0.5), BallInf([1,0.], 0.65);

julia> Z = X ∩ Y;

julia> typeof(Z)
Intersection{Float64,BallInf{Float64},BallInf{Float64}}

julia> dim(Z)
2

We can check if the intersection is empty with isempty:

julia> isempty(Z)
false

Do not confuse Intersection with the concrete operation, which is computed with the lowercase intersection function:

julia> W = intersection(X, Y)
Hyperrectangle{Float64}([0.425, 0.0], [0.075, 0.5])

∩

Alias for Intersection.

dim(cap::Intersection)::Int

Return the dimension of an intersection of two convex sets.

Input

• cap – intersection of two convex sets

Output

The ambient dimension of the intersection of two convex sets.

ρ(d::AbstractVector{N}, cap::Intersection{N}) where {N<:Real}

Return an upper bound on the support function of the intersection of two convex sets in a given direction.

Input

• d – direction
• cap – intersection of two convex sets

Output

An uper bound on the support function in the given direction.

Algorithm

The support function of an intersection of $X$ and $Y$ is upper bounded by the minimum of the support functions of $X$ and $Y$.

ρ(d::AbstractVector{N},
  cap::Intersection{N, S1, S2};
  [algorithm]::String="line_search",
  [kwargs...]) where {N<:Real,
                      S1<:LazySet{N},
                      S2<:Union{HalfSpace{N}, Hyperplane{N}, Line{N}}}

Return the support function of the intersection of a compact set and a half-space/hyperplane/line in a given direction.

Input

• d – direction

• cap – lazy intersection of a compact set and a half-space/hyperplane/ line

• algorithm – (optional, default: "line_search"): the algorithm to calculate the support function; valid options are:

  • "line_search" – solve the associated univariate optimization problem using a line search method (either Brent or the Golden Section method)
  • "projection" – only valid for intersection with a hyperplane; evaluates the support function by reducing the problem to the 2D intersection of a rank 2 linear transformation of the given compact set in the plane generated by the given direction d and the hyperplane's normal vector n
  • "simple" – take the $\min$ of the support function evaluation of each operand

Output

The scalar value of the support function of the set cap in the given direction.

Notes

It is assumed that the set cap.X is compact.

Any additional number of arguments to the algorithm backend can be passed as keyword arguments.

Algorithm

The algorithms are based on solving the associated optimization problem

where $D_h = \{ λ : λ ≥ 0 \}$ if $H$ is a half-space or $D_h = \{ λ : λ ∈ \mathbb{R} \}$ if $H$ is a hyperplane.

For additional information we refer to:

• G. Frehse, R. Ray. Flowpipe-Guard Intersection for Reachability Computations with Support Functions.
• C. Le Guernic. Reachability Analysis of Hybrid Systems with Linear Continuous Dynamics, PhD thesis.
• T. Rockafellar, R. Wets. Variational Analysis.

ρ(d::AbstractVector{N}, cap::Intersection{N, S1, S2}; kwargs...)
    where {N<:Real, S1<:LazySet{N}, S2<:AbstractPolyhedron{N}}

Return an upper bound of the intersection between a compact set and a polyhedron along a given direction.

Input

• d – direction
• cap – intersection of a compact set and a polyhedron
• kwargs – additional arguments that are passed to the support-function algorithm

Output

An upper bound of the support function of the given intersection.

Algorithm

The idea is to solve the univariate optimization problem ρ(di, X ∩ Hi) for each half-space in the set P and then take the minimum. This gives an overapproximation of the exact support function.

This algorithm is inspired from G. Frehse, R. Ray. Flowpipe-Guard Intersection for Reachability Computations with Support Functions.

Notes

This method relies on the constraints_list of the polyhedron.

σ(d::AbstractVector{N}, cap::Intersection{N}) where {N<:Real}

Return the support vector of an intersection of two convex sets in a given direction.

Input

• d – direction
• cap – intersection of two convex sets

Output

The support vector in the given direction.

isbounded(cap::Intersection)::Bool

Determine whether an intersection of two convex sets is bounded.

Input

• cap – intersection of two convex sets

Output

true iff the intersection is bounded.

Algorithm

We first check if any of the wrapped sets is bounded. Otherwise, we check boundedness via isbounded_unit_dimensions.

isempty(cap::Intersection)::Bool

Return if the intersection is empty or not.

Input

• cap – intersection of two convex sets

Output

true iff the intersection is empty.

Notes

The result will be cached, so a second query will be fast.

∈(x::AbstractVector{N}, cap::Intersection{N})::Bool where {N<:Real}

Check whether a given point is contained in an intersection of two convex sets.

Input

• x – point/vector
• cap – intersection of two convex sets

Output

true iff $x ∈ cap$.

constraints_list(cap::Intersection{N}) where {N<:Real}

Return the list of constraints of an intersection of two (polyhedral) sets.

Input

• cap – intersection of two (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 by taking the intersection of the constraints_lists of the sets and remove redundant constraints.

This function ignores the boolean output from the in-place remove_redundant_constraints!, which may inform the user that the constraints are infeasible. In that case, the list of constraints at the moment when the infeasibility was detected is returned.

isempty_known(cap::Intersection)

Ask whether the status of emptiness is known.

Input

• cap – intersection of two convex sets

Output

true iff the emptiness status is known. In this case, isempty(cap) can be used to obtain the status.

set_isempty!(cap::Intersection, isempty::Bool)

Set the status of emptiness in the cache.

Input

• cap – intersection of two convex sets
• isempty – new status of emptiness

swap(cap::Intersection{N, S1, S2}) where {N<:Real, S1, S2}

Return a new Intersection object with the arguments swapped.

Input

• cap – intersection of two convex sets

Output

A new Intersection object with the arguments swapped. The old cache is shared between the old and new objects.

Notes

The advantage of using this function instead of manually swapping the arguments is that the cache is shared.

use_precise_ρ(cap::Intersection{N})::Bool where {N<:Real}

Determine whether a precise algorithm for computing $ρ$ shall be applied.

Input

• cap – intersection of two convex sets

Output

true if a precise algorithm shall be applied.

Notes

The default implementation always returns true.

If the result is false, a coarse approximation of the support function is returned.

This function can be overwritten by the user to control the policy.

_line_search(ℓ, X, H; [kwargs...])

Given a compact and convex set $X$ and a halfspace $H = \{x: a^T x ≤ b \}$ or a hyperplane $H = \{x: a^T x = b \}$, calculate:

where $D_h = \{ λ : λ ≥ 0 \}$ if $H$ is a half-space or $D_h = \{ λ : λ ∈ \mathbb{R} \}$ if $H$ is a hyperplane.

Input

• ℓ – direction
• X – set
• H – halfspace or hyperplane

Output

The tuple (fmin, λmin), where fmin is the minimum value of the function $f(λ) = ρ(ℓ - λa) + λb$ over the feasible set $λ ≥ 0$, and $λmin$ is the minimizer.

Notes

This function requires the Optim package, and relies on the univariate optimization interface Optim.optimize(...).

Additional arguments to the optimize backend can be passed as keyword arguments. The default method is Optim.Brent().

Examples

julia> X = Ball1(zeros(2), 1.0);

julia> H = HalfSpace([-1.0, 0.0], -1.0); # x >= 0 

julia> using Optim

julia> using LazySets: _line_search

julia> _line_search([1.0, 0.0], X, H) # uses Brent's method by default
(1.0, 999999.9849478417)

We can specify the upper bound in Brent's method:

julia> _line_search([1.0, 0.0], X, H, upper=1e3)
(1.0, 999.9999849478418)

Instead of using Brent, we use the Golden Section method:

julia> _line_search([1.0, 0.0], X, H, upper=1e3, method=GoldenSection())
(1.0, 381.9660112501051)

_projection(ℓ, X, H::Union{Hyperplane{N}, Line{N}};
            [lazy_linear_map]=false,
            [lazy_2d_intersection]=true,
            [algorithm_2d_intersection]=nothing,
            [kwargs...]) where {N}

Given a compact and convex set $X$ and a hyperplane $H = \{x: n ⋅ x = γ \}$, calculate the support function of the intersection between the rank-2 projection $Π_{nℓ} X$ and the line $Lγ = \{(x, y): x = γ \}$.

Input

• ℓ – direction
• X – set
• H – hyperplane
• lazy_linear_map – (optional, default: false) to perform the projection lazily or concretely
• lazy_2d_intersection – (optional, default: true) to perform the 2D intersection between the projected set and the line lazily or concretely
• algorithm_2d_intersection – (optional, default: nothing) if given, fixes the support function algorithm used for the intersection in 2D; otherwise the default is implied

Output

The support function of $X ∩ H$ along direction $ℓ$.

Algorithm

This projection method is based on Prop. 8.2, page 103, C. Le Guernic. Reachability Analysis of Hybrid Systems with Linear Continuous Dynamics, PhD thesis.

In the original algorithm, Section 8.2 of Le Guernic's thesis, the linear map is performed concretely and the intersection is performed lazily (these are the default options in this algorithm, but here the four combinations are available). If the set $X$ is a zonotope, its concrete projection is again a zonotope (sometimes called "zonogon"). The intersection between this zonogon and the line can be taken efficiently in a lazy way (see Section 8.2.2 of Le Guernic's thesis), if one uses dispatch on ρ(y_dir, Sℓ⋂Lγ; kwargs...) given that Sℓ is itself a zonotope.

Notes

This function depends itself on the calculation of the support function of another set in two dimensions. Obviously one doesn't want to use again algorithm="projection" for this second calculation. The option algorithm_2d_intersection is such that, if it is not given, the default support function algorithm is used (e.g. "line_search"). You can still pass additional arguments to the "line_search" backend through the kwargs.

linear_map(M::AbstractMatrix{N}, cap::Intersection{N}) where {N}

Return the concrete linear map of a lazy intersection.

Input

• M – matrix
• cap – lazy intersection

Output

The set obtained by applying the given linear map to the lazy intersection.

Notes

This function relies on computing cap concretely (i.e. as a set representation), and then applying the linear map.

plot_recipe(cap::Intersection{N}, [ε]::N=-one(N),
            [Nφ]::Int=PLOT_POLAR_DIRECTIONS) where {N<:Real}

Convert a lazy intersection to a pair (x, y) of points for plotting.

Input

• cap – lazy intersection
• ε – (optional, default 0) ignored, used for dispatch
• Nφ – (optional, default: PLOT_POLAR_DIRECTIONS) number of polar directions used in the template overapproximation

Output

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

plot_intersection(cap::Intersection{N}, [ε]::N=zero(N),
                  [Nφ]::Int=PLOT_POLAR_DIRECTIONS) where {N<:Real}

Plot a lazy intersection.

Input

• cap – lazy intersection
• ε – (optional, default 0) ignored, used for dispatch
• Nφ – (optional, default: PLOT_POLAR_DIRECTIONS) number of polar directions used in the template overapproximation

Notes

This function is separated from the main LazySet plot recipe because iterative refinement is not available for lazy intersections (since it uses the support vector (but see #1187)).

Also note that if the set is a nested intersection, you may have to manually overapproximate this set before plotting (see LazySets.Approximations.overapproximate for details).

Examples

julia> using LazySets.Approximations

julia> X = Ball2(zeros(2), 1.) ∩ Ball2(ones(2), 1.5);  # lazy intersection

julia> plot(X)

You can specify the accuracy of the overapproximation of the lazy intersection by passing a higher value for Nφ, which stands for the number of polar directions used in the overapproximation. This number can also be passed to the plot function directly.

julia> plot(overapproximate(X, PolarDirections(100)))

julia> plot(X, -1., 100)  # equivalent to the above line

IntersectionCache

Container for information cached by a lazy Intersection object.

Fields

• isempty – is the intersection empty? There are three possible states, encoded as Int8 values -1, 0, 1:

  • $-1$ - it is currently unknown whether the intersection is empty or not
  • $0$ - intersection is not empty
  • $1$ - intersection is empty

IntersectionArray{N<:Real, S<:LazySet{N}} <: LazySet{N}

Type that represents the intersection of a finite number of convex sets.

Fields

• array – array of convex sets

Notes

This type assumes that the dimensions of all elements match.

The EmptySet is the absorbing element for IntersectionArray.

Constructors:

• IntersectionArray(array::Vector{<:LazySet}) – default constructor

• IntersectionArray([n]::Int=0, [N]::Type=Float64) – constructor for an empty sum with optional size hint and numeric type

dim(ia::IntersectionArray)::Int

Return the dimension of an intersection of a finite number of sets.

Input

• ia – intersection of a finite number of convex sets

Output

The ambient dimension of the intersection of a finite number of sets.

σ(d::AbstractVector{N}, ia::IntersectionArray{N})::Vector{N} where {N<:Real}

Return the support vector of an intersection of a finite number of sets in a given direction.

Input

• d – direction
• ia – intersection of a finite number of convex sets

Output

The support vector in the given direction. If the direction has norm zero, the result depends on the individual sets.

isbounded(ia::IntersectionArray)::Bool

Determine whether an intersection of a finite number of convex sets is bounded.

Input

• ia – intersection of a finite number of convex sets

Output

true iff the intersection is bounded.

Algorithm

We first check if any of the wrapped sets is bounded. Otherwise, we check boundedness via isbounded_unit_dimensions.

∈(x::AbstractVector{N}, ia::IntersectionArray{N})::Bool where {N<:Real}

Check whether a given point is contained in an intersection of a finite number of convex sets.

Input

• x – point/vector
• ia – intersection of a finite number of convex sets

Output

true iff $x ∈ ia$.

array(cpa::CartesianProductArray{N, S}
     )::Vector{S} where {N<:Real, S<:LazySet{N}}

Return the array of a Cartesian product of a finite number of convex sets.

Input

• cpa – Cartesian product array

Output

The array of a Cartesian product of a finite number of convex sets.

array(cha::ConvexHullArray{N, S})::Vector{S} where {N<:Real, S<:LazySet{N}}

Return the array of a convex hull of a finite number of convex sets.

Input

• cha – convex hull array

Output

The array of a convex hull of a finite number of convex sets.

array(ia::IntersectionArray{N, S})::Vector{S} where {N<:Real, S<:LazySet{N}}

Return the array of an intersection of a finite number of convex sets.

Input

• ia – intersection of a finite number of convex sets

Output

The array of an intersection of a finite number of convex sets.

array(msa::MinkowskiSumArray{N, S})::Vector{S} where {N<:Real, S<:LazySet{N}}

Return the array of a Minkowski sum of a finite number of convex sets.

Input

• msa – Minkowski sum array

Output

The array of a Minkowski sum of a finite number of convex sets.

array(cms::CacheMinkowskiSum{N, S})::Vector{S} where {N<:Real, S<:LazySet{N}}

Return the array of a caching Minkowski sum.

Input

• cms – caching Minkowski sum

Output

The array of a caching Minkowski sum.

array(cup::UnionSetArray{N, S})::Vector{S} where {N<:Real, S<:LazySet{N}}

Return the array of a union of a finite number of convex sets.

Input

• cup – union of a finite number of convex sets

Output

The array that holds the union of a finite number of convex sets.

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

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.

MinkowskiSum{N<:Real, S1<:LazySet{N}, S2<:LazySet{N}} <: LazySet{N}

Type that represents the Minkowski sum of two convex sets.

Fields

• X – first convex set
• Y – second convex set

Notes

The ZeroSet is the neutral element and the EmptySet is the absorbing element for MinkowskiSum.

⊕(X::LazySet, Y::LazySet)

Unicode alias constructor ⊕ (oplus) for the lazy Minkowski sum operator.

X + Y

Convenience constructor for Minkowski sum.

Input

• X – a convex set
• Y – another convex set

Output

The symbolic Minkowski sum of $X$ and $Y$.

swap(ms::MinkowskiSum)

Return a new MinkowskiSum object with the arguments swapped.

Input

• ms – Minkowski sum of two convex sets

Output

A new MinkowskiSum object with the arguments swapped.

dim(ms::MinkowskiSum)::Int

Return the dimension of a Minkowski sum.

Input

• ms – Minkowski sum

Output

The ambient dimension of the Minkowski sum.

ρ(d::AbstractVector{N}, ms::MinkowskiSum{N}) where {N<:Real}

Return the support function of a Minkowski sum.

Input

• d – direction
• ms – Minkowski sum

Output

The support function in the given direction.

Algorithm

The support function in direction $d$ of the Minkowski sum of two sets $X$ and $Y$ is the sum of the support functions of $X$ and $Y$ in direction $d$.

σ(d::AbstractVector{N}, ms::MinkowskiSum{N}) where {N<:Real}

Return the support vector of a Minkowski sum.

Input

• d – direction
• ms – Minkowski sum

Output

The support vector in the given direction. If the direction has norm zero, the result depends on the summand sets.

Algorithm

The support vector in direction $d$ of the Minkowski sum of two sets $X$ and $Y$ is the sum of the support vectors of $X$ and $Y$ in direction $d$.

isbounded(ms::MinkowskiSum)::Bool

Determine whether a Minkowski sum is bounded.

Input

• ms – Minkowski sum

Output

true iff both wrapped sets are bounded.

isempty(ms::MinkowskiSum)::Bool

Return if a Minkowski sum is empty or not.

Input

• ms – Minkowski sum

Output

true iff any of the wrapped sets are empty.

constraints_list(ms::MinkowskiSum)

Return the list of constraints of a lazy Minkowski sum of two polyhedral sets.

Input

• ms – Minkowski sum of two polyhedral sets

Output

The list of constraints of the Minkowski sum.

Algorithm

We compute a concrete set representation via minkowski_sum and call constraints_list on the result.

MinkowskiSumArray{N<:Real, S<:LazySet{N}} <: LazySet{N}

Type that represents the Minkowski sum of a finite number of convex sets.

Fields

• array – array of convex sets

Notes

This type assumes that the dimensions of all elements match.

The ZeroSet is the neutral element and the EmptySet is the absorbing element for MinkowskiSumArray.

Constructors:

• MinkowskiSumArray(array::Vector{<:LazySet}) – default constructor

• MinkowskiSumArray([n]::Int=0, [N]::Type=Float64) – constructor for an empty sum with optional size hint and numeric type

dim(msa::MinkowskiSumArray)::Int

Return the dimension of a Minkowski sum of a finite number of sets.

Input

• msa – Minkowski sum array

Output

The ambient dimension of the Minkowski sum of a finite number of sets.

ρ(d::AbstractVector{N}, msa::MinkowskiSumArray{N}) where {N<:Real}

Return the support function of a Minkowski sum array of a finite number of sets in a given direction.

Input

• d – direction
• msa – Minkowski sum array

Output

The support function in the given direction.

Algorithm

The support function of the Minkowski sum of sets is the sum of the support functions of each set.

σ(d::AbstractVector{N}, msa::MinkowskiSumArray{N}) where {N<:Real}

Return the support vector of a Minkowski sum of a finite number of sets in a given direction.

Input

• d – direction
• msa – Minkowski sum array

Output

The support vector in the given direction. If the direction has norm zero, the result depends on the summand sets.

isbounded(msa::MinkowskiSumArray)::Bool

Determine whether a Minkowski sum of a finite number of convex sets is bounded.

Input

• msa – Minkowski sum of a finite number of convex sets

Output

true iff all wrapped sets are bounded.

isempty(msa::MinkowskiSumArray)::Bool

Return if a Minkowski sum array is empty or not.

Input

• msa – Minkowski sum array

Output

true iff any of the wrapped sets are empty.

array(cpa::CartesianProductArray{N, S}
     )::Vector{S} where {N<:Real, S<:LazySet{N}}

Return the array of a Cartesian product of a finite number of convex sets.

Input

• cpa – Cartesian product array

Output

The array of a Cartesian product of a finite number of convex sets.

array(cha::ConvexHullArray{N, S})::Vector{S} where {N<:Real, S<:LazySet{N}}

Return the array of a convex hull of a finite number of convex sets.

Input

• cha – convex hull array

Output

The array of a convex hull of a finite number of convex sets.

array(ia::IntersectionArray{N, S})::Vector{S} where {N<:Real, S<:LazySet{N}}

Return the array of an intersection of a finite number of convex sets.

Input

• ia – intersection of a finite number of convex sets

Output

The array of an intersection of a finite number of convex sets.

array(msa::MinkowskiSumArray{N, S})::Vector{S} where {N<:Real, S<:LazySet{N}}

Return the array of a Minkowski sum of a finite number of convex sets.

Input

• msa – Minkowski sum array

Output

The array of a Minkowski sum of a finite number of convex sets.

array(cms::CacheMinkowskiSum{N, S})::Vector{S} where {N<:Real, S<:LazySet{N}}

Return the array of a caching Minkowski sum.

Input

• cms – caching Minkowski sum

Output

The array of a caching Minkowski sum.

array(cup::UnionSetArray{N, S})::Vector{S} where {N<:Real, S<:LazySet{N}}

Return the array of a union of a finite number of convex sets.

Input

• cup – union of a finite number of convex sets

Output

The array that holds the union of a finite number of convex sets.

CacheMinkowskiSum{N<:Real, S<:LazySet{N}} <: LazySet{N}

Type that represents the Minkowski sum of a finite number of convex sets. Support vector queries are cached.

Fields

• array – array of convex sets
• cache – cache of support vector query results

Notes

This type assumes that the dimensions of all elements match.

The ZeroSet is the neutral element and the EmptySet is the absorbing element for CacheMinkowskiSum.

The cache (field cache) is implemented as dictionary whose keys are directions and whose values are pairs (k, s) where k is the number of elements in the array array when the support vector was evaluated last time, and s is the support vector that was obtained. Thus this type assumes that array is not modified except by adding new sets at the end.

Constructors:

• CacheMinkowskiSum(array::Vector{<:LazySet}) – default constructor

• CacheMinkowskiSum([n]::Int=0, [N]::Type=Float64) – constructor for an empty sum with optional size hint and numeric type

dim(cms::CacheMinkowskiSum)::Int

Return the dimension of a caching Minkowski sum.

Input

• cms – caching Minkowski sum

Output

The ambient dimension of the caching Minkowski sum.

σ(d::AbstractVector{N}, cms::CacheMinkowskiSum{N}) where {N<:Real}

Return the support vector of a caching Minkowski sum in a given direction.

Input

• d – direction
• cms – caching Minkowski sum

Output

The support vector in the given direction. If the direction has norm zero, the result depends on the summand sets.

Notes

The result is cached, i.e., any further query with the same direction runs in constant time. When sets are added to the caching Minkowski sum, the query is only performed for the new sets.

isbounded(cms::CacheMinkowskiSum)::Bool

Determine whether a caching Minkowski sum is bounded.

Input

• cms – caching Minkowski sum

Output

true iff all wrapped sets are bounded.

isempty(cms::CacheMinkowskiSum)::Bool

Return if a caching Minkowski sum array is empty or not.

Input

• cms – caching Minkowski sum

Output

true iff any of the wrapped sets are empty.

Notes

Forgotten sets cannot be checked anymore. Usually they have been empty because otherwise the support vector query should have crashed before. In that case, the caching Minkowski sum should not be used further.

array(cpa::CartesianProductArray{N, S}
     )::Vector{S} where {N<:Real, S<:LazySet{N}}

Return the array of a Cartesian product of a finite number of convex sets.

Input

• cpa – Cartesian product array

Output

The array of a Cartesian product of a finite number of convex sets.

array(cha::ConvexHullArray{N, S})::Vector{S} where {N<:Real, S<:LazySet{N}}

Return the array of a convex hull of a finite number of convex sets.

Input

• cha – convex hull array

Output

The array of a convex hull of a finite number of convex sets.

array(ia::IntersectionArray{N, S})::Vector{S} where {N<:Real, S<:LazySet{N}}

Return the array of an intersection of a finite number of convex sets.

Input

• ia – intersection of a finite number of convex sets

Output

The array of an intersection of a finite number of convex sets.

array(msa::MinkowskiSumArray{N, S})::Vector{S} where {N<:Real, S<:LazySet{N}}

Return the array of a Minkowski sum of a finite number of convex sets.

Input

• msa – Minkowski sum array

Output

The array of a Minkowski sum of a finite number of convex sets.

array(cms::CacheMinkowskiSum{N, S})::Vector{S} where {N<:Real, S<:LazySet{N}}

Return the array of a caching Minkowski sum.

Input

• cms – caching Minkowski sum

Output

The array of a caching Minkowski sum.

array(cup::UnionSetArray{N, S})::Vector{S} where {N<:Real, S<:LazySet{N}}

Return the array of a union of a finite number of convex sets.

Input

• cup – union of a finite number of convex sets

Output

The array that holds the union of a finite number of convex sets.

forget_sets!(cms::CacheMinkowskiSum)::Int

Tell a caching Minkowski sum to forget the stored sets (but not the support vectors). Only those sets are forgotten such that for each cached direction the support vector has been computed before.

Input

• cms – caching Minkowski sum

Output

The number of sets that have been forgotten.

Notes

This function should only be used under the assertion that no new directions are queried in the future; otherwise such support vector results will be incorrect.

This implementation is optimistic and first tries to remove all sets. However, it also checks that for all cached directions the support vector has been computed before. If it finds that this is not the case, the implementation identifies the biggest index $k$ such that the above holds for the $k$ oldest sets, and then it only removes these. See the example below.

Examples

julia> x1 = BallInf(ones(3), 3.); x2 = Ball1(ones(3), 5.);

julia> cms1 = CacheMinkowskiSum(2); cms2 = CacheMinkowskiSum(2);

julia> d = ones(3);

julia> a1 = array(cms1); a2 = array(cms2);

julia> push!(a1, x1); push!(a2, x1);

julia> σ(d, cms1); σ(d, cms2);

julia> push!(a1, x2); push!(a2, x2);

julia> σ(d, cms1);

julia> idx1 = forget_sets!(cms1) # support vector was computed for both sets
2

julia> idx1 = forget_sets!(cms2) # support vector was only computed for first set
1

LinearMap{N<:Real, S<:LazySet{N}, NM, MAT<:AbstractMatrix{NM}} <: LazySet{N}

Type that represents a linear transformation $M⋅S$ of a convex set $S$.

Fields

• M – matrix/linear map
• X – convex set

Notes

This type is parametric in the elements of the linear map, NM, which is independent of the numeric type of the wrapped set (N). Typically NM = N, but there may be exceptions, e.g., if NM is an interval that holds numbers of type N, where N is a floating point number type such as Float64.

    *(M::AbstractMatrix{N}, X::LazySet{N}) where {N<:Real}

Return the linear map of a convex set.

Input

• M – matrix/linear map
• X – convex set

Output

A lazy linear map, i.e. a LinearMap instance.

    *(α::N, X::LazySet{N}) where {N<:Real}

Return the linear map of a convex set scaled by a given number.

Input

• α – scalar
• X – convex set

Output

The lazy linear map of the convex set, X ↦ M * X, such that M is a sparse matrix proportional to the identity and whose non-zero entries equal α.

    *(α::N, lm::LinearMap{N}) where {N<:Real, LM<:LinearMap{N}}

Return the linear map scaled by a given value.

Input

• α – scalar
• lm – linear map

Output

The scaled linear map.

dim(lm::LinearMap)::Int

Return the dimension of a linear map.

Input

• lm – linear map

Output

The ambient dimension of the linear map.

ρ(d::AbstractVector{N}, lm::LinearMap{N}; kwargs...) where {N<:Real}

Return the support function of the linear map.

Input

• d – direction
• lm – linear map
• kwargs – additional arguments that are passed to the support function algorithm

Output

The support function in the given direction. If the direction has norm zero, the result depends on the wrapped set.

Notes

If $L = M⋅S$, where $M$ is a matrix and $S$ is a convex set, it follows that $ρ(d, L) = ρ(M^T d, S)$ for any direction $d$.

σ(d::AbstractVector{N}, lm::LinearMap{N}) where {N<:Real}

Return the support vector of the linear map.

Input

• d – direction
• lm – linear map

Output

The support vector in the given direction. If the direction has norm zero, the result depends on the wrapped set.

Notes

If $L = M⋅S$, where $M$ is a matrix and $S$ is a convex set, it follows that $σ(d, L) = M⋅σ(M^T d, S)$ for any direction $d$.

∈(x::AbstractVector{N}, lm::LinearMap{N})::Bool where {N<:Real}

Check whether a given point is contained in a linear map of a convex set.

Input

• x – point/vector
• lm – linear map of a convex set

Output

true iff $x ∈ lm$.

Algorithm

Note that $x ∈ M⋅S$ iff $M^{-1}⋅x ∈ S$. This implementation does not explicitly invert the matrix, which is why it also works for non-square matrices.

Examples

julia> lm = LinearMap([2.0 0.0; 0.0 1.0], BallInf([1., 1.], 1.));

julia> [5.0, 1.0] ∈ lm
false
julia> [3.0, 1.0] ∈ lm
true

An example with non-square matrix:

julia> B = BallInf(zeros(4), 1.);

julia> M = [1. 0 0 0; 0 1 0 0]/2;

julia> [0.5, 0.5] ∈ M*B
true

an_element(lm::LinearMap{N})::Vector{N} where {N<:Real}

Return some element of a linear map.

Input

• lm – linear map

Output

An element in the linear map. It relies on the an_element function of the wrapped set.

isbounded(lm::LinearMap; cond_tol::Number=DEFAULT_COND_TOL)::Bool

Determine whether a linear map is bounded.

Input

• lm – linear map
• cond_tol – (optional) tolerance of matrix condition (used to check whether the matrix is invertible)

Output

true iff the linear map is bounded.

Algorithm

We first check if the matrix is zero or the wrapped set is bounded. If not, we perform a sufficient check whether the matrix is invertible. If the matrix is invertible, then the map being bounded is equivalent to the wrapped set being bounded, and hence the map is unbounded. Otherwise, we check boundedness via isbounded_unit_dimensions.

isempty(lm::LinearMap)::Bool

Return if a linear map is empty or not.

Input

• lm – linear map

Output

true iff the wrapped set is empty.

vertices_list(lm::LinearMap{N}; prune::Bool=true)::Vector{Vector{N}} where {N<:Real}

Return the list of vertices of a (polyhedral) linear map.

Input

• lm – linear map
• prune – (optional, default: true) if true removes redundant vertices

Output

A list of vertices.

Algorithm

We assume that the underlying set X is polyhedral. Then the result is just the linear map applied to the vertices of X.

constraints_list(lm::LinearMap{N}) where {N<:Real}

Return the list of constraints of a (polyhedral) linear map.

Input

• lm – linear map

Output

The list of constraints of the linear map.

Notes

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

Algorithm

We fall back to a concrete set representation and apply linear_map.

linear_map(M::AbstractMatrix{N}, lm::LinearMap{N}) where {N<:Real}

Return the linear map of a lazy linear map.

Input

• M – matrix
• lm – linear map

Output

The polytope representing the linear map of the lazy linear map of a set.

ExponentialMap{N<:Real, S<:LazySet{N}} <: LazySet{N}

Type that represents the action of an exponential map on a convex set.

Fields

• spmexp – sparse matrix exponential
• X – convex set

Examples

The ExponentialMap type is overloaded to the usual times * operator when the linear map is a lazy matrix exponential. For instance,

julia> using SparseArrays

julia> A = sprandn(100, 100, 0.1);

julia> E = SparseMatrixExp(A);

julia> B = BallInf(zeros(100), 1.);

julia> M = E * B; # represents the image set: exp(A) * B

julia> M isa ExponentialMap
true

julia> dim(M)
100

dim(em::ExponentialMap)::Int

Return the dimension of an exponential map.

Input

• em – an ExponentialMap

Output

The ambient dimension of the exponential map.

ρ(d::AbstractVector{N}, em::ExponentialMap{N}) where {N<:Real}

Return the support function of the exponential map.

Input

• d – direction
• em – exponential map

Output

The support function in the given direction.

Notes

If $E = \exp(M)⋅S$, where $M$ is a matrix and $S$ is a convex set, it follows that $ρ(d, E) = ρ(\exp(M)^T d, S)$ for any direction $d$.

We allow sparse direction vectors, but will convert them to dense vectors to be able to use expmv.

σ(d::AbstractVector{N}, em::ExponentialMap{N}) where {N<:Real}

Return the support vector of the exponential map.

Input

• d – direction
• em – exponential map

Output

The support vector in the given direction. If the direction has norm zero, the result depends on the wrapped set.

Notes

If $E = \exp(M)⋅S$, where $M$ is a matrix and $S$ is a convex set, it follows that $σ(d, E) = \exp(M)⋅σ(\exp(M)^T d, S)$ for any direction $d$.

We allow sparse direction vectors, but will convert them to dense vectors to be able to use expmv.

∈(x::AbstractVector{N}, em::ExponentialMap{N})::Bool where {N<:Real}

Check whether a given point is contained in an exponential map of a convex set.

Input

• x – point/vector
• em – exponential map of a convex set

Output

true iff $x ∈ em$.

Algorithm

This implementation exploits that $x ∈ \exp(M)⋅S$ iff $\exp(-M)⋅x ∈ S$. This follows from $\exp(-M)⋅\exp(M) = I$ for any $M$.

Examples

julia> using SparseArrays

julia> em = ExponentialMap(
        SparseMatrixExp(sparse([1, 2], [1, 2], [2.0, 1.0], 2, 2)),
        BallInf([1., 1.], 1.));

julia> [-1.0, 1.0] ∈ em
false
julia> [1.0, 1.0] ∈ em
true

isbounded(em::ExponentialMap)::Bool

Determine whether an exponential map is bounded.

Input

• em – exponential map

Output

true iff the exponential map is bounded.

isempty(em::ExponentialMap)::Bool

Return if an exponential map is empty or not.

Input

• em – exponential map

Output

true iff the wrapped set is empty.

vertices_list(em::ExponentialMap{N})::Vector{Vector{N}} where {N<:Real}

Return the list of vertices of a (polytopic) exponential map.

Input

• em – exponential map

Output

A list of vertices.

Algorithm

We assume that the underlying set X is polytopic. Then the result is just the exponential map applied to the vertices of X.

ExponentialProjectionMap{N<:Real, S<:LazySet{N}} <: LazySet{N}

Type that represents the application of a projection of a sparse matrix exponential to a convex set.

Fields

• spmexp – projection of a sparse matrix exponential
• X – convex set

dim(eprojmap::ExponentialProjectionMap)::Int

Return the dimension of a projection of an exponential map.

Input

• eprojmap – projection of an exponential map

Output

The ambient dimension of the projection of an exponential map.

σ(d::AbstractVector{N},
  eprojmap::ExponentialProjectionMap{N}) where {N<:Real}

Return the support vector of a projection of an exponential map.

Input

• d – direction
• eprojmap – projection of an exponential map

Output

The support vector in the given direction. If the direction has norm zero, the result depends on the wrapped set.

Notes

If $S = (L⋅M⋅R)⋅X$, where $L$ and $R$ are matrices, $M$ is a matrix exponential, and $X$ is a set, it follows that $σ(d, S) = L⋅M⋅R⋅σ(R^T⋅M^T⋅L^T⋅d, X)$ for any direction $d$.

We allow sparse direction vectors, but will convert them to dense vectors to be able to use expmv.

isbounded(eprojmap::ExponentialProjectionMap)::Bool

Determine whether an exponential projection map is bounded.

Input

• eprojmap – exponential projection map

Output

true iff the exponential projection map is bounded.

Algorithm

We first check if the left or right projection matrix is zero or the wrapped set is bounded. Otherwise, we check boundedness via isbounded_unit_dimensions.

isempty(eprojmap::ExponentialProjectionMap)::Bool

Return if an exponential projection map is empty or not.

Input

• eprojmap – exponential projection map

Output

true iff the wrapped set is empty.

SparseMatrixExp{N}

Type that represents the matrix exponential, $\exp(M)$, of a sparse matrix.

Fields

• M – sparse matrix

Examples

Take for exammple a random sparse matrix:

julia> using SparseArrays

julia> A = sprandn(100, 100, 0.1);

julia> E = SparseMatrixExp(A);

julia> size(E)
(100, 100)

Now, E is a lazy representation of $\exp(A)$. To compute with E, use get_row and get_column (or get_rows and get_columns; they return row and column vectors (or matrices). For example:

julia> get_row(E, 10); # compute E[10, :]

julia> get_column(E, 10); # compute E[:, 10]

julia> get_rows(E, [10]); # same as get_row(E, 10) but a 1x100 matrix is returned

julia> get_columns(E, [10]); # same as get_column(E, 10) but a 100x1 matrix is returned

Notes

This type is provided for use with very large and very sparse matrices. The evaluation of the exponential matrix action over vectors relies on the Expokit package.

    *(spmexp::SparseMatrixExp{N},
      X::LazySet{N})::ExponentialMap{N} where {N<:Real}

Return the exponential map of a convex set from a sparse matrix exponential.

Input

• spmexp – sparse matrix exponential
• X – convex set

Output

The exponential map of the convex set.

get_row(spmexp::SparseMatrixExp{N}, i::Int) where {N}

Return a single row of a sparse matrix exponential.

Input

• spmexp – sparse matrix exponential
• i – row index

Output

A row vector corresponding to the ith row of the matrix exponential.

Notes

This function uses Julia's transpose function to create the result. The result is of type Transpose; in Julia versions older than v0.7, the result was of type RowVector.

ProjectionSparseMatrixExp{N<:Real}

Type that represents the projection of a sparse matrix exponential, i.e., $L⋅\exp(M)⋅R$ for a given sparse matrix $M$.

Fields

• L – left multiplication matrix
• E – sparse matrix exponential
• R – right multiplication matrix

    *(projspmexp::ProjectionSparseMatrixExp,
      X::LazySet)::ExponentialProjectionMap

Return the application of a projection of a sparse matrix exponential to a convex set.

Input

• projspmexp – projection of a sparse matrix exponential
• X – convex set

Output

The application of the projection of a sparse matrix exponential to the convex set.

ResetMap{N<:Real, S<:LazySet{N}} <: LazySet{N}

Type that represents a lazy reset map. A reset map is a special case of an affine map $A x + b, x ∈ X$ where the linear map $A$ is the identity matrix with zero entries in all reset dimensions, and the translation vector $b$ is zero in all other dimensions.

Fields

• X – convex set
• resets – resets (a mapping from an index to a new value)

Example

julia> X = BallInf([2.0, 2.0, 2.0], 1.0);

julia> r = Dict(1 => 4.0, 3 => 0.0);

julia> rm = ResetMap(X, r);

Here rm modifies the set X such that x1 is reset to 4 and x3 is reset to 0, while x2 is not modified. Hence rm is equivalent to the set Hyperrectangle([4.0, 2.0, 0.0], [0.0, 1.0, 0.0]), i.e., an axis-aligned line segment embedded in 3D.

The corresponding affine map $A x + b$ would be:

Use the function get_A (resp. get_b) to create the matrix A (resp. vector b) corresponding to a given reset map.

The (in this case unique) support vector of rm in direction ones(3) is:

julia> σ(ones(3), rm)
3-element Array{Float64,1}:
 4.0
 3.0
 0.0

dim(rm::ResetMap)

Return the dimension of a reset map.

Input

• rm – reset map

Output

The dimension of a reset map.

ρ(d::AbstractVector{N}, rm::ResetMap{N}) where {N<:Real}

Return the support function of a reset map.

Input

• d – direction
• rm – reset map

Output

The support function in the given direction.

Notes

We use the usual dot-product definition, but for unbounded sets we redefine the product between $0$ and $±∞$ as $0$; Julia returns NaN here.

julia> Inf * 0.0
NaN

See the discussion here.

σ(d::AbstractVector{N}, rm::ResetMap{N}) where {N<:Real}

Return the support vector of a reset map.

Input

• d – direction
• rm – reset map

Output

The support vector in the given direction. If the direction has norm zero, the result depends on the wrapped set.

an_element(rm::ResetMap)

Return some element of a reset map.

Input

• rm – reset map

Output

An element in the reset map. It relies on the an_element function of the wrapped set.

isempty(rm::ResetMap)::Bool

Return if a reset map is empty or not.

Input

• rm – reset map

Output

true iff the wrapped set is empty.

get_A(rm::ResetMap{N}) where {N<:Real}

Return the $A$ matrix of the affine map $A x + b, x ∈ X$ represented by a reset map.

Input

• rm – reset map

Output

The (diagonal) matrix for the affine map $A x + b, x ∈ X$ represented by the reset map.

Algorithm

We construct the identity matrix and set all entries in the reset dimensions to zero.

get_b(rm::ResetMap{N}) where {N<:Real}

Return the $b$ vector of the affine map $A x + b, x ∈ X$ represented by a reset map.

Input

• rm – reset map

Output

The (sparse) vector for the affine map $A x + b, x ∈ X$ represented by the reset map. The vector contains the reset value for all reset dimensions, and is zero for all other dimensions.

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

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<:Real, 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.

Translation{N<:Real, VN<:AbstractVector{N}, S<:LazySet{N}} <: LazySet{N}

Type that represents a lazy translation.

The translation of set X along vector v is the map:

A translation is a special case of an affine map $A x + b, x ∈ X$ where the linear map $A$ is the identity matrix and the translation vector $b = v$.

Fields

• X – convex set
• v – vector that defines the translation

Example

julia> X = BallInf([2.0, 2.0, 2.0], 1.0);

julia> v = [1.0, 0.0, 0.0]; # translation along dimension 1

julia> tr = Translation(X, v);

julia> typeof(tr)
Translation{Float64,Array{Float64,1},BallInf{Float64}}

julia> tr.X
BallInf{Float64}([2.0, 2.0, 2.0], 1.0)

julia> tr.v
3-element Array{Float64,1}:
 1.0
 0.0
 0.0

The sum operator + is overloaded to create translations:

julia> X + v == Translation(X, v)
true

And so does the Minkowski sum operator, ⊕:

julia> X ⊕ v == Translation(X, v)
true

The translation of a translation is performed immediately:

julia> tr = (X+v)+v
Translation{Float64,Array{Float64,1},BallInf{Float64}}(BallInf{Float64}([2.0, 2.0, 2.0], 1.0), [2.0, 0.0, 0.0])

julia> tr.v
3-element Array{Float64,1}:
 2.0
 0.0
 0.0

The dimension of a translation is obtained with the dim function:

julia> dim(tr)
3

For the support vector (resp. support function) along vector d, use σ and ρ respectively:

julia> σ([1.0, 0.0, 0.0], tr)
3-element Array{Float64,1}:
 5.0
 3.0
 3.0

julia> ρ([1.0, 0.0, 0.0], tr)
5.0

See the docstring of each of these functions for details.

The an_element function is useful to obtain an element of a translation:

julia> e = an_element(tr)
3-element Array{Float64,1}:
 4.0
 2.0
 2.0

The lazy linear map of a translation is again a translation, since the following simplification rule applies: $M * (X⊕v) = (M*X) ⊕ (M*v)$:

julia> using LinearAlgebra: I

julia> Q = Matrix(2.0I, 3, 3) * tr;

julia> Q isa Translation && Q.v == 2 * tr.v
true

Use the isempty method to query if the translation is empty; it falls back to the isempty method of the wrapped set:

julia> isempty(tr)
false

The list of constraints of the translation of a polyhedron (in general, a set whose constraints_list is available) can be computed from a lazy translation:

julia> constraints_list(tr)
6-element Array{HalfSpace{Float64,VN} where VN<:AbstractArray{Float64,1},1}:
 HalfSpace{Float64,LazySets.Arrays.SingleEntryVector{Float64}}([1.0, 0.0, 0.0], 5.0)
 HalfSpace{Float64,LazySets.Arrays.SingleEntryVector{Float64}}([0.0, 1.0, 0.0], 3.0)
 HalfSpace{Float64,LazySets.Arrays.SingleEntryVector{Float64}}([0.0, 0.0, 1.0], 3.0)
 HalfSpace{Float64,LazySets.Arrays.SingleEntryVector{Float64}}([-1.0, 0.0, 0.0], -3.0)
 HalfSpace{Float64,LazySets.Arrays.SingleEntryVector{Float64}}([0.0, -1.0, 0.0], -1.0)
 HalfSpace{Float64,LazySets.Arrays.SingleEntryVector{Float64}}([0.0, 0.0, -1.0], -1.0)

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

Convenience constructor for a translation.

Input

• X – convex set
• v – vector

Output

The symbolic translation of $X$ along vector $v$.

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

Unicode alias constructor ⊕ (oplus) for the lazy translation operator.

dim(tr::Translation)::Int

Return the dimension of a translation.

Input

• tr – translation

Output

The dimension of a translation.

ρ(d::AbstractVector{N}, tr::Translation{N}) where {N<:Real}

Return the support function of a translation.

Input

• d – direction
• tr – translation

Output

The support function in the given direction.

σ(d::AbstractVector{N}, tr::Translation{N}) where {N<:Real}

Return the support vector of a translation.

Input

• d – direction
• tr – translation

Output

The support vector in the given direction. If the direction has norm zero, the result depends on the wrapped set.

an_element(tr::Translation)

Return some element of a translation.

Input

• tr – translation

Output

An element in the translation.

Notes

This function first asks for an_element function of the wrapped set, then translates this element according to the given translation vector.

isempty(tr::Translation)::Bool

Return if a translation is empty or not.

Input

• tr – translation

Output

true iff the wrapped set is empty.

constraints_list(tr::Translation{N}, ::Val{true}) where {N<:Real}

Return the list of constraints of the translation of a set.

Input

• tr – lazy translation of a polyhedron

Output

The list of constraints of the translation.

Notes

We assume that the set wrapped by the lazy translation X offers a method constraints_list(⋅).

Algorithm

Let the translation be defined by the set of points y such that y = x + v for all x ∈ X. Then, each defining halfspace a⋅x ≤ b is transformed to a⋅y ≤ b + a⋅v.

LinearMap(M::AbstractMatrix{N}, tr::Translation{N}) where {N<:Real}

Return the lazy linear map of a translation.

Input

• M – matrix
• tr – translation

Output

The translation defined by the linear map.

Notes

This method defines the simplification rule: $M * (X⊕v) = (M*X) ⊕ (M*v)$, returning a new translation.

linear_map(M::AbstractMatrix{N}, tr::Translation{N}) where {N<:Real}

Concrete linear map of a polyhedron in constraint representation.

Input

• M – matrix
• tr – translation of a convex set

Output

A concrete set corresponding to the linear map. The type of the result depends on the type of the set wrapped by tr.

Algorithm

We compute translate(linear_map(M, tr.X), M * tr.v).

∈(x::AbstractVector{N}, tr::Translation{N})::Bool where {N<:Real}

Check whether a given point is contained in the translation of a convex set.

Input

• x – point/vector
• tr – translation of a convex set

Output

true iff $x ∈ tr$.

Algorithm

This implementation relies on the set membership function for the wrapped set tr.X, since $x ∈ X ⊕ v$ iff $x - v ∈ X$.

AffineMap{N<:Real, S<:LazySet{N}, NM, MAT<:AbstractMatrix{NM},
          VN<:AbstractVector{NM}} <: LazySet{N}

Type that represents an affine transformation $M⋅X ⊕ v$ of a convex set $X$.

Fields

• M – matrix/linear map
• X – convex set
• v – translation vector

Notes

An affine map is the composition of a linear map and a translation. This type is parametric in the coefficients of the linear map, NM, which may be different from the numeric type of the wrapped set (N). However, the numeric type of the translation vector should be NM.

    *(M::AbstractMatrix{N}, X::LazySet{N}) where {N<:Real}

Return the linear map of a convex set.

Input

• M – matrix/linear map
• X – convex set

Output

A lazy linear map, i.e. a LinearMap instance.

    *(α::N, am::AffineMap{N}) where {N<:Real}

Return the affine map scaled by a given number.

Input

• α – scalar
• am – affine map

Output

The scaled affine map.

dim(am::AffineMap)::Int

Return the dimension of an affine map.

Input

• am – affine map

Output

The dimension of an affine map.

σ(d::AbstractVector{N}, am::AffineMap{N}) where {N<:Real}

Return the support vector of an affine map.

Input

• d – direction
• am – affine map

Output

The support vector in the given direction.

ρ(d::AbstractVector{N}, am::AffineMap{N}) where {N<:Real}

Return the support function of an affine map.

Input

• d – direction
• am – affine map

Output

The support function in the given direction.

an_element(am::AffineMap)

Return some element of an affine map.

Input

• am – affine map

Output

An element of the affine map. It relies on the an_element function of the wrapped set.

isempty(am::AffineMap)::Bool

Return whether an affine map is empty or not.

Input

• am – affine map

Output

true iff the wrapped set is empty and the affine vector is empty.

isbounded(am::AffineMap; cond_tol::Number=DEFAULT_COND_TOL)::Bool

Determine whether an affine map is bounded.

Input

• am – affine map
• cond_tol – (optional) tolerance of matrix condition (used to check whether the matrix is invertible)

Output

true iff the affine map is bounded.

Algorithm

We first check if the matrix is zero or the wrapped set is bounded. If not, we perform a sufficient check whether the matrix is invertible. If the matrix is invertible, then the map being bounded is equivalent to the wrapped set being bounded, and hence the map is unbounded. Otherwise, we check boundedness via isbounded_unit_dimensions.

∈(x::AbstractVector{N}, am::AffineMap{N})::Bool where {N<:Real}

Check whether a given point is contained in the affine map of a convex set.

Input

• x – point/vector
• am – affine map of a convex set

Output

true iff $x ∈ am$.

Algorithm

Note that $x ∈ M⋅S ⊕ v$ iff $M^{-1}⋅(x - v) ∈ S$. This implementation does not explicitly invert the matrix, which is why it also works for non-square matrices.

Examples

julia> am = AffineMap([2.0 0.0; 0.0 1.0], BallInf([1., 1.], 1.), [-1.0, -1.0]);

julia> [5.0, 1.0] ∈ am
false

julia> [3.0, 1.0] ∈ am
true

An example with a non-square matrix:

julia> B = BallInf(zeros(4), 1.);

julia> M = [1. 0 0 0; 0 1 0 0]/2;

julia> [0.5, 0.5] ∈ M*B
true

vertices_list(am::AffineMap{N};
              [apply_convex_hull]::Bool)::Vector{Vector{N}} where {N<:Real}

Return the list of vertices of a (polyhedral) affine map.

Input

• am – affine map
• apply_convex_hull – (optional, default: true) if true, apply the convex hull operation to the list of vertices transformed by the affine map

Output

A list of vertices.

Algorithm

This implementation computes all vertices of X, then transforms them through the affine map, i.e. x ↦ M*x + v for each vertex x of X. By default, the convex hull operation is taken before returning this list. For dimensions three or higher, this operation relies on the functionality through the concrete polyhedra library Polyhedra.jl.

If you are not interested in taking the convex hull of the resulting vertices under the affine map, pass apply_convex_hull=false as a keyword argument.

Note that we assume that the underlying set X is polyhedral, either concretely or lazily, i.e. there the function vertices_list should be applicable.

constraints_list(am::AffineMap{N}) where {N<:Real}

Return the list of constraints of a (polyhedral) affine map.

Input

• am – affine map

Output

The list of constraints of the affine map.

Notes

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

Algorithm

Falls back to the list of constraints of the translation of a lazy linear map.

linear_map(M::AbstractMatrix{N}, am::AffineMap{N}) where {N<:Real}

Return the linear map of a lazy affine map.

Input

• M – matrix
• am – affine map

Output

A set corresponding to the linear map of the lazy affine map of a set.

SymmetricIntervalHull{N<:Real, S<:LazySet{N}} <: AbstractHyperrectangle{N}

Type that represents the symmetric interval hull of a compact convex set.

Fields

• X – compact convex set
• cache – partial storage of already computed bounds, organized as mapping from dimension to tuples (bound, valid), where valid is a flag indicating if the bound entry has been computed

Notes

The symmetric interval hull can be computed with $2n$ support vector queries of unit vectors, where $n$ is the dimension of the wrapped set (i.e., two queries per dimension). When asking for the support vector for a direction $d$, one needs $2k$ such queries, where $k$ is the number of non-zero entries in $d$.

However, if one asks for many support vectors in a loop, the number of computations may exceed $2n$. To be most efficient in such cases, this type stores the intermediately computed bounds in the cache field.

The set X must be compact.

dim(sih::SymmetricIntervalHull)::Int

Return the dimension of a symmetric interval hull of a convex set.

Input

• sih – symmetric interval hull of a convex set

Output

The ambient dimension of the symmetric interval hull of a convex set.

σ(d::AbstractVector{N}, sih::SymmetricIntervalHull{N}) where {N<:Real}

Return the support vector of a symmetric interval hull of a convex set in a given direction.

Input

• d – direction
• sih – symmetric interval hull of a convex set

Output

The support vector of the symmetric interval hull of a convex set in the given direction. If the direction has norm zero, the origin is returned.

Algorithm

For each non-zero entry in d we need to either look up the bound (if it has been computed before) or compute it, in which case we store it for future queries. One such computation just asks for the support vector of the underlying set for both the positive and negative unit vector in the respective dimension.

center(sih::SymmetricIntervalHull{N})::Vector{N} where {N<:Real}

Return the center of a symmetric interval hull of a convex set.

Input

• sih – symmetric interval hull of a convex set

Output

The origin.

radius_hyperrectangle(sih::SymmetricIntervalHull{N}
                     )::Vector{N} where {N<:Real}

Return the box radius of a symmetric interval hull of a convex set in every dimension.

Input

• sih – symmetric interval hull of a convex set

Output

The box radius of the symmetric interval hull of a convex set.

Notes

This function computes the symmetric interval hull explicitly.

radius_hyperrectangle(sih::SymmetricIntervalHull{N},
                      i::Int)::N where {N<:Real}

Return the box radius of a symmetric interval hull of a convex set in a given dimension.

Input

• sih – symmetric interval hull of a convex set
• i – dimension of interest

Output

The radius in the given dimension. If it was computed before, this is just a look-up, otherwise it requires two support vector computations.

UnionSet{N<:Real, S1<:LazySet{N}, S2<:LazySet{N}}

Type that represents the set union of two convex sets.

Fields

• X – convex set
• Y – convex set

∪

Alias for UnionSet.

swap(cup::UnionSet)

Return a new UnionSet object with the arguments swapped.

Input

• cup – union of two convex sets

Output

A new UnionSet object with the arguments swapped.

dim(cup::UnionSet)::Int

Return the dimension of the set union of two convex sets.

Input

• cup – union of two convex sets

Output

The ambient dimension of the union of two convex sets.

σ(d::AbstractVector{N}, cup::UnionSet{N}; [algorithm]="support_vector") where {N<:Real}

Return the support vector of the union of two convex sets in a given direction.

Input

• d – direction
• cup – union of two convex sets
• algorithm – (optional, default: "supportvector"): the algorithm to compute the support vector; if "supportvector", use the support vector of each argument; if "support_function" use the support function of each argument and evaluate the support vector of only one of them

Output

The support vector in the given direction.

Algorithm

The support vector of the union of two convex sets $X$ and $Y$ can be obtained as the vector that maximizes the support function of either $X$ or $Y$, i.e. it is sufficient to find the $\argmax(ρ(d, X), ρ(d, Y)])$ and evaluate its support vector.

The default implementation, with option algorithm="support_vector", computes the support vector of $X$ and $Y$ and then compares the support function using a dot product. If it happens that the support function can be more efficiently computed (without passing through the support vector), consider using the alternative algorithm="support_function" implementation, which evaluates the support function of each set directly and then calls only the support vector of either $X$ or $Y$.

ρ(d::AbstractVector{N}, cup::UnionSet{N}) where {N<:Real}

Return the support function of the union of two convex sets in a given direction.

Input

• d – direction
• cup – union of two convex sets

Output

The support function in the given direction.

Algorithm

The support function of the union of two convex sets $X$ and $Y$ is the maximum of the support functions of $X$ and $Y$.

an_element(cup::UnionSet{N})::Vector{N} where {N<:Real}

Return some element of a union of two convex sets.

Input

• cup – union of two convex sets

Output

An element in the union of two convex sets.

Algorithm

We use an_element on the first wrapped set.

∈(x::AbstractVector{N}, cup::UnionSet{N})::Bool where {N<:Real}

Check whether a given point is contained in a union of two convex sets.

Input

• x – point/vector
• cup – union of two convex sets

Output

true iff $x ∈ cup$.

isempty(cup::UnionSet)::Bool

Check whether a union of two convex sets is empty.

Input

• cup – union of two convex sets

Output

true iff the union is empty.

isbounded(cup::UnionSet)::Bool

Determine whether a union of two convex sets is bounded.

Input

• cup – union of two convex sets

Output

true iff the union is bounded.

UnionSetArray{N<:Real, S<:LazySet{N}}

Type that represents the set union of a finite number of convex sets.

Fields

• array – array of convex sets

dim(cup::UnionSetArray)::Int

Return the dimension of the set union of a finite number of convex sets.

Input

• cup – union of a finite number of convex sets

Output

The ambient dimension of the union of a finite number of convex sets.

array(cup::UnionSetArray{N, S})::Vector{S} where {N<:Real, S<:LazySet{N}}

Return the array of a union of a finite number of convex sets.

Input

• cup – union of a finite number of convex sets

Output

The array that holds the union of a finite number of convex sets.

σ(d::AbstractVector{N}, cup::UnionSetArray{N}; [algorithm]="support_vector") where {N<:Real}

Return the support vector of the union of a finite number of convex sets in a given direction.

Input

• d – direction
• cup – union of a finite number of convex sets
• algorithm – (optional, default: "supportvector"): the algorithm to compute the support vector; if "supportvector", use the support vector of each argument; if "support_function" use the support function of each argument and evaluate the support vector of only one of them

Output

The support vector in the given direction.

Algorithm

The support vector of the union of a finite number of convex sets $X₁, X₂, ...$ can be obtained as the vector that maximizes the support function, i.e. it is sufficient to find the $\argmax(ρ(d, X₂), ρ(d, X₂), ...])$ and evaluate its support vector.

The default implementation, with option algorithm="support_vector", computes the support vector of all $X₁, X₂, ...$ and then compares the support function using a dot product. If it happens that the support function can be more efficiently computed (without passing through the support vector), consider using the alternative algorithm="support_function" implementation, which evaluates the support function of each set directly and then calls only the support vector of one of the $Xᵢ$.

ρ(d::AbstractVector{N}, cup::UnionSetArray{N}) where {N<:Real}

Return the support function of the union of a finite number of convex sets in a given direction.

Input

• d – direction
• cup – union of a finite number of convex sets

Output

The support function in the given direction.

Algorithm

The support function of the union of a finite number of convex sets $X₁, X₂, ...$ can be obtained as the maximum of $ρ(d, X₂), ρ(d, X₂), ...$.

an_element(cup::UnionSetArray{N})::Vector{N} where {N<:Real}

Return some element of a union of a finite number of convex sets.

Input

• cup – union of a finite number of convex sets

Output

An element in the union of a finite number of convex sets.

Algorithm

We use an_element on the first wrapped set.

∈(x::AbstractVector{N}, cup::UnionSetArray{N})::Bool where {N<:Real}

Check whether a given point is contained in a union of a finite number of convex sets.

Input

• x – point/vector
• cup – union of a finite number of convex sets

Output

true iff $x ∈ cup$.

isempty(cup::UnionSetArray)::Bool

Check whether a union of a finite number of convex sets is empty.

Input

• cup – union of a finite number of convex sets

Output

true iff the union is empty.

isbounded(cup::UnionSetArray)::Bool

Determine whether a union of a finite number of convex sets is bounded.

Input

• cup – union of a finite number of convex sets

Output

true iff the union is bounded.

Complement{N<:Real, S<:LazySet{N}}

Type that represents the complement of a convex set.

Fields

• X – convex set

Notes

Since X is assumed to be closed, unless X is empty or the universe, its complement is open (i.e., not closed). Since X is assumed to be closed, unless X is empty, the universe, or a half-space, its complement is not convex.

The complement of the complement is the original set again.

Examples

julia> B = BallInf(zeros(2), 1.); C = Complement(B)
Complement{Float64,BallInf{Float64}}(BallInf{Float64}([0.0, 0.0], 1.0))

julia> Complement(C)
BallInf{Float64}([0.0, 0.0], 1.0)

dim(C::Complement)

Return the dimension of the complement of a convex set.

Input

• C – complement of a convex set

Output

The dimension of the complement of a convex set.

∈(x::AbstractVector{N}, C::Complement{N})::Bool where {N<:Real}

Check whether a given point is contained in the complement of a convex set.

Input

• x – point/vector
• C – complement of a convex set

Output

true iff the vector is contained in the complement.

Algorithm

isempty(C::Complement)::Bool

Return if the complement of a convex set is empty or not.

Input

• C – complement of a convex set

Output

false unless the original set is universal.

Algorithm

We use the isuniversal method.

Rectification{N<:Real, S<:LazySet{N}}

Type that represents the rectification of a convex set.

Fields

• X – convex set
• cache – storage of information computed before

Notes

Given a vector $v = (v_1, …, v_n)$, its rectification is defined as $\text{rectify}(v) = (v_1', …, v_n')$ such that $v_i' = \max(v_i, 0)$ for each $i = 1, …, n$.

The extension to a set $X$ is defined elementwise:

The rectification of a convex set $X$ is not necessarily convex. It can be expressed exactly as the union of the intersection of $X$ with the nonnegative orthant and the projection of the intersection of $X$ with each other orthant. This can be seen as follows.

First we observe that rectification distributes with union.

Next we express $X$ as the union of the intersection of $X$ with each orthant $O$.

Thus we have

Clearly, $\text{rectify}(X ∩ O_j) = X$ if $O_j$ is the nonnegative orthant.

For example, consider a two-dimensional case and call the orthants $O_1, …, O_4$ in clockwise fashion, starting with the nonnegative orthant. We conclude that

The rectification of the intersection in the nonpositive orthant, $\text{rectify}(X ∩ O_3)$, is either the empty set or the singleton containing the origin. The rectification of $X ∩ O_2$ and $X ∩ O_4$ both result in flat $1$-dimensional line segments on the corresponding hyperplane of $O_1$.

dim(r::Rectification)::Int

Return the dimension of a rectification.

Input

• r – rectification

Output

The ambient dimension of the rectification.

σ(d::AbstractVector{N}, r::Rectification{N}) where {N<:Real}

Return the support vector of a rectification.

Input

• d – direction
• r – rectification

Output

The support vector in the given direction. If the direction has norm zero, the result depends on the wrapped set.

σ(d::AbstractVector{N},
  r::Rectification{N, <:AbstractHyperrectangle{N}}) where {N<:Real}

Return the support vector of the rectification of a hyperrectangular set.

Input

• d – direction
• r – rectification of a hyperrectangular set

Output

The support vector in the given direction.

Algorithm

Let $r(·)$ be the rectification of a vector respectively a set, and let $H$ be a hyperrectangle. Then $σ_{r(H)}(d) = r(σ_{H}(d))$.

σ(d::AbstractVector{N},
  r::Rectification{N, <:CartesianProduct{N}}) where {N<:Real}

Return the support vector of the rectification of a Cartesian product of two convex sets.

Input

• d – direction
• r – rectification of a Cartesian product of two convex sets

Output

The support vector in the given direction.

Algorithm

Rectification distributes with the Cartesian product. Let $r(·)$ be the rectification of a set. We can just query the support vector for $r(X)$ and $r(Y)$ recursively: $σ_{r(X × Y)}(d) = σ_{r(X)}(d_X) × σ_{r(Y)}(d_Y)$, where $x × y$ concatenates vectors $x$ and $y$.

σ(d::AbstractVector{N},
  r::Rectification{N, <:CartesianProductArray{N}}) where {N<:Real}

Return the support vector of the rectification of a Cartesian product of a finite number of convex sets.

Input

• d – direction
• r – rectification of a Cartesian product of a finite number of convex sets

Output

The support vector in the given direction.

Algorithm

Rectification distributes with the Cartesian product. Let $r(·)$ be the rectification of a set. We can just query the support vector for each subspace recursively: $σ_{r(X_1 × ⋯ × X_m)}(d) = σ_{r(X_1)}(d_{X_1}) × ⋯ × σ_{r(X_m)}(d_{X_m})$, where $x × y$ concatenates vectors $x$ and $y$.

ρ(d::AbstractVector{N}, r::Rectification{N}) where {N<:Real}

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

Input

• d – direction
• r – rectification of a convex set

Output

The support value of the rectification of a convex set in the given direction.

Algorithm

We use different procedures for different types of input sets. If the wrapped set has a suitable structure for which we can efficiently compute the support vector, we fall back to the evaluation of the support function by means of the support vector. Otherwise we compute the union of projections to obtain a precise result (see to_union_of_projections), and then compute the support function for this union. (The union is cached internally, so subsequent queries are more efficient.)

an_element(r::Rectification{N})::Vector{N} where {N<:Real}

Return some element of a rectification.

Input

• r – rectification

Output

An element in the rectification. The implementation relies on the an_element function of the wrapped set.

∈(x::AbstractVector{N}, r::Rectification{N})::Bool where {N<:Real}

Check whether a given point is contained in a rectification.

Input

• x – point/vector
• r – rectification

Output

true iff $x ∈ r$.

Algorithm

We first scan for negative entries in the vector. If there are any, the vector is not contained in the rectification.

Next we ask a membership query in the wrapped set. If the answer is positive, the vector is contained in the rectification.

Otherwise, we scan for zero entries in the vector. If there are none, membership reduces to membership in the wrapped set, and so the answer is negative.

Finally, if there are zero entries in the vector and the vector is not contained in the wrapped set, we give up and throw an error.

isempty(r::Rectification)::Bool

Check whether a rectification is empty or not.

Input

• r – rectification

Output

true iff the wrapped set is empty.

isbounded(r::Rectification)::Bool

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

to_union_of_projections(r::Rectification{N},
                        concrete_intersection::Bool=false
                       ) where {N<:Real}

Compute an equivalent union of projections from a rectification of a convex set.

Input

• r – rectification of a convex set
• concrete_intersection – (optional, default: false) option to compute all intersections concretely or lazily

Algorithm

Let $X$ be the set wrapped by the rectification $r$. We compute a union of sets that represents the rectification of $X$ precisely. The sets are lazy projections, potentially of intersections.

We first identify those dimensions where $X$ is negative, using one support-function query per dimension, and collect the dimensions in the index set $I_\text{neg}$. For each element in $I_\text{neg}$ we will later apply a projection to zero.

Next we identify those dimensions from $I_\text{neg}$ where $X$ is also positive, using another support-function query in each dimension, and collect the dimensions in the index set $I_\text{mix}$. Let us call the remaining dimensions ($I_\text{neg} \setminus I_\text{mix}$) $I_\text{nonpos}$. For each dimension in $j ∈ I_\text{mix}$ we will apply an intersection with axis-aligned polyhedra. In particular, we distinguish two cases using half-spaces $x_j ≤ 0$ and $x_j ≥ 0$, and then compute all possible combinations to intersect, using one half-space per dimension $j ∈ I_\text{mix}$.

Next we project the intersections in all dimensions from $i ∈ I_\text{mix}$ such that we used the half-space $x_i ≤ 0$ in their computation, and in all dimensions $j ∈ I_\text{nonpos}$ irrespective of the half-space used.

Finally, we take the union of the resulting sets.

Output

The result can be one of three cases depending on the wrapped set $X$, namely

• the set $X$ if $X$ is contained in the positive quadrant,
• a LinearMap (projection) of $X$ if for each dimension, $X$ is only either positive or negative, or
• a UnionSetArray of LinearMaps (projections) otherwise.

RectificationCache{N<:Real}

Struct that is used as a cache for Rectifications.

Fields

• set – set represented by the rectification (can be nothing if not computed yet)
• use_support_vector – flag indicating whether to use support-vector computations for the cached set