Utilities

Macros

LazySets.@neutral — Macro

@neutral(SET, NEUT)

Create methods to make a lazy set operation commutative with a given neutral-element set type.

Input

SET – set type of lazy operation
NEUT – set type of neutral element

Output

Nothing.

Notes

This macro generates four functions (possibly two more if @absorbing has been used in advance, and possibly two or four more if @declare_array_version has been used in advance).

Examples

@neutral(MinkowskiSum, N) creates at least the following methods:

neutral(::MinkowskiSum) = N
MinkowskiSum(X, N) = X
MinkowskiSum(N, X) = X
MinkowskiSum(N, N) = N

source

LazySets.@absorbing — Macro

@absorbing(SET, ABS)

Create methods to make a lazy set operation commutative with a given absorbing-element set type.

Input

SET – set type of lazy operation
ABS – set type of absorbing element

Output

Nothing.

Notes

This macro generates four functions (possibly two more if @neutral has been used in advance, and possibly two or four more if @declare_array_version has been used in advance).

Examples

@absorbing(MinkowskiSum, A) creates at least the following methods:

absorbing(::MinkowskiSum) = A
MinkowskiSum(X, A) = A
MinkowskiSum(A, X) = A
MinkowskiSum(A, A) = A

source

LazySets.@neutral_absorbing — Macro

@neutral_absorbing(SET, NEUT, ABS)

Create two methods to avoid method ambiguities for a lazy set operation with respect to neutral-element and absorbing-element set types.

Input

SET – set type of lazy operation
NEUT – set type of neutral element
ABS – set type of absorbing element

Output

A quoted expression containing the function definitions.

Notes

This macro is used internally in other macros.

Examples

@neutral_absorbing(MinkowskiSum, N, A) creates the following methods as quoted expressions:

MinkowskiSum(N, A) = A
MinkowskiSum(A, N) = A

source

LazySets.@declare_binary_operation — Macro

@declare_binary_operation(SET)

Create common methods for binary set operations.

Input

SET – set type of the lazy operation

Output

Nothing.

Notes

This macro generates seven methods. See the example below.

Examples

@declare_binary_operation(MinkowskiSum) creates the following methods:

iterate(::MinkowskiSum)
length(::MinkowskiSum)
getindex(::MinkowskiSum, ::Int)
getindex(::MinkowskiSum, ::AbstractVector{Int})
lastindex(::MinkowskiSum)
array(::MinkowskiSum)
is_array_constructor(::Type{MinkowskiSum})

source

LazySets.@declare_array_version — Macro

@declare_array_version(SET, SETARR)

Create methods to connect a lazy set operation with its array set type.

Input

SET – set type of lazy operation
SETARR – set type of array version

Output

Nothing.

Notes

This macro generates six methods (and possibly up to eight more if @neutral/@absorbing has been used in advance for the base and/or array set type). See the example below.

Examples

@declare_array_version(MinkowskiSum, MinkowskiSumArray) creates at least the following methods:

array_constructor(::Type{MinkowskiSum}) = MinkowskiSumArray
binary_constructor(::Type{MinkowskiSumArray}) = MinkowskiSum
is_array_constructor(::Type{MinkowskiSumArray}) = true
MinkowskiSum!(X, Y)
MinkowskiSum!(X, arr)
MinkowskiSum!(arr, X)
MinkowskiSum!(arr1, arr2)

source

LazySets.@array_neutral — Macro

@array_neutral(FUN, NEUT, SETARR)

Create two methods to avoid method ambiguities for a lazy set operation with respect to the neutral-element set type and the array set type.

Input

FUN – function name
NEUT – set type of neutral element
SETARR – set type of array version

Output

A quoted expression containing the function definitions.

Examples

@array_neutral(MinkowskiSum, N, ARR) creates the following methods as quoted expressions:

MinkowskiSum(N, ARR) = ARR
MinkowskiSum(ARR, N) = ARR

source

LazySets.@array_absorbing — Macro

@array_absorbing(FUN, ABS, SETARR)

Create two methods to avoid method ambiguities for a lazy set operation with respect to the absorbing-element set type and the array set type.

