Zonotopes (AbstractZonotope)

AbstractZonotope{N} <: AbstractCentrallySymmetricPolytope{N}

Abstract type for zonotopic sets.

Notes

Mathematically, a zonotope is defined as the set

\[Z = \left\{ c + ∑_{i=1}^p ξ_i g_i,~~ ξ_i ∈ [-1, 1]~~ ∀ i = 1,…, p \right\},\]

where $c ∈ ℝ^n$ is its center and $\{g_i\}_{i=1}^p$, $g_i ∈ ℝ^n$, is the set of generators. This characterization defines a zonotope as the finite Minkowski sum of line segments. Zonotopes can be equivalently described as the image of a unit infinity-norm ball in $ℝ^n$ by an affine transformation.

See Zonotope for a standard implementation of this interface.

Every concrete AbstractZonotope must define the following functions:

• generators(::AbstractZonotope) – return an iterator over the generators
• genmat(::AbstractZonotope) – return a generator matrix

Since the functions genmat and generators can be defined in terms of each other, it is sufficient to only genuinely implement one of them and let the implementation of the other function call the fallback implementation genmat_fallback resp. generators_fallback.

The subtypes of AbstractZonotope (including abstract interfaces):

julia> subtypes(AbstractZonotope)
5-element Vector{Any}:
 AbstractHyperrectangle
 HParallelotope
 LineSegment
 Zonotope
 ZonotopeMD

generators(Z::AbstractZonotope)

Return an iterator over the generators of a zonotopic set.

Input

• Z – zonotopic set

Output

An iterator over the generators of Z.

genmat(Z::AbstractZonotope)

Return a generator matrix of a zonotopic set.

Input

• Z – zonotopic set

Output

A generator matrix of Z.

constraints_list(X::LazySet)

Compute a list of linear constraints of a polyhedral set.

Input

• X – polyhedral set

Output

A list of the linear constraints of X.

Extended help

constraints_list(P::AbstractZonotope)

Algorithm

This is the (inefficient) fallback implementation for rational numbers. It first computes the vertices and then converts the corresponding polytope to constraint representation.

Extended help

constraints_list(Z::AbstractZonotope{<:AbstractFloat})

Notes

The main algorithm assumes that the generator matrix is full rank. The result has $2 \binom{p}{n-1}$ (with $p$ being the number of generators and $n$ being the ambient dimension) constraints, which is optimal under this assumption. If this assumption is not given, the implementation tries to work around.

Algorithm

We follow the algorithm presented in Althoff et al. [ASB10]. Three cases are not covered by that algorithm, so we handle them separately. The first case is zonotopes in one dimension. The second case is that there are fewer generators than dimensions, $p < n$, or the generator matrix is not full rank, in which case we fall back to the (slower) computation based on the vertex representation. The third case is that the zonotope is flat in some dimensions, in which case we project the zonotope to the non-flat dimensions and extend the result later.

ngens(Z::AbstractZonotope)

Return the number of generators of a zonotopic set.

Input

• Z – zonotopic set

Output

An integer representing the number of generators.

order(Z::AbstractZonotope)

Return the order of a zonotopic set.

Input

• Z – zonotopic set

Output

A rational number representing the order of the zonotopic set.

Notes

The order of a zonotopic set is defined as the quotient of its number of generators and its dimension.

reflect(X::LazySet)

Compute the reflection of a set in the origin.

Input

• X – set

Output

A set representing the reflection $-X$.

Extended help

reflect(Z::AbstractZonotope)

Algorithm

If $Z$ has center $c$ and generator matrix $G$, then $-Z$ has center $-c$ and generator matrix $G$. For the latter, observe that $G$ and $-G$ behave the same way.

remove_redundant_generators(Z::AbstractZonotope)

Remove all redundant (pairwise linearly dependent) generators of a zonotopic set.

Input

• Z – zonotopic set

Output

