AbstractMatrixZonotope{N}

Abstract supertype for all matrix zonotope representations.

Every concrete AbstractSparsePolynomialZonotope must define the following functions:

• size(::AbstractSparsePolynomialZonotope, [dim]) – return the size of the matrix zonotope

size(::AbstractMatrixZonotope, [dim])

Return a tuple containing the dimensions of a matrix zonotope. Optionally you can specify a dimension to just get the length of that dimension.

MatrixZonotope{N, MN<:AbstractMatrix{N}}(A0::MN, Ai::Vector{MN},
                idx::Vector{Int}=collect(1:length(Aᵢ))) <: AbstractMatrixZonotope{N}

Type that represents a matrix zonotope.

Fields

• A0 – center of the matrix zonotope
• Ai – vector of matrices; each matrix is a generator of the matrix zonotope
• idx – identifier vector of positive integers for each factor

Notes

Mathematically a matrix zonotope is defined as the set of matrices

\[\mathcal{A} = \left\{A ∈ ℝ^{n×m} : A^{(0)} + ∑_{i=1}^p ξ_i A^{(i)},~~ ξ_i ∈ [-1, 1]~~ ∀ i = 1,…, p \right\},\]

It can be written in shorthand notation as ``\mathcal{A} = \braket{A^{(0)},A^{(1)}, ..., A^{(p)} }_{MZ}. Matrix zonotopes were introduced in Althoff et al. [ALK11].

Examples

julia> A0 = [2.0 1.0; -1.0 0.0];

julia> Ai = [[1.0 -1.0; 0.0 -1.0], [0.0 2.0; -1.0 1.0]];

julia> idx = [1, 3];

julia> MZ = MatrixZonotope(A0, Ai, idx)
MatrixZonotope{Float64, Matrix{Float64}}([2.0 1.0; -1.0 0.0], [[1.0 -1.0; 0.0 -1.0], [0.0 2.0; -1.0 1.0]], [1, 3])

center(MZ::MatrixZonotope)

Return the center matrix of a matrix zonotope.

Input

• MZ – matrix zonotope

Output

The center matrix of MZ.

generators(MZ::MatrixZonotope)

Return the generators of a matrix zonotope.

Input

• MZ – matrix zonotope

Output

The generators of MZ.

indexvector(MZ::MatrixZonotope)

Return the index vector of a matrix zonotope.

Input

• MZ – matrix zonotope

Output

A vector of unique positive integers representing each generator.

order(MZ::MatrixZonotope)

Return the order of a matrix zonotope.

Input

• MZ – matrix zonotope

Output

A rational number representing the order of the matrix zonotope.

Notes

The order of a matrix zonotope is defined as the quotient of its number of generators and the product of its dimensions. Alternatively it can be thought as the order of the zonotopic set constructed from the vectorization of the center and the generators.

transpose(MZ::MatrixZonotope)

Return the transpose of a matrix zonotope.

Notes

The transpose of a matrix zonotope is defined as:

\[ \mathcal{A}ᵀ = \braket{(A^{(0)})ᵀ,(A^{(1)})ᵀ, \dots, (A^{(p)})ᵀ }\]

ngens(MZ::MatrixZonotope)

Return the number of generators of a matrix zonotope.

Input

• MZ – matrix zonotope

Output

An integer representing the number of generators.

minkowski_sum(A::MatrixZonotope, B::MatrixZonotope)

Compute the minkowski sum of two matrix zonotopes.

Input

• A – a matrix zonotope
• B – a matrix zonotope

Output

A matrix zonotope representing the minkowski sum between matrix zonotopes.

remove_redundant_generators(MZ::MatrixZonotope)

Remove redundant generators from a matrix zonotope.

Input

• MZ – a matrix zonotope

Output

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

Algorithm

This function first vectorizes the matrix zonotope into a standard zonotope, removes redundant generators from the resulting zonotope, and then converts it back to a matrix zonotope of the original dimensions.

Extended help

remove_redundant_generators(Z::Zonotope)

reduce_order(MZ::MatrixZonotope, r::Real,
             [method]::AbstractReductionMethod=GIR05())

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

Input

• MZ – matrix zonotope
• r – desired order
• method – (optional, default: GIR05()) the reduction method used

Output

A new zonotope with fewer generators, if possible.

Algorithm

This function first vectorizes the matrix zonotope into a standard zonotope, reduces the order of the resulting zonotope, and then converts it back to a matrix zonotope of the original dimensions.

Extended help

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

Extended help

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

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 1:maximum(dim).

norm(MZ::MatrixZonotope, p::Real=Inf)

Compute the operator $p$-norm of a matrix zonotope.

Input

• MZ – matrix zonotope
• p – (optional, default: Inf) norm

Output

A real number representing the norm.

Notes

For a matrix zonotope \mathcal{A}, itsp`-norm is defined as

\[‖\mathcal{A}‖_p = \sup_{A \in \mathcal{A}} ‖A‖_p\]

where $‖A‖_p$ denotes the induced matrix norm.

linear_map(M::AbstractMatrix, MZ::MatrixZonotope)

Apply a linear transformation to a matrix zonotope from the left.

Input

• M – a linear map / matrix
• MZ – a matrix zonotope

Output

A matrix zonotope with transformed center and generators

linear_map(M::AbstractMatrix, MZ::MatrixZonotope)

Apply a linear transformation to a matrix zonotope from the right.

Input

• M – a linear map / matrix
• MZ – a matrix zonotope

Output

A matrix zonotope with transformed center and generators

_rowwise_zonotope_norm(MZ::MatrixZonotope{N}, norm_fn::Function) where {N}

Compute the induced matrix norm of a matrix zonotope by reducing to row-wise zonotope $ℓ₁$ norms.

Input

• MZ – matrix zonotope
• norm_fn – function to approximate the zonotope $ℓ₁$ norm

Output

The induced matrix $p$-norm of the matrix zonotope.

Algorithm

For each row index $i = 1, ..., n$, we construct a zonotope with center given by the $i$-th row of the center matrix and as generators the $i$-th row of each generator matrix. The norm of this zonotope is then computed using the provided norm_fn. The final result is the maximum of these $n$ row-wise zonotope norms.

vectorize(MZ::MatrixZonotope)

Vectorize a matrix zonotope to transform it into a zonotope.

Input

• MZ – a matrix zonotope

Output

A zonotope.

matrixize(Z::Zonotope, dims::Tuple{Int,Int})

Reshape a zonotope to transform it into a matrix zonotope.

Input

• Z – a zonotope
• dims – target dimensions of the matrix zonotope

Output

A matrix zonotope.

MatrixZonotopeProduct{N}(factors::Vector{<:MatrixZonotope{N}}) <: AbstractMatrixZonotope{N}

Represents the product of multiple matrix zonotopes.

Fields

• factors – a vector of matrix zonotopes [A1, A2, ..., An]

Notes

Mathematically, this represents the set:

\[\mathcal{C} = \{ A_1 A_2 \dots A_n ~|~ A_i \in \mathcal{A}_i \}\]

factors(MZP::MatrixZonotopeProduct)

Return the factors of a matrix zonotope product.

nfactors(MZP::MatrixZonotopeProduct)

Return the number of factors of a matrix zonotope product.

MatrixZonotopeExp{N}(MZ::AbstractMatrixZonotope{N}) <: AbstractMatrixZonotope{N}

Represents the matrix exponential of a matrix zonotope.

Fields

• M – a square matrix zonotope representing the exponent.

Notes

Mathematically, this represents the set:

\[\mathcal{C} = \{ \exp(M) ~|~ M \in \mathcal{M} \}\]