Input

FUN – function name
ABS – set type of absorbing element
SETARR – set type of array version

Output

A quoted expression containing the function definitions.

Examples

@array_absorbing(MinkowskiSum, ABS, ARR) creates the following methods as quoted expressions:

MinkowskiSum(ABS, ARR) = ABS
MinkowskiSum(ARR, ABS) = ABS

source

Types

LazySets.CachedPair — Type

CachedPair{N}

A mutable pair of an index and a vector.

Fields

idx – index
vec – vector

source

Sampling

LazySets._sample_unit_nsphere_muller! — Function

_sample_unit_nsphere_muller!(D::Vector{Vector{N}}, n::Int, p::Int;
                             [rng]::AbstractRNG=GLOBAL_RNG,
                             [seed]::Union{Int, Nothing}=nothing) where {N}

Draw samples from a uniform distribution on an $n$-dimensional unit sphere using Muller's method.

Input

D – output, vector of points
n – dimension of the sphere
p – number of random samples
rng – (optional, default: GLOBAL_RNG) random number generator
seed – (optional, default: nothing) seed for reseeding

Output

The modified vector D.

Algorithm

This function implements Muller's method of normalized Gaussians [1] to uniformly sample over the $n$-dimensional sphere $S^n$ (which is the bounding surface of the $n$-dimensional unit ball).

Given $n$ canonical Gaussian random variables $Z₁, Z₂, …, Z_n$, the distribution of the vectors

\[\dfrac{1}{α}\left(z₁, z₂, …, z_n\right)^T,\]

where $α := \sqrt{z₁² + z₂² + … + z_n²}$, is uniform over $S^n$.

[1] Muller, Mervin E. A note on a method for generating points uniformly on n-dimensional spheres. Communications of the ACM 2.4 (1959): 19-20.

source

LazySets._sample_unit_nball_muller! — Function

_sample_unit_nball_muller!(D::Vector{Vector{N}}, n::Int, p::Int;
                           [rng]::AbstractRNG=GLOBAL_RNG,
                           [seed]::Union{Int, Nothing}=nothing) where {N}

Draw samples from a uniform distribution on an $n$-dimensional unit ball using Muller's method.

Input

D – output, vector of points
n – dimension of the ball
p – number of random samples
rng – (optional, default: GLOBAL_RNG) random number generator
seed – (optional, default: nothing) seed for reseeding

Output

The modified vector D.

Algorithm

This function implements Muller's method of normalized Gaussians [1] to uniformly sample from the interior of the unit ball.

Given $n$ Gaussian random variables $Z₁, Z₂, …, Z_n$ and a uniformly distributed random variable $r$ with support in $[0, 1]$, the distribution of the vectors

\[\dfrac{r^{1/n}}{α} \left(z₁, z₂, …, z_n\right)^T,\]

where $α := \sqrt{z₁² + z₂² + … + z_n²}$, is uniform over the $n$-dimensional unit ball.

[1] Muller, Mervin E. A note on a method for generating points uniformly on n-dimensional spheres. Communications of the ACM 2.4 (1959): 19-20.

source

LazySets.sample — Function

sample(B::Ball2{N}, [nsamples]::Int;
       [rng]::AbstractRNG=GLOBAL_RNG,
       [seed]::Union{Int, Nothing}=nothing) where {N}

Return samples from a uniform distribution on the given ball in the 2-norm.

Input

B – ball in the 2-norm
nsamples – number of random samples
rng – (optional, default: GLOBAL_RNG) random number generator
seed – (optional, default: nothing) seed for reseeding

Output

A linear array of nsamples elements drawn from a uniform distribution in B.

Algorithm

Random sampling with uniform distribution in B is computed using Muller's method of normalized Gaussians. This function requires the package Distributions. See _sample_unit_nball_muller! for implementation details.

source

sample(X::LazySet{N}, num_samples::Int;
       [sampler]=_default_sampler(X),
       [rng]::AbstractRNG=GLOBAL_RNG,
       [seed]::Union{Int, Nothing}=nothing,
       [include_vertices]=false,
       [VN]=Vector{N}) where {N}