A new zonotope with fewer generators, or the same zonotopic set if no generator could be removed.

Algorithm

By default this implementation returns the input zonotopic set. Subtypes of AbstractZonotope whose generators can be removed have to define a new method.

togrep(Z::AbstractZonotope)

Return a generator representation of a zonotopic set.

Input

• Z – zonotopic set

Output

The same set in generator representation. This fallback implementation returns a Zonotope; however, more specific implementations may return other generator representations.

vertices_list(X::LazySet)

Compute a list of vertices of a polytopic set.

Input

• X – polytopic set

Output

A list of the vertices of X.

Extended help

vertices_list(Z::AbstractZonotope; [apply_convex_hull]::Bool=true)

Input

• apply_convex_hull – (optional, default: true) if true, post-process the computation with the convex hull of the points

Algorithm

Two-dimensional case

We use a trick to speed up enumerating vertices of 2-dimensional zonotopic sets with all generators in the first quadrant or third quadrant (same sign). Namely, sort the generators by angle and add them clockwise in increasing order and counterclockwise in decreasing order. A more detailed explanation can be found here.

To avoid the cumulative sum from both directions separately, we build a 2D index matrix to sum generators for both directions in one matrix-vector product.

General case

If the zonotopic set has $p$ generators, each vertex is the result of summing the center with some linear combination of generators, where the combination factors are $ξ_i ∈ \{-1, 1\}$.

There are at most $2^p$ distinct vertices. Use the flag apply_convex_hull to control whether a convex-hull algorithm is applied to the vertices computed by this method; otherwise, redundant vertices may be present.

∈(x::AbstractVector, X::LazySet)

Check whether a point lies in a set.

Input

• x – point/vector
• X – set

Output

true iff $x ∈ X$.

Extended help

∈(x::AbstractVector, Z::AbstractZonotope; solver=nothing)

Input

• solver – (optional, default: nothing) the backend used to solve the linear program

Examples

julia> Z = Zonotope([1.0, 0.0], [0.1 0.0; 0.0 0.1]);

julia> [1.0, 0.2] ∈ Z
false
julia> [1.0, 0.1] ∈ Z
true

Notes

If solver == nothing, we fall back to default_lp_solver(N).

Algorithm

The membership problem is reduced to the following linear program. Let $p$ and $n$ be the number of generators and ambient dimension, respectively. We consider the $p$-dimensional space of elements $(ξ_1, …, ξ_p)$ constrained to $ξ_i ∈ [-1, 1]$ for all $i = 1, …, p$ such that $x-c = Gξ$ holds.

linear_map(M::AbstractMatrix, X::LazySet)

Compute the linear map $M · X$.

Input

• M – matrix
• X – set

Output

A set representing the linear map $M · X$.

Extended help

linear_map(M::AbstractMatrix, Z::AbstractZonotope)

Output

A Zonotope.

Algorithm

We apply the linear map to the center and the generators.

If the map has output dimension 1, a specialized algorithm ensures that the resulting zonotope only has a single generator (or none if the map is zero).

reduce_order(Z::AbstractZonotope, r::Real,
             [method]::AbstractReductionMethod=GIR05())

Reduce the order of a zonotopic set by overapproximating with a zonotope with fewer generators.

Input

• Z – zonotopic set
• r – desired order
• method – (optional, default: GIR05()) the reduction method used

Output

A new zonotope with fewer generators, if possible.

Algorithm

The available algorithms are:

julia> subtypes(AbstractReductionMethod)
4-element Vector{Any}:
 LazySets.ASB10
 LazySets.COMB03
 LazySets.GIR05
 LazySets.SRMB16

See the documentation of each algorithm for references. Most methods split the given zonotopic set Z into two zonotopes, K and L, where K contains the most "representative" generators and L contains the generators that are reduced, Lred, using a box overapproximation. This methodology varies slightly for SRMB16. We follow the notation from Yang and Scott [YS18]. See also Kopetzki et al. [KSA17].

