Zonotope

Zonotope{N<:Real, 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

where $c \in \mathbb{R}^n$ is its center and $\{g_i\}_{i=1}^p$, $g_i \in \mathbb{R}^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 $\mathbb{R}^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 set of generators:

julia> Z = Zonotope([1.0, 0.0], [0.1 0.0; 0.0 0.1])
Zonotope{Float64,Array{Float64,1},Array{Float64,2}}([1.0, 0.0], [0.1 0.0; 0.0 0.1])

julia> dim(Z)
2

julia> center(Z)
2-element Array{Float64,1}:
 1.0
 0.0

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

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

We can collect its vertices using vertices_list:

julia> vertices_list(Z)
4-element Array{Array{Float64,1},1}:
 [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., 1.], Z)
2-element Array{Float64,1}:
 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., 1.], [1., 1.]])
Zonotope{Float64,Array{Float64,1},Array{Float64,2}}([1.0, 1.0], [1.0 0.0 1.0; 0.0 1.0 1.0])

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

center(Z::Zonotope{N}) where {N<:Real}

Return the center of a zonotope.

Input

• Z – zonotope

Output

The center of the zonotope.

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

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.

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

Concrete scaling of a zonotope.

Input

• α – scalar
• Z – zonotope

Output

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

ngens(Z::Zonotope)

Return the number of generators of a zonotope.

Input

• Z – zonotope

Output

Integer representing the number of generators.

togrep(Z::Zonotope)

Return a generator representation of a zonotope.

Input

• Z – zonotopic set

Output

The same set Z.

reduce_order(Z::Zonotope, r::Union{Integer, Rational})

Reduce the order of a zonotope by overapproximating with a zonotope with less generators.

Input

• Z – zonotope
• r – desired order

Output

A new zonotope with less generators, if possible.

Algorithm

See overapproximate(Z::Zonotope{N}, ::Type{<:Zonotope}, r::Union{Integer, Rational}) where {N<:Real} for details.

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

Return two zonotopes obtained by splitting the given zonotope.

Input

• Z – zonotope
• 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 [Prop. 3, 1], that we state next. The zonotope $Z = ⟨c, g^{(1, …, p)}⟩$ is split into:

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

[1] Althoff, M., Stursberg, O., & Buss, M. (2008). Reachability analysis of nonlinear systems with uncertain parameters using conservative linearization. In Proc. of the 47th IEEE Conference on Decision and Control.

remove_zero_generators(Z::Zonotope{N, VN, MN}) where {N<:Real,
                                                      VN<:AbstractVector{N},
                                                      MN<:AbstractMatrix{N}}

Return a new zonotope removing the generators which are zero of the given zonotope.

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.