Intersection

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.75);

julia> Z = X ∩ Y;

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

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,Array{Float64,1},Array{Float64,1}}([0.375, 0.0], [0.125, 0.5])

∩

Alias for Intersection.

dim(cap::Intersection)

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 on the support function 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, S1, S2}; kwargs...
 ) where {N<:Real, S1<:AbstractPolyhedron{N}, S2<:AbstractPolyhedron{N}}

Return an upper bound on the support function of the intersection between two polyhedral sets.

Input

• d – direction
• cap – intersection of two polyhedral sets
• kwargs – additional arguments that are passed to the support-function algorithm

Output

The support function for the given direction.

Algorithm

We combine the constraints of the two polyhedra to a new HPolyhedron, for which we then evaluate the support function.

σ(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)

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)

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}) 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}) 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::Union{<:HalfSpace, <:Hyperplane, <:Line}; [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)

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}) 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)

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}) 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}) 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}) 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}) 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}) 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::CachedMinkowskiSumArray{N, 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}) 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.