Zonotope

Zonotope{N, VN<:AbstractVector{N}, MN<:AbstractMatrix{N}} <: AbstractZonotope{N}

Type that represents a zonotope.

Fields

• center – center of the zonotope
• generators – matrix; each column is a generator of the zonotope

Notes

Mathematically, a zonotope is defined as the set

\[Z = \left\{ x ∈ ℝ^n : x = 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.

Zonotopes can be constructed in two different ways: either passing the generators as a matrix, where each column represents a generator, or passing a list of vectors, where each vector represents a generator. Below we illustrate both ways.

Examples

A two-dimensional zonotope with given center and matrix of generators:

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> dim(Z)
2

julia> center(Z)
2-element Vector{Float64}:
 1.0
 0.0

julia> genmat(Z)
2×2 Matrix{Float64}:
 0.1  0.0
 0.0  0.1

Here, the first vector in the Zonotope constructor corresponds to the center and each column of the second argument corresponds to a generator. The functions center and genmat respectively return the center and the generator matrix of a zonotope.

We can collect the vertices using vertices_list:

julia> vertices_list(Z)
4-element Vector{Vector{Float64}}:
 [1.1, 0.1]
 [0.9, 0.1]
 [0.9, -0.1]
 [1.1, -0.1]

The support vector along a given direction can be computed using σ (resp. the support function can be computed using ρ):

julia> σ([1.0, 1.0], Z)
2-element Vector{Float64}:
 1.1
 0.1

Zonotopes admit an alternative constructor that receives a list of vectors, each vector representing a generator:

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

julia> genmat(Z)
2×3 Matrix{Float64}:
 1.0  0.0  1.0
 0.0  1.0  1.0

generators(Z::Zonotope)

Return an iterator over the generators of a zonotope.

Input

• Z – zonotope

Output

An iterator over the generators of Z.

genmat(Z::Zonotope)

Return the generator matrix of a zonotope.

Input

• Z – zonotope

Output

A matrix where each column represents one generator of the zonotope Z.

rand(T::Type{<:LazySet}; [N]::Type{<:Real}=Float64, [dim]::Int=2,
     [rng]::AbstractRNG=GLOBAL_RNG, [seed]::Union{Int, Nothing}=nothing
    )

Create a random set of the given set type.

Input

• T – set type
• N – (optional, default: Float64) numeric type
• dim – (optional, default: 2) dimension
• rng – (optional, default: GLOBAL_RNG) random number generator
• seed – (optional, default: nothing) seed for reseeding

Output

A random set of the given set type.

Extended help

rand(::Type{Zonotope}; [N]::Type{<:Real}=Float64, [dim]::Int=2,
     [rng]::AbstractRNG=GLOBAL_RNG, [seed]::Union{Int, Nothing}=nothing)

Algorithm

All numbers are normally distributed with mean 0 and standard deviation 1.

The number of generators can be controlled with the argument num_generators. For a negative value we choose a random number in the range dim:2*dim (except if dim == 1, in which case we only create a single generator).

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.

Extended help

remove_redundant_generators(Z::Zonotope)

Algorithm

This method normalizes each generator to have unit norm, sorts the normalized generators lexicographicaly, and then traverses them once to merge consecutive generators that are approximately collinear by summing them into a single generator.

For Rational inputs, we use a less efficient implementation: For each generator $g_j$ that has not been checked yet, we find all other generators that are linearly dependent with $g_j$. Then we combine those generators into a single generator.

For one-dimensional zonotopes we use a more efficient implementation where we just take the absolute sum of all generators.

Notes

The implementation may change the order of the non-removed generators.

remove_zero_generators(Z::Zonotope)

Return a new zonotope removing the generators that are zero.

Input

• Z – zonotope

Output

If there are no zero generators, the result is the original zonotope Z. Otherwise the result is a new zonotope that has the center and generators as Z except for those generators that are zero.

linear_map!(Zout::Zonotope, M::AbstractMatrix, Z::Zonotope)

Compute the concrete linear map of a zonotope, storing the result in Zout.

Input

• Zout – zonotope (output)
• M – matrix
• Z – zonotope

Output

The zonotope Zout, which is modified in-place.

scale!(α::Real, X::LazySet)

Scale a set by modifying it.

Input

• α – scalar
• X – set

Output

The scaled set representing $α ⋅ X$.

Extended help

scale!(α::Real, Z::Zonotope)

Algorithm

The result is obtained by applying the numerical scale to the center and generators.