Random sampling of an arbitrary set X.

Input

X – set to be sampled
num_samples – number of random samples
sampler – (optional, default: _default_sampler(X)) the sampler used; falls back to CombinedSampler
rng – (optional, default: GLOBAL_RNG) random number generator
seed – (optional, default: nothing) seed for reseeding
include_vertices – (optional, default: false) option to include the vertices of X
VN – (optional, default: Vector{N}) vector type of the sampled points

Output

A vector of num_samples vectors. If num_samples is not passed, the result is just one sample (not wrapped in a vector).

Algorithm

See the documentation of the respective Sampler.

Notes

If include_vertices == true, we include all vertices computed with vertices. Alternatively if a number $k$ is passed, we plot the first $k$ vertices returned by vertices(X).

source

LazySets.AbstractSampler — Type

AbstractSampler

Abstract type for defining new sampling methods.

Notes

All subtypes should implement a sample!(D, X, ::Method) method where the first argument is the output (vector of vectors), the second argument is the set to be sampled, and the third argument is the sampler instance.

source

LazySets.CombinedSampler — Type

CombinedSampler <: AbstractSampler

Type used for sampling arbitrary sets by trying different sampling strategies.

Algorithm

The algorithm is to first try a RejectionSampler 100 times. If that fails, it tries a RandomWalkSampler.

source

LazySets.FaceSampler — Type

FaceSampler <: AbstractSampler

Type used for sampling from the k-faces of a set.

Fields

dim – dimension of the faces to be sampled; a negative number is interpreted as n - dim where n is the dimension of the set

Notes

For a three-dimensional polytope, the following face dimensions exist:

3-face – the polytope itself
2-faces – 2-dimensional polygonal faces
1-faces – 1-dimensional edges
0-faces – 0-dimensional vertices

For more information see Wikipedia.

Algorithm

Currently only hyperrectangles are supported. For each point to be sampled, we randomly split the integers 1 .. n into two subgroups of size k and n-k respectively. For the i-th coordinate in the first group, we sample in the interval low(H, i) .. high(H, i). For the i-th coordinate in the second group, we randomly pick either low(H, i) or high(H, i).

source

LazySets.HalfSpaceSampler — Type

HalfSpaceSampler{D} <: AbstractSampler

Type used for sampling from a half-space.

Fields

distribution – (optional, default: nothing) distribution from which samples are drawn

Notes

If distribution is nothing (default), the sampling algorithm uses a DefaultUniform over $[0, 1]^n$.

source

LazySets.HyperplaneSampler — Type

HyperplaneSampler{D} <: AbstractSampler

Type used for sampling from a hyperplane.

Fields

distribution – (optional, default: nothing) distribution from which samples are drawn

Notes

If distribution is nothing (default), the sampling algorithm uses a DefaultUniform over $[0, 1]^n$.

source

LazySets.SingletonSampler — Type

SingletonSampler <: AbstractSampler

Type used for sampling from a singleton.

source

LazySets.RejectionSampler — Type

RejectionSampler{D} <: AbstractSampler

Type used for rejection sampling of a bounded set X.

Fields

distribution – (optional, default: DefaultUniform) distribution from which the sample is drawn
tight – (optional, default: false) set to true if the support of the distribution is known to coincide with the set X
maxiter – (optional, default: Inf) maximum number of iterations before giving up

Algorithm

Draw a sample $x$ from a given distribution of a box-overapproximation of the original set $X$ in all $n$ dimensions. The function rejects a drawn sample $x$ and redraws as long as the sample is not contained in the original set $X$, i.e., while $x ∉ X$.

Notes

The maxiter parameter is useful when sampling from sets that are small compared to their box approximation, e.g., flat sets, for which the probability of sampling from within the set is close to zero.

source

LazySets.RandomWalkSampler — Type

RandomWalkSampler <: AbstractSampler

Type used for sampling from a convex polytope using its vertex representation. This is especially useful if rejection sampling does not work because the polytope is flat.

Fields

variant – (optional, default: true) choice of a variant (see below)

Notes

The sampling is not uniform - points in the center of the polytope are more likely to be sampled.

