Common Set Operations
This section of the manual describes the basic symbolic types describing operations between sets.
- Common Set Operations
Cartesian Product
Binary Cartesian Product
LazySets.CartesianProduct
— Type.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 setY
– 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 constructorCartesianProduct(Xarr::Vector{S}) where {S<:LazySet}
– constructor from an array of convex sets
Base.:*
— Method. *(X::LazySet, Y::LazySet)
Alias for the binary Cartesian product.
*(a::N, X::LazySet) where {N}
Return a linear map of a convex set by a scalar value.
Input
a
– scalarX
– convex set
Output
The linear map of the convex set.
LazySets.dim
— Method.dim(cp::CartesianProduct)::Int
Return the dimension of a Cartesian product.
Input
cp
– Cartesian product
Output
The ambient dimension of the Cartesian product.
LazySets.σ
— Method.σ(d::V, cp::CartesianProduct) where {N<:Real, V<:AbstractVector{N}}
Return the support vector of a Cartesian product.
Input
d
– directioncp
– Cartesian product
Output
The support vector in the given direction. If the direction has norm zero, the result depends on the product sets.
Algorithm
Base.:∈
— Method.∈(x::AbstractVector{<:Real}, cp::CartesianProduct)::Bool
Check whether a given point is contained in a Cartesian product set.
Input
x
– point/vectorcp
– Cartesian product
Output
true
iff $x ∈ cp$.
$n$-ary Cartesian Product
LazySets.CartesianProductArray
— Type.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 constructorCartesianProductArray([n]::Int=0, [N]::Type=Float64)
– constructor for an empty product with optional size hint and numeric type
LazySets.array
— Method.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.
LazySets.dim
— Method.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.
LazySets.σ
— Method.σ(d::V, cpa::CartesianProductArray{N, <:LazySet{N}}) where {N<:Real, V<:AbstractVector{N}}
Support vector of a Cartesian product.
Input
d
– directioncpa
– Cartesian product array
Output
The support vector in the given direction. If the direction has norm zero, the result depends on the product sets.
Base.:∈
— Method.∈(x::AbstractVector{N}, cpa::CartesianProductArray{N, <:LazySet{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/vectorcpa
– Cartesian product array
Output
true
iff $x ∈ \text{cpa}$.
Convex Hull
Binary Convex Hull
LazySets.ConvexHull
— Type.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 setY
– 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)
LazySets.ConvexHull{Float64,LazySets.Ball2{Float64},LazySets.Ball2{Float64}}
LazySets.CH
— Type.CH
Alias for ConvexHull
.
LazySets.dim
— Method.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.
LazySets.σ
— Method.σ(d::V, ch::ConvexHull) where {N<:Real, V<:AbstractVector{N}}
Return the support vector of a convex hull of two convex sets in a given direction.
Input
d
– directionch
– convex hull of two convex sets
$n$-ary Convex Hull
LazySets.ConvexHullArray
— Type.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 constructorConvexHullArray([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);
LazySets.CHArray
— Type.CHArray
Alias for ConvexHullArray
.
LazySets.array
— Method.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.
LazySets.dim
— Method.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.
LazySets.σ
— Method.σ(d::V, cha::ConvexHullArray) where {N<:Real, V<:AbstractVector{N}}
Return the support vector of a convex hull array in a given direction.
Input
d
– directioncha
– convex hull array
Convex Hull Algorithms
LazySets.convex_hull
— Function.convex_hull(points::Vector{S}; [algorithm]::String="monotone_chain"
)::Vector{S} where {S<:AbstractVector{N}} where {N<:Real}
Compute the convex hull of points in the plane.
Input
points
– list of 2D vectorsalgorithm
– (optional, default:"monotone_chain"
) the convex hull algorithm, valid options are:"monotone_chain"
"monotone_chain_sorted"
Output
The convex hull as a list of 2D vectors with the coordinates of the points.
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);
LazySets.convex_hull!
— Function.convex_hull!(points::Vector{S}; [algorithm]::String="monotone_chain"
)::Vector{S} where {S<:AbstractVector{N}} where {N<:Real}
Compute the convex hull of points in the plane, in-place.
Input
points
– list of 2D vectors (is modified)algorithm
– (optional, default:"monotone_chain"
) the convex hull algorithm; valid options are:"monotone_chain"
"monotone_chain_sorted"
Output
The convex hull as a list of 2D vectors with the coordinates of the points.
Notes
See the non-modifying version convex_hull
for more details.
LazySets.right_turn
— Function.right_turn(O::AbstractVector{N}, A::AbstractVector{N}, B::AbstractVector{N}
)::N where {N<:Real}
Determine if the acute angle defined by the three points O
, A
, B
in the plane is a right turn (counter-clockwise) with respect to the center O
.
Input
O
– 2D center pointA
– 2D one pointB
– 2D another point
Output
Scalar representing the rotation.
Algorithm
The cross product is used to determine the sense of rotation. If the result is 0, the points are collinear; if it is positive, the three points constitute a positive angle of rotation around O
from A
to B
; otherwise they constitute a negative angle.
LazySets.monotone_chain!
— Function.monotone_chain!(points::Vector{S}; sort::Bool=true
)::Vector{S} where {S<:AbstractVector{N}} where {N<:Real}
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 functionsort
– (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
Binary Intersection
LazySets.Intersection
— Type.Intersection{N<:Real, S1<:LazySet{N}, S2<:LazySet{N}} <: LazySet{N}
Type that represents the intersection of two convex sets.
Fields
X
– convex setY
– convex set
Base.:∩
— Method.∩
Alias for Intersection
.
LazySets.dim
— Method.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.
LazySets.σ
— Method.σ(d::V, cap::Intersection) where {N<:Real, V<:AbstractVector{N}}
Return the support vector of an intersection of two convex sets in a given direction.
Input
d
– directioncap
– intersection of two convex sets
Output
The support vector in the given direction.
Base.:∈
— Method.∈(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/vectorcap
– intersection of two convex sets
Output
true
iff $x ∈ cap$.
Base.isempty
— Method.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.
$n$-ary Intersection
LazySets.IntersectionArray
— Type.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 constructorIntersectionArray([n]::Int=0, [N]::Type=Float64)
– constructor for an empty sum with optional size hint and numeric type
LazySets.array
— Method.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.
LazySets.dim
— Method.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.
LazySets.σ
— Method.σ(d::AbstractVector{<:Real}, ia::IntersectionArray)::Vector{<:Real}
Return the support vector of an intersection of a finite number of sets in a given direction.
Input
d
– directionia
– 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.
Minkowski Sum
Binary Minkowski Sum
LazySets.MinkowskiSum
— Type.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 setY
– second convex set
Notes
The ZeroSet
is the neutral element and the EmptySet
is the absorbing element for MinkowskiSum
.
Base.:+
— Method.X + Y
Convenience constructor for Minkowski sum.
Input
X
– a convex setY
– another convex set
Output
The symbolic Minkowski sum of $X$ and $Y$.
LazySets.:⊕
— Function.⊕(X::LazySet, Y::LazySet)
Unicode alias constructor ⊕ (oplus
) for the lazy Minkowski sum operator.
LazySets.dim
— Method.dim(ms::MinkowskiSum)::Int
Return the dimension of a Minkowski sum.
Input
ms
– Minkowski sum
Output
The ambient dimension of the Minkowski sum.
LazySets.σ
— Method.σ(d::V, ms::MinkowskiSum) where {N<:Real, V<:AbstractVector{N}}
Return the support vector of a Minkowski sum.
Input
d
– directionms
– Minkowski sum
Output
The support vector in the given direction. If the direction has norm zero, the result depends on the summand sets.
$n$-ary Minkowski Sum
LazySets.MinkowskiSumArray
— Type.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 constructorMinkowskiSumArray([n]::Int=0, [N]::Type=Float64)
– constructor for an empty sum with optional size hint and numeric type
LazySets.array
— Method.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.
LazySets.dim
— Method.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.
LazySets.σ
— Method.σ(d::AbstractVector{<:Real}, msa::MinkowskiSumArray)::Vector{<:Real}
Return the support vector of a Minkowski sum of a finite number of sets in a given direction.
Input
d
– directionmsa
– Minkowski sum array
Output
The support vector in the given direction. If the direction has norm zero, the result depends on the summand sets.
$n$-ary Minkowski Sum with cache
LazySets.CacheMinkowskiSum
— Type.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 setscache
– 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 constructorCacheMinkowskiSum([n]::Int=0, [N]::Type=Float64)
– constructor for an empty sum with optional size hint and numeric type
LazySets.array
— Method.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.
LazySets.dim
— Method.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.
LazySets.σ
— Method.σ(d::AbstractVector{<:Real}, cms::CacheMinkowskiSum)::Vector{<:Real}
Return the support vector of a caching Minkowski sum in a given direction.
Input
d
– directioncms
– 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.
LazySets.forget_sets!
— Method.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
Maps
Linear Map
LazySets.LinearMap
— Type.LinearMap{NM, N} <: LazySet{N}
Type that represents a linear transformation $M⋅S$ of a convex set $S$.
Fields
M
– matrix/linear mapX
– convex set
Notes
This type is parametric in the elements of the linear map, NM
, and independently on the type of elements of the target set (N
). Typically NM = N
but it is not necessarily always the case e.g. if NM
is an interval that holds numbers of type N
, where N
is a floating point number type such as Float64
.
LazySets.dim
— Method.dim(lm::LinearMap)::Int
Return the dimension of a linear map.
Input
lm
– linear map
Output
The ambient dimension of the linear map.
LazySets.σ
— Method.σ(d::AbstractVector{<:Real}, lm::LinearMap)::AbstractVector{<:Real}
Return the support vector of the linear map.
Input
d
– directionlm
– 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$.
Base.:*
— Method. *(M::AbstractMatrix, X::LazySet)
Return the linear map of a convex set.
Input
M
– matrix/linear mapX
– convex set
Output
A lazy linear map, i.e. a LinearMap
instance.
Base.:*
— Method. *(a::N, X::LazySet) where {N}
Return a linear map of a convex set by a scalar value.
Input
a
– scalarX
– convex set
Output
The linear map of the convex set.
Base.:∈
— Method.∈(x::AbstractVector{N}, lm::LinearMap{NM, N})::Bool where {NM, N<:Real}
Check whether a given point is contained in a linear map of a convex set.
Input
x
– point/vectorlm
– 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
LazySets.an_element
— Method.an_element(lm::LinearMap)
Return some element of a linear map.
Input
lmap
– linear map
Output
An element in the linear map. It relies on the an_element
function of the wrapped set.
Exponential Map
LazySets.ExponentialMap
— Type.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 exponentialX
– 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> 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
LazySets.dim
— Method.dim(em::ExponentialMap)::Int
Return the dimension of an exponential map.
Input
em
– an ExponentialMap
Output
The ambient dimension of the exponential map.
LazySets.σ
— Method.σ(d::V, em::ExponentialMap) where {N<:Real, V<:AbstractVector{N}}
Return the support vector of the exponential map.
Input
d
– directionem
– 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
.
Base.:∈
— Method.∈(x::AbstractVector{N}, em::ExponentialMap{<:LazySet{N}})::Bool where {N<:Real}
Check whether a given point is contained in an exponential map of a convex set.
Input
x
– point/vectorem
– 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> em = ExponentialMap(SparseMatrixExp(SparseMatrixCSC([2.0 0.0; 0.0 1.0])),
BallInf([1., 1.], 1.));
julia> ∈([5.0, 1.0], em)
false
julia> ∈([1.0, 1.0], em)
true
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 exponentialX
– convex set
LazySets.dim
— Method.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.
LazySets.σ
— Method.σ(d::V, eprojmap::ExponentialProjectionMap) where {N<:Real, V<:AbstractVector{N}}
Return the support vector of a projection of an exponential map.
Input
d
– directioneprojmap
– 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
.
LazySets.SparseMatrixExp
— Type.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> 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.
Base.:*
— Method. *(spmexp::SparseMatrixExp, X::LazySet)::ExponentialMap
Return the exponential map of a convex set from a sparse matrix exponential.
Input
spmexp
– sparse matrix exponentialX
– convex set
Output
The exponential map of the convex set.
*(M::AbstractMatrix, X::LazySet)
Return the linear map of a convex set.
Input
M
– matrix/linear mapX
– convex set
Output
A lazy linear map, i.e. a LinearMap
instance.
*(a::N, X::LazySet) where {N}
Return a linear map of a convex set by a scalar value.
Input
a
– scalarX
– convex set
Output
The linear map of the convex set.
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 matrixE
– sparse matrix exponentialR
– right multiplication matrix
Base.:*
— Method. *(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 exponentialX
– convex set
Output
The application of the projection of a sparse matrix exponential to the convex set.
*(a::N, X::LazySet) where {N}
Return a linear map of a convex set by a scalar value.
Input
a
– scalarX
– convex set
Output
The linear map of the convex set.
Symmetric Interval Hull
LazySets.SymmetricIntervalHull
— Type.SymmetricIntervalHull{N<:Real, S<:LazySet{N}} <: AbstractHyperrectangle{N}
Type that represents the symmetric interval hull of a convex set.
Fields
X
– convex setcache
– partial storage of already computed bounds, organized as mapping from dimension to tuples(bound, valid)
, wherevalid
is a flag indicating if thebound
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.
LazySets.dim
— Method.dim(P::AbstractPointSymmetricPolytope)::Int
Return the ambient dimension of a point symmetric set.
Input
P
– set
Output
The ambient dimension of the set.
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.
LazySets.σ
— Method.σ(d::V, H::AbstractHyperrectangle{N}) where {N<:Real, V<:AbstractVector{N}}
Return the support vector of a hyperrectangular set in a given direction.
Input
d
– directionH
– hyperrectangular set
Output
The support vector in the given direction. If the direction has norm zero, the vertex with biggest values is returned.
σ(d::V, sih::SymmetricIntervalHull{N}) where {N<:Real, V<:AbstractVector{N}}
Return the support vector of a symmetric interval hull of a convex set in a given direction.
Input
d
– directionsih
– 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.
LazySets.an_element
— Method.an_element(S::LazySet{N}) where {N<:Real}
Return some element of a convex set.
Input
S
– convex set
Output
An element of a convex set.
an_element(P::AbstractPointSymmetricPolytope{N})::Vector{N} where {N<:Real}
Return some element of a point symmetric polytope.
Input
P
– point symmetric polytope
Output
The center of the point symmetric polytope.