split(Z::AbstractZonotope, j::Int)

Return two zonotopes obtained by splitting the given zonotopic set.

Input

• Z – zonotopic set
• j – index of the generator to be split

Output

The zonotope obtained by splitting Z into two zonotopes such that their union is Z and their intersection is possibly non-empty.

Algorithm

This function implements Althoff et al. [ASB08], Prop. 3, which we state next. The zonotopic set $Z = ⟨c, g^{(1, …, p)}⟩$ is split into:

\[Z₁ = ⟨c - \frac{1}{2}g^{(j)}, (g^{(1, …,j-1)}, \frac{1}{2}g^{(j)}, g^{(j+1, …, p)})⟩ \\ Z₂ = ⟨c + \frac{1}{2}g^{(j)}, (g^{(1, …,j-1)}, \frac{1}{2}g^{(j)}, g^{(j+1, …, p)})⟩,\]

such that $Z₁ ∪ Z₂ = Z$ and $Z₁ ∩ Z₂ = Z^*$, where

\[Z^* = ⟨c, (g^{(1,…,j-1)}, g^{(j+1,…, p)})⟩.\]

split(Z::AbstractZonotope, gens::AbstractVector{Int},
      nparts::AbstractVector{Int})

Split a zonotopic set along the given generators into a vector of zonotopes.

Input

• Z – zonotopic set
• gens – vector of indices of the generators to be split
• n – vector of integers describing the number of partitions in the corresponding generator

Output

The zonotopes obtained by splitting Z into 2^{n_i} zonotopes for each generator i such that their union is Z and their intersection is possibly non-empty.

Examples

Splitting of a two-dimensional zonotopic set along its first generator:

julia> Z = Zonotope([1.0, 0.0], [0.1 0.0; 0.0 0.1])
Zonotope{Float64, Vector{Float64}, Matrix{Float64}}([1.0, 0.0], [0.1 0.0; 0.0 0.1])

julia> split(Z, [1], [1])
2-element Vector{Zonotope{Float64, Vector{Float64}, Matrix{Float64}}}:
 Zonotope{Float64, Vector{Float64}, Matrix{Float64}}([0.95, 0.0], [0.05 0.0; 0.0 0.1])
 Zonotope{Float64, Vector{Float64}, Matrix{Float64}}([1.05, 0.0], [0.05 0.0; 0.0 0.1])

Here, the first vector in the arguments corresponds to the zonotopic set's generator to be split, and the second vector corresponds to the exponent of 2^n parts that the set will be split into along the corresponding generator.

As an example, below we split a two-dimensional zonotope along both of its generators, each time into four parts.

julia> Z = Zonotope([1.0, 0.0], [0.1 0.0; 0.0 0.1])
Zonotope{Float64, Vector{Float64}, Matrix{Float64}}([1.0, 0.0], [0.1 0.0; 0.0 0.1])