The set to be sampled from must provide its vertices via vertices_list.

Algorithm

Choose a random convex combination of the vertices of a convex polytope X.

If variant == false, we proceed as follows. Let $V = \{v_i\}_i$ denote the set of vertices of X. Then any point $p \in \mathbb{R}^n$ of the convex polytope $X$ is a convex combination of its vertices, i.e., $p = \sum_{i} v_i α_i$ for some (non-negative) coefficients $\{α_i\}_i$ that add up to 1. The algorithm chooses a random convex combination (the $α_i$). To produce this combination, we apply the finite-difference operator on a sorted uniform sample over $[0, 1]$; the method can be found in [1] and [2].

If variant == true, we start from a random vertex and then repeatedly walk toward a random vertex inside the polytope.

References

[1] Rubin, Donald B. The Bayesian bootstrap. The annals of statistics (1981): 130-134.

[2] StackExchange post

source

LazySets.PolynomialZonotopeSampler — Type

PolynomialZonotopeSampler{D} <: AbstractSampler

Type used for sampling from polynomial zonotopes.

Fields

distribution – (optional, default: nothing) distribution from which samples are drawn

Notes

If distribution is nothing (default), the sampling algorithm uses a DefaultUniform over $[-1, 1]^n$.

source

Symbolics

LazySets._vec — Function

_vec(vars)

Transform a tuple of operations into one vector of operations.

Input

vars – tuple where each element is either variable-like (Num) or a vector of variables (Vector{Num})

Output

A vector of Operation obtained by concatenating each tuple component.

Examples

julia> using Symbolics

julia> vars = @variables x[1:2] y
2-element Vector{Any}:
  x[1:2]
 y

julia> LazySets._vec(vars)
3-element Vector{Num}:
 x[1]
 x[2]
    y

source

Functions for numbers

LazySets.sign_cadlag — Function

sign_cadlag(x::Real)

This function works like the sign function but is $1$ for input $0$.

Input

x – real scalar

Output

$1$ if $x ≥ 0$, $-1$ otherwise.

Notes

This is the sign function right-continuous at zero (see càdlàg function). It can be used with vector-valued arguments via the dot operator.

Examples

julia> LazySets.sign_cadlag.([-0.6, 1.3, 0.0])
3-element Vector{Float64}:
 -1.0
  1.0
  1.0

source

LazySets.minmax — Function

minmax(a, b, c)

Compute the minimum and maximum of three numbers a, b, c.

Input

a – number
b – number
c – number

Output

The minimum and maximum of three given numbers.

Examples

julia> LazySets.minmax(1.4, 52.4, -5.2)
(-5.2, 52.4)

source

LazySets.arg_minmax — Function

arg_minmax(a, b, c)

Compute the indices of the minimum and maximum of three numbers a, b, c.

Input

a – first number
b – second number
c – third number

Output

The indices of the minimum and maximum of the three given numbers.

Examples

julia> LazySets.arg_minmax(1.4, 52.4, -5.2)
(3, 2)

source

Other functions

LazySets._an_element_helper_hyperplane — Function

_an_element_helper_hyperplane(a::AbstractVector{N}, b,
                              [nonzero_entry_a]::Int) where {N}

Helper function that computes an element on a hyperplane $a⋅x = b$.

Input

a – normal direction
b – constraint
nonzero_entry_a – (optional, default: computes the first index) index i such that a[i] is different from 0

Output

An element on a hyperplane.

Algorithm

We compute the point on the hyperplane as follows:

We already found a nonzero entry of $a$ in dimension, say, $i$.
We set $x[i] = b / a[i]$.
We set $x[j] = 0$ for all $j ≠ i$.

source

LazySets.binary_search_constraints — Function

binary_search_constraints(d::AbstractVector{N},
                          constraints::Vector{<:HalfSpace{N}};
                          [start_index]::Int=div(length(constraints)+1, 2),
                          [choose_lower]::Bool=false) where {N}

Perform a binary search in the constraints.

Input

d – direction
constraints – constraints
start_index – (optional, default: div(length(constraints)+1, 2)) start index
choose_lower – (optional, default: false) flag for choosing the lower index (see the 'Output' section)

