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

convert(::Type{Zonotope}, Z::AbstractZonotope)

Convert a zonotopic set to a zonotope.

Input

• Zonotope – target type
• H – zonotopic set

Output

A zonotope.

center(Z::Zonotope)

Return the center of a zonotope.

Input

• Z – zonotope

Output

The center of the zonotope.

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.

high(Z::Zonotope, i::Int)

Return the higher coordinate of a zonotope in a given dimension.

Input

• Z – zonotope
• i – dimension of interest

Output

The higher coordinate of the zonotope in the given dimension.

low(Z::Zonotope, i::Int)

Return the lower coordinate of a zonotope in a given dimension.

Input

• Z – zonotope
• i – dimension of interest

Output

The lower coordinate of the zonotope in the given dimension.

ngens(Z::Zonotope)

Return the number of generators of a zonotope.

Input

• Z – zonotope

Output

An integer representing the number of generators.

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

Create a random zonotope.

Input

• Zonotope – type for dispatch
• 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
• num_generators – (optional, default: -1) number of generators of the zonotope (see the comment below)

Output

A random zonotope.

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::Zonotope{N}) where {N}

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

Input

• Z – zonotope

Output

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

Algorithm

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.

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.

togrep(Z::Zonotope)

Return a generator representation of a zonotope.

Input

• Z – zonotope

Output

The same set Z.

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, Z::Zonotope)

Concrete scaling of a zonotope modifying Z in-place.

Input

• α – scalar
• Z – zonotope

Output

The zonotope obtained by applying the numerical scale to the center and generators of $Z$.

translate!(Z::Zonotope, v::AbstractVector)

Translate (i.e., shift) a zonotope by a given vector in-place.

Input

• Z – zonotope
• v – translation vector

Output

A translated zonotope.

Notes

See also LazySets.API.translate(Z::LazySet, v::AbstractVector) for the out-of-place version.

Algorithm

We add the translation vector to the center of the zonotope.