julia> split(Z, [1, 2], [2, 2])
16-element Vector{Zonotope{Float64, Vector{Float64}, Matrix{Float64}}}:
Zonotope{Float64, Vector{Float64}, Matrix{Float64}}([0.925, -0.075], [0.025 0.0; 0.0 0.025])
Zonotope{Float64, Vector{Float64}, Matrix{Float64}}([0.925, -0.025], [0.025 0.0; 0.0 0.025])
Zonotope{Float64, Vector{Float64}, Matrix{Float64}}([0.925, 0.025], [0.025 0.0; 0.0 0.025])
Zonotope{Float64, Vector{Float64}, Matrix{Float64}}([0.925, 0.075], [0.025 0.0; 0.0 0.025])
Zonotope{Float64, Vector{Float64}, Matrix{Float64}}([0.975, -0.075], [0.025 0.0; 0.0 0.025])
Zonotope{Float64, Vector{Float64}, Matrix{Float64}}([0.975, -0.025], [0.025 0.0; 0.0 0.025])
Zonotope{Float64, Vector{Float64}, Matrix{Float64}}([0.975, 0.025], [0.025 0.0; 0.0 0.025])
Zonotope{Float64, Vector{Float64}, Matrix{Float64}}([0.975, 0.075], [0.025 0.0; 0.0 0.025])
Zonotope{Float64, Vector{Float64}, Matrix{Float64}}([1.025, -0.075], [0.025 0.0; 0.0 0.025])
Zonotope{Float64, Vector{Float64}, Matrix{Float64}}([1.025, -0.025], [0.025 0.0; 0.0 0.025])
Zonotope{Float64, Vector{Float64}, Matrix{Float64}}([1.025, 0.025], [0.025 0.0; 0.0 0.025])
Zonotope{Float64, Vector{Float64}, Matrix{Float64}}([1.025, 0.075], [0.025 0.0; 0.0 0.025])
Zonotope{Float64, Vector{Float64}, Matrix{Float64}}([1.075, -0.075], [0.025 0.0; 0.0 0.025])
Zonotope{Float64, Vector{Float64}, Matrix{Float64}}([1.075, -0.025], [0.025 0.0; 0.0 0.025])
Zonotope{Float64, Vector{Float64}, Matrix{Float64}}([1.075, 0.025], [0.025 0.0; 0.0 0.025])
Zonotope{Float64, Vector{Float64}, Matrix{Float64}}([1.075, 0.075], [0.025 0.0; 0.0 0.025])

ρ(d::AbstractVector, X::LazySet)

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

Input

• d – direction
• X – set

Output

The evaluation of the support function of X in direction d.

Notes

The convenience alias support_function is also available.

We have the following identity based on the support vector $σ$:

\[ ρ(d, X) = d ⋅ σ(d, X)\]

Extended help

ρ(d::AbstractVector, Z::AbstractZonotope)

Algorithm

The support value is $cᵀ d + ‖Gᵀ d‖₁$, where $c$ is the center and $G$ is the generator matrix of Z.

σ(d::AbstractVector, X::LazySet)

Compute a support vector of a set in a given direction.

Input

• d – direction
• X – set

Output

A support vector of X in direction d.

Notes

The convenience alias support_vector is also available.

Extended help

σ(d::AbstractVector, Z::AbstractZonotope)

Notes

If the direction has norm zero, the vertex with $ξ_i = 1 \ \ ∀ i = 1,…, p$ is returned.

isdisjoint(X::LazySet, Y::LazySet, [witness]::Bool=false)

Check whether two sets are disjoint (i.e., do not intersect), and optionally compute a witness.

Input

• X – set
• Y – set
• witness – (optional, default: false) compute a witness if activated

Output

• If the witness option is deactivated: true iff $X ∩ Y = ∅$
• If the witness option is activated:
  • (true, []) iff $X ∩ Y = ∅$
  • (false, v) iff $X ∩ Y ≠ ∅$ for some $v ∈ X ∩ Y$

Notes

The convenience alias is_intersection_empty is also available.

Extended help

isdisjoint(Z1::AbstractZonotope, Z2::AbstractZonotope,
           [witness]::Bool=false; [solver]=nothing)

Input

• solver – (optional, default: nothing) the backend used to solve the linear program

Algorithm

The algorithm is taken from Guibas et al. [GNZ03].

$Z1 ∩ Z2 = ∅$ iff $c_1 - c_2 ∉ Z(0, [g_1, g_2])$, where $c_i$ and $g_i$ are the center and generators of zonotope Zi and $Z(c, g)$ represents the zonotope with center $c$ and generators $g$.

minkowski_difference(X::LazySet, Y::LazySet)

Compute the Minkowski difference of two sets.

Input

• X – set
• Y – set

Output

A set representing the Minkowski difference $X ⊖ Y$.

Notes

