Intersection

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

Type that represents the intersection of two sets.

Fields

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

Notes

If the arguments of the lazy intersection are half-spaces, the set is simplified to a polyhedron in constraint representation (HPolyhedron).

The intersection preserves convexity: if the set arguments are convex, then their intersection is convex as well.

The convenience alias ∩ can be typed by \cap<tab>.

Examples

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

julia> X, Y = BallInf([0.0, 0.0], 0.5), BallInf([1.0, 0.0], 0.75);

julia> Z = X ∩ Y;

julia> typeof(Z)
Intersection{Float64, BallInf{Float64, Vector{Float64}}, BallInf{Float64, Vector{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, Vector{Float64}, Vector{Float64}}([0.375, 0.0], [0.125, 0.5])

dim(cap::Intersection)

Return the dimension of an intersection of two sets.

Input

• cap – intersection of two sets

Output

The ambient dimension of the intersection of two sets.

ρ(d::AbstractVector, cap::Intersection)

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

Input

• d – direction
• cap – intersection of two sets

Output

An upper 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-function evaluations for $X$ and $Y$.

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

Evaluate 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/line; evaluate 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 first set of the intersection (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

\[\min_{λ ∈ D_h} ρ(ℓ - λa, X) + λb.\]

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

For additional information we refer to Frehse and Ray [FR12], Guernic [Gue09] and Rockafellar and Wets [RW98]

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

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 polyhedron and then take the minimum. This gives an overapproximation of the exact support value.

This algorithm is inspired from Frehse and Ray [FR12].

Notes

This method relies on the constraints_list of the polyhedron.

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

Evaluate 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 evaluation of the support function in 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, cap::Intersection)

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

Input

• d – direction
• cap – intersection of two sets

Output

A support vector in the given direction.

Algorithm

We compute the concrete intersection, which may be expensive.

isbounded(cap::Intersection)

Check whether an intersection of two sets is bounded.

Input

• cap – intersection of two 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 LazySets._isbounded_unit_dimensions.

isempty(cap::Intersection)

Check whether the intersection of two sets is empty.

Input

• cap – intersection of two sets

Output

true iff the intersection is empty.

Notes

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

∈(x::AbstractVector, cap::Intersection)

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

Input

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

Output

true iff $x ∈ cap$.

Algorithm

A point $x$ is in the intersection iff it is in each set.

constraints_list(cap::Intersection)

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

Input

• cap – intersection of two (polyhedral) sets

Output

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

vertices_list(cap::Intersection)

Return a list of vertices of a lazy intersection of two (polyhedral) sets.

Input

• cap – intersection of two (polyhedral) sets

Output

A list containing the vertices of the lazy intersection of two sets.

Notes

We assume that the underlying sets are polyhedral and that the intersection is bounded.

Algorithm

We compute the concrete intersection using intersection and then take the vertices of that representation.

isempty_known(cap::Intersection)

Ask whether the status of emptiness is known.

Input

• cap – intersection of two sets

Output

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

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

Set the status of emptiness in the cache.

Input

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

swap(cap::Intersection)

Return a new Intersection object with the arguments swapped.

Input

• cap – intersection of two 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)

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

Input

• cap – intersection of two 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, <:Line2D}; [kwargs...])

Given a convex set $X$ and a half-space $H = \{x: a^T x ≤ b \}$ or a hyperplane/line $H = \{x: a^T x = b \}$, calculate:

\[\min_{λ ∈ D_h} ρ(ℓ - λa, X) + λb.\]

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

Input

• ℓ – direction
• X – convex set
• H – half-space or hyperplane or line

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 >= 1

julia> using Optim

julia> using LazySets: _line_search

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

julia> v[1]
1.0

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

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

julia> v[1]
1.0

Instead of Brent's method we can use the Golden Section method:

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

julia> v[1]
1.0

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

Given a 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 – convex set
• H – hyperplane
• lazy_linear_map – (optional, default: false) flag to perform the projection lazily or concretely
• lazy_2d_intersection – (optional, default: true) flag 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 used

Output

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

Algorithm

This projection method is based on Prop. 8.2, [1, page 103].

In the original algorithm, Guernic [Gue09], Section 8.2, 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 [Gue09, Section 8.2.2]), if one uses dispatch on ρ(y_dir, Sℓ⋂Lγ; kwargs...) given that Sℓ is itself a zonotope.

Notes

This function depends on the calculation of the support function of another set in two dimensions. Obviously one does not want to use algorithm="projection" again for this second calculation. The option algorithm_2d_intersection is used for that: if 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 arguments.

linear_map(M::AbstractMatrix, cap::Intersection)

Return the concrete linear map of an intersection of two sets.

Input

• M – matrix
• cap – intersection of two sets

Output

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

Algorithm

This method computes the concrete intersection.

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

Convert an intersection of two sets to a pair (x, y) of points for plotting.

Input

• cap – intersection of two sets
• ε – (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}, [ε]::Real=zero(N),
                  [Nφ]::Int=PLOT_POLAR_DIRECTIONS) where {N}

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 overapproximate for details).

Examples

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 an explicit 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, 0.0, 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
  • $0$ - intersection is not empty
  • $1$ - intersection is empty

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

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

Fields

• array – array of sets

Notes

This type assumes that the dimensions of all elements match.

The EmptySet is the absorbing element for IntersectionArray.

The intersection preserves convexity: if the set arguments are convex, then their intersection is convex as well.

The convenience alias ∩ can be typed by \cap<tab>.

Intersection!(X, Y)

Convenience function to compute the lazy intersection and modify IntersectionArrays in-place.

dim(ia::IntersectionArray)

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

Input

• ia – intersection of a finite number of sets

Output

The ambient dimension of the intersection of a finite number of sets, or 0 if there is no set in the array.

σ(d::AbstractVector, ia::IntersectionArray)

Return a 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 sets

Output

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

Algorithm

This implementation computes the concrete intersection, which can be expensive.

isbounded(ia::IntersectionArray)

Check whether an intersection of a finite number of sets is bounded.

Input

• ia – intersection of a finite number of 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 LazySets._isbounded_unit_dimensions.

∈(x::AbstractVector, ia::IntersectionArray)

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

Input

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

Output

true iff $x ∈ ia$.

Algorithm

A point $x$ is in the intersection iff it is in each set.

array(ia::IntersectionArray)

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

Input

• ia – intersection of a finite number of sets

Output

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

constraints_list(ia::IntersectionArray)

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.