SimpleSparsePolynomialZonotope

SimpleSparsePolynomialZonotope{N, VN<:AbstractVector{N},
                               MN<:AbstractMatrix{N},
                               ME<:AbstractMatrix{Int}}
    <: AbstractSparsePolynomialZonotope{N}

Type that represents a sparse polynomial zonotope that is simple in the sense that there is no distinction between independent and dependent generators.

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

\[\mathcal{PZ} = \left\{x ∈ ℝ^n : x = c + ∑_{i=1}^h \left(∏_{k=1}^p α_k^{E_{k, i}} \right) g_i,~~ α_k ∈ [-1, 1]~~ ∀ i = 1,…,p \right\},\]

where $c ∈ ℝ^n$ is the offset vector (or center), $G ∈ ℝ^{n × h}$ is the generator matrix with columns $g_i$ (each $g_i$ is called a generator), and where $E ∈ \mathbb{N}^{p×h}_{≥0}$ is the exponent matrix with matrix elements $E_{k, i}$.

Fields

• c – offset vector
• G – generator matrix
• E – exponent matrix

Notes

Sparse polynomial zonotopes were introduced in [1]. The simple variation was defined in [2].

• [1] N. Kochdumper and M. Althoff. *Sparse Polynomial Zonotopes: A Novel Set

Representation for Reachability Analysis*. Transactions on Automatic Control,

• [2] N. Kochdumper. Challenge Problem 5: Polynomial Zonotopes in Julia.

JuliaReach and JuliaIntervals Days 3, 2021.

PolynomialZonotope = SimpleSparsePolynomialZonotope

Alias for SimpleSparsePolynomialZonotope.

convex_hull(X::LazySet)

Compute the convex hull of a set.

Input

• X – set

Output

A set representing the convex hull of X.

Notes

The convex hull of a set $X$ is defined as

\[ \{λx + (1-λ)y \mid x, y ∈ X, λ ∈ [0, 1]\}.\]

Extended help

convex_hull(P::SimpleSparsePolynomialZonotope)

Output

The tightest convex simple sparse polynomial zonotope containing P.

expmat(P::SimpleSparsePolynomialZonotope)

Return the matrix of exponents of a simple sparse polynomial zonotope.

Input

• P – simple 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 ($lpha_k$ in the mathematical set definition) and each column corresponds to a monomial.

Examples

julia> S = SimpleSparsePolynomialZonotope([2.0, 0], [1 2;2 2.], [1 4;1 2])
SimpleSparsePolynomialZonotope{Float64, Vector{Float64}, Matrix{Float64}, Matrix{Int64}}([2.0, 0.0], [1.0 2.0; 2.0 2.0], [1 4; 1 2])

julia> expmat(S)
2×2 Matrix{Int64}:
 1  4
 1  2

ngens(Z::AbstractZonotope)

Return the number of generators of a zonotopic set.

Input

• Z – zonotopic set

Output

An integer representing the number of generators.

Extended help

ngens(P::SimpleSparsePolynomialZonotope)

Notes

This number corresponds to the number of monomials in the polynomial representation of P.

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{SimpleSparsePolynomialZonotope};
     [N]::Type{<:Real}=Float64, [dim]::Int=2, [nparams]::Int=2,
     [maxdeg]::Int=3, [num_generators]::Int=-1,
     [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). 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.

remove_redundant_generators(S::SimpleSparsePolynomialZonotope)

Remove redundant generators from a simple sparse polynomial zonotope.

Input

• S – simple sparse polynomial zonotope

Output

A new simple sparse polynomial zonotope such that redundant generators have been removed.

Notes

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

Algorithm

Let G be the generator matrix and E the exponent matrix of S. The following simplifications are performed:

• Zero columns in G and the corresponding columns in E are removed.
• For zero columns in E, the corresponding column in G is summed to the center.
• Repeated columns in E are grouped together by summing the corresponding columns in G.

quadratic_map(Q::Vector{<:AbstractMatrix}, S::SimpleSparsePolynomialZonotope)

Return the quadratic map of a simple sparse polynomial zonotope.

Input

• Q – vector of square matrices
• S – simple sparse polynomial zonotope

Output

The quadratic map of P represented as a simple sparse polynomial zonotope.

Algorithm

This method implements Proposition 12 in [1]. See also Proposition 3.1.30 in [2].

[1] N. Kochdumper, M. Althoff. Sparse polynomial zonotopes: A novel set representation for reachability analysis. 2021 [2] N. Kochdumper. Extensions of polynomial zonotopes and their application to verification of cyber-physical systems. 2021.

quadratic_map(Q::Vector{<:AbstractMatrix}, S1::SimpleSparsePolynomialZonotope,
              S2::SimpleSparsePolynomialZonotope)

Return the quadratic map of two simple sparse polynomial zonotopes. The quadratic map is the set

\[ \{x \mid xᵢ = s₁ᵀQᵢs₂, s₁ ∈ S₁, s₂ ∈ S₂, Qᵢ ∈ Q\}.\]

Input

• Q – vector of square matrices
• S1 – simple sparse polynomial zonotope
• S2 – simple sparse polynomial zonotope

Output

The quadratic map of the given simple sparse polynomial zonotopes represented as a simple sparse polynomial zonotope.

Algorithm

This method implements Proposition 3.1.30 in [1].

[1] N. Kochdumper. Extensions of polynomial zonotopes and their application to verification of cyber-physical systems. 2021.

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::SimpleSparsePolynomialZonotope,
                  P2::SimpleSparsePolynomialZonotope)

Algorithm

This method implements Proposition 3.1.22 in [1].

[1] Kochdumper, Niklas. Extensions of polynomial zonotopes and their application to verification of cyber-physical systems. PhD diss., Technische Universität München, 2022.

convex_hull(X::LazySet, Y::LazySet; [algorithm]=nothing,
            [backend]=nothing, [solver]=nothing)

Compute the convex hull of two polytopic sets.

Input

• X – polytopic set
• Y – polytopic set
• algorithm – (optional, default: nothing) the convex-hull algorithm
• backend – (optional, default: nothing) backend for polyhedral computations (used for higher-dimensional sets)
• solver – (optional, default: nothing) the linear-programming solver used in the backend

Output

If the sets are empty, the result is an EmptySet. If the convex hull consists of a single point, the result is a Singleton. If the input sets are one-dimensional, the result is an Interval. If the input sets are two-dimensional, the result is a VPolygon. Otherwise the result is a VPolytope.

Algorithm

We compute the vertices of both X and Y using vertices_list and then compute the convex hull of the union of those vertices.

Extended help

convex_hull(P1::SimpleSparsePolynomialZonotope,
            P2::SimpleSparsePolynomialZonotope)

Output

The tightest convex simple sparse polynomial zonotope containing P1 and P2.

linear_combination(X::LazySet, Y::LazySet)

Compute the linear combination of two sets.

Input

• X – set
• Y – set

Output

A set representing the linear combination of X and Y.

Notes

The linear combination of two sets $X$ and $Y$ is defined as

\[ \left\{\frac{1}{2}(1+λ)x + \frac{1}{2}(1-λ)y \mid x ∈ X, y ∈ Y, λ ∈ [-1, 1]\right\}.\]

If $X$ and $Y$ are convex, their linear combination is identical with the convex hull of their union $X ∪ Y$.

Extended help

linear_combination(P1::SimpleSparsePolynomialZonotope,
                   P2::SimpleSparsePolynomialZonotope)

Notes

This method implements the algorithm described in Proposition 3.1.25 of [1].

[1] N. Kochdumper. Extensions of polynomial zonotopes and their application to verification of cyber-physical systems. 2021.