The Minkowski difference of two sets $X$ and $Y$ is defined as

\[ X ⊖ Y = \{z \mid \{z\} ⊕ Y ⊆ X\}\]

The convenience alias pontryagin_difference is also available.

There is some inconsistency in the literature regarding the naming conventions. In this library, both Minkowski difference and Pontryagin difference refer to the geometric difference of two sets.

Extended help

minkowski_difference(Z1::AbstractZonotope, Z2::AbstractZonotope)

Output

An HPolytope.

Algorithm

For one-dimensional sets, this method implements a simple algorithm for intervals. For two-dimensional sets, this method implements Althoff [Alt15], Proposition 6. For higher-dimensional sets, this method implements Althoff [Alt15], Theorem 3.

minkowski_sum(X::LazySet, Y::LazySet)

Compute the Minkowski sum of two sets.

Input

• X – set
• Y – set

Output

A set representing the Minkowski sum $X ⊕ Y$.

Notes

The Minkowski sum of two sets $X$ and $Y$ is defined as

\[ X ⊕ Y = \{x + y \mid x ∈ X, y ∈ Y\}.\]

Extended help

minkowski_sum(Z1::AbstractZonotope, Z2::AbstractZonotope)

Algorithm

The resulting zonotope is obtained by summing up the centers and concatenating the generators of Z1 and Z2.

norm(X::LazySet, [p]::Real=Inf)

Return the norm of a set.

Input

• X – set
• p – (optional, default: Inf) norm

Output

A real number representing the norm.

Notes

The norm of a set is the norm of the enclosing ball (of the given $p$-norm) of minimal volume that is centered in the origin.

norm(Z::AbstractZonotope, p::Real=Inf)

Compute the $ℓ_p$ norm of a zonotope.

generators_fallback(Z::AbstractZonotope)

Fallback definition of generators for zonotopic sets.

Input

• Z – zonotopic set

Output

An iterator over the generators of Z.

genmat_fallback(Z::AbstractZonotope; [gens]=generators(Z), [ngens]=nothing)

Fallback definition of genmat for zonotopic sets.

Input

• Z – zonotopic set
• gens – (optional; default: generators(Z)) iterator over generators
• ngens – (optional; default: nothing) number of generators or nothing if unknown

Output

A matrix where each column represents one generator of Z.

Notes

Passing the number of generators (ngens) is more efficient, since otherwise the generators have to be obtained from the iterator (gens) and stored in an intermediate vector until the final result matrix can be allocated.

_l1_norm(Z::AbstractZonotope)

Compute the exact $ℓ₁$ norm of a zonotope with generator matrix $G ∈ \mathbb{R}^{d×n}$

Notes

The function exploits the fact that the mapping $ξ ↦ ‖ c + ∑_{i=1}^n ξ_i g_i ‖_1$ is a convex function of the coefficients $ξ_i$. As a result, its maximum over the hypercube $[-1,1]^n$ is attained at one of the $2^n$ corners.

This algorithm has time complexity $\mathcal{O}(2ⁿ · d)$, and thus is only practical for zonotopes with a small number of generators.

AbstractReductionMethod

Abstract supertype for order-reduction methods of a zonotopic set.

ASB10 <: AbstractReductionMethod

Zonotope order-reduction method from Althoff et al. [ASB10].

COMB03 <: AbstractReductionMethod

Zonotope order-reduction method from Combastel [Com03].

GIR05 <: AbstractReductionMethod

Zonotope order-reduction method from Girard [Gir05].

SRMB16 <: AbstractReductionMethod

Zonotope order-reduction method from Scott et al. [SRMB16].

Fields

• ϵ – (optional; default: 1e-6) pivot threshold
• δ – (optional; default: 1e-3) volume threshold

Notes

The method reorders the generator matrix using reduced row echelon form (rref) to the form $[T ~ V]$, then iteratively removes one generator from $V$ while updating $T$.