Output

In the default setting, the result is the smallest index k such that d ⪯ constraints[k].a, or length(constraints)+1 if no such k exists. If the choose_lower flag is set, the result is the largest index k such that constraints[k].a < d, which is equivalent to being k-1 in the normal setting.

source

LazySets.get_constrained_lowdimset — Function

get_constrained_lowdimset(cpa::CartesianProductArray{N, S},
                          P::AbstractPolyhedron{N}) where {N, S}

Preprocessing step for the intersection between a Cartesian product of a finite number of sets and a polyhedron.

Input

cpa – Cartesian product of a finite number of sets
P – polyhedron

Output

A four-tuple of:

a low-dimensional CartesianProductArray in the constrained dimensions of the original set cpa
the variables in the constrained blocks,
the original block structure of the low-dimensional sets,
the list of the constrained blocks.

source

LazySets.get_radius! — Function

get_radius!(sih::SymmetricIntervalHull{N}, i::Int) where {N}

Compute the radius of the symmetric interval hull of a set in a given dimension.

Input

sih – symmetric interval hull of a set
i – dimension in which the radius should be computed

Output

The radius of the symmetric interval hull of a set in a given dimension.

Algorithm

We ask for the extrema of the underlying set in dimension i.

source

LazySets.is_tighter_same_dir_2D — Function

is_tighter_same_dir_2D(c1::HalfSpace,
                       c2::HalfSpace;
                       [strict]::Bool=false)

Check if the first of two two-dimensional constraints with equivalent normal direction is tighter.

Input

c1 – first linear constraint
c2 – second linear constraint
strict – (optional; default: false) check for strictly tighter constraints?

Output

true iff the first constraint is tighter.

source

LazySets._leq_trig — Function

_leq_trig(u::AbstractVector{N}, v::AbstractVector{N}) where {N<:AbstractFloat}

Compare two 2D vectors by their direction.

Input

u – first 2D direction
v – second 2D direction

Output

true iff $\arg(u) [2π] ≤ \arg(v) [2π]$.

Notes

The argument is measured in counter-clockwise fashion, with the 0 being the direction (1, 0).

Algorithm

The implementation uses the arctangent function with sign, atan, which for two arguments implements the atan2 function.

source

LazySets.same_block_structure — Function

same_block_structure(x::AbstractVector{S1}, y::AbstractVector{S2}
                    ) where {S1<:LazySet, S2<:LazySet}

Check whether two vectors of sets have the same block structure, i.e., the $i$-th entry in the vectors have the same dimension.

Input

x – first vector
y – second vector

Output

true iff the vectors have the same block structure.

source

LazySets._σ_hyperplane_halfspace — Function

    _σ_hyperplane_halfspace(d::AbstractVector, a, b;
                            [error_unbounded]::Bool=true,
                            [halfspace]::Bool=false)

Return a support vector of a hyperplane $a⋅x = b$ in direction d.

Input

d – direction
a – normal direction
b – constraint
error_unbounded – (optional, default: true) true if an error should be thrown whenever the set is unbounded in the given direction
halfspace – (optional, default: false) true if the support vector should be computed for a half-space

Output

A pair (v, f) where v is a vector and f is a Boolean flag.

The flag f is false in one of the following cases:

The direction has norm zero.
The direction is (a multiple of) the hyperplane's normal direction.
The direction is (a multiple of) the opposite of the hyperplane's normal

direction and halfspace is false. In all these cases, v is any point on the hyperplane.

Otherwise, the flag f is true, the set is unbounded in the given direction, and v is any vector.

If error_unbounded is true and the set is unbounded in the given direction, this function throws an error instead of returning.

Notes

For correctness, consider the weak duality of LPs: If the primal is unbounded, then the dual is infeasible. Since there is only a single constraint, the feasible set of the dual problem is $a ⋅ y == d$, $y ≥ 0$ (with objective function $b ⋅ y$). It is easy to see that this problem is infeasible whenever $a$ is not parallel to $d$.

source

Utilities

Macros

Types

Inspection of set interfaces

File formats

Sampling

Symbolics

Functions for numbers

Other functions