SparsePolynomialZonotope

SparsePolynomialZonotope{N, VN<:AbstractVector{N}, MN<:AbstractMatrix{N},
                         MNI<:AbstractMatrix{N},
                         ME<:AbstractMatrix{Int},
                         VI<:AbstractVector{Int}}
    <: AbstractSparsePolynomialZonotope{N}

Type that represents a sparse polynomial zonotope.

A sparse polynomial zonotope $\mathcal{PZ} ⊂ ℝ^n$ is represented by the set

\[\mathcal{PZ} = \left\{x ∈ ℝ^n : x = c + ∑ᵢ₌₁ʰ\left(∏ₖ₌₁ᵖ α_k^{E_{k, i}} \right)Gᵢ+∑ⱼ₌₁^qβⱼGIⱼ,~~ α_k, βⱼ ∈ [-1, 1],~~ ∀ k = 1,…,p, j=1,…,q \right\},\]

where $c ∈ ℝ^n$ is the offset vector (or center), $Gᵢ ∈ ℝ^{n}$ are the dependent generators, $GIⱼ ∈ ℝ^{n}$ are the independent generators, and $E ∈ \mathbb{N}^{p×h}_{≥0}$ is the exponent matrix with matrix elements $E_{k, i}$.

In the implementation, $Gᵢ ∈ ℝ^n$ are arranged as columns of the dependent generator matrix $G ∈ ℝ^{n × h}$, and similarly $GIⱼ ∈ ℝ^{n}$ are arranged as columns of the independent generator matrix $GI ∈ ℝ^{n×q}$.

The shorthand notation $\mathcal{PZ} = ⟨ c, G, GI, E, idx ⟩$ is often used, where $idx ∈ \mathbb{N}^p$ is a list of non-repeated natural numbers storing a unique identifier for each dependent factor $αₖ$.

Fields

• c – offset vector
• G – dependent generator matrix
• GI – independent generator matrix
• E – exponent matrix
• idx – identifier vector of positive integers for the dependent parameters

Notes

Sparse polynomial zonotopes were introduced in Kochdumper and Althoff [KA21].

expmat(P::SparsePolynomialZonotope)

Return the matrix of exponents of the sparse polynomial zonotope.

Input

• P – sparse polynomial zonotope

Output

The matrix of exponents, where each column is a multidegree.

Notes

In the exponent matrix, each row corresponds to a parameter ($αₖ$ in the definition) and each column to a monomial.

genmat_dep(P::SparsePolynomialZonotope)

Return the matrix of dependent generators of a sparse polynomial zonotope.

Input

• P – sparse polynomial zonotope

Output

The matrix of dependent generators.

genmat_indep(P::SparsePolynomialZonotope)

Return the matrix of independent generators of a sparse polynomial zonotope.

Input

• P – sparse polynomial zonotope

Output

The matrix of independent generators.

indexvector(P::SparsePolynomialZonotope)

Return the index vector of a sparse polynomial zonotope.

Input

• P – sparse polynomial zonotope

Output

The index vector.

Notes

The index vector contains positive integers for the dependent parameters.

polynomial_order(P::SPZ)

Return the polynomial order of a sparse polynomial zonotope.

Input

• P – sparse polynomial zonotope

Output

The polynomial order.

Notes

The polynomial order is the maximum sum of all monomials' parameter exponents.

rand(::Type{SparsePolynomialZonotope}; [N]::Type{<:Real}=Float64,
     [dim]::Int=2, [nparams]::Int=2, [maxdeg]::Int=3,
     [num_dependent_generators]::Int=-1,
     [num_independent_generators]::Int=-1, [rng]::AbstractRNG=GLOBAL_RNG,
     [seed]::Union{Int, Nothing}=nothing)

Create a random sparse polynomial zonotope.

Input

• SparsePolynomialZonotope – type for dispatch
• N – (optional, default: Float64) numeric type
• dim – (optional, default: 2) dimension
• nparams – (optional, default: 2) number of parameters
• maxdeg – (optional, default: 3) maximum degree for each parameter
• num_dependent_generators – (optional, default: -1) number of dependent generators (see comment below)
• num_independent_generators – (optional, default: -1) number of independent generators (see comment below)
• rng – (optional, default: GLOBAL_RNG) random number generator
• seed – (optional, default: nothing) seed for reseeding

Output

A random sparse polynomial zonotope.

Algorithm

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

The number of generators can be controlled with the arguments num_dependent_generators and num_dependent_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). Note that the final number of generators may be lower if redundant monomials are generated.

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(S::SparsePolynomialZonotope)

Notes

The result uses dense arrays irrespective of the array type of S.

Algorithm

Let G be the dependent generator matrix, E the exponent matrix, and GI the independent generator matrix of S. We perform the following simplifications:

• Remove zero columns in G and the corresponding columns in E.
• Remove Zero columns in GI.
• For zero columns in E, add the corresponding column in G to the center.
• Group repeated columns in E together by summing the corresponding columns in G.

uniqueID(n::Int)

Return a collection of n unique identifiers (integers 1, …, n).

Input

• n – number of variables

Output

1:n.

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)
3-element Vector{Any}:
 LazySets.ASB10
 LazySets.COMB03
 LazySets.GIR05

See the documentation of each algorithm for references. These 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. We follow the notation from Yang and Scott [YS18]. See also Kopetzki et al. [KSA17].

Extended help

reduce_order(P::SparsePolynomialZonotope, r::Real,
             [method]::AbstractReductionMethod=GIR05())

Notes

This method implements the algorithm described in Kochdumper [Koc22], Proposition 3.1.39.

ρ(d::AbstractVector, P::SparsePolynomialZonotope; [enclosure_method]=nothing)

Bound the support function of $P$ in the direction $d$.

Input

• d – direction
• P – sparse polynomial zonotope
• enclosure_method – (optional; default: nothing) method to use for enclosure; an AbstractEnclosureAlgorithm from the Rangeenclosures.jl package

Output

An overapproximation of the support function in the given direction.

Algorithm

This method implements Kochdumper [Koc22], Proposition 3.1.16.

cartesian_product(X::LazySet, Y::LazySet)

Compute the Cartesian product of two sets.

Input

• X – set
• Y – set

Output

A set representing the Cartesian product $X × Y$.

Notes

The Cartesian product of two sets $X$ and $Y$ is defined as

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

Extended help

cartesian_product(P1::SparsePolynomialZonotope, P2::SparsePolynomialZonotope)

Algorithm

This method implements Kochdumper [Koc22], Proposition 3.1.22.

exact_sum(X::LazySet, Y::LazySet)

Compute the exact sum of two parametric sets.

Input

• X – parametric set
• Y – parametric set

Output

A set representing the exact sum, sometimes written $X ⊞ Y$.

Notes

For parametric sets, the exact sum behaves like the Minkowski sum, except that the parameters are shared. Thus, for nonparametric sets, it coincides with the Minkowski sum.

Extended help

exact_sum(P1::SparsePolynomialZonotope, P2::SparsePolynomialZonotope)

Algorithm

This method implements Kochdumper [Koc22], Proposition 3.1.20.

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(P1::SparsePolynomialZonotope, P2::SparsePolynomialZonotope)

Algorithm

See Kochdumper [Koc22], Proposition 3.1.19.