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.

center(P::SimpleSparsePolynomialZonotope)

Return the center of a simple sparse polynomial zonotope.

Input

• P – simple sparse polynomial zonotope

Output

The center of P.

convex_hull(P::SimpleSparsePolynomialZonotope)

Compute the convex hull of a simple sparse polynomial zonotope.

Input

• P – simple sparse polynomial zonotope

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

genmat(P::SimpleSparsePolynomialZonotope)

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

Input

• P – simple sparse polynomial zonotope

Output

The matrix of generators of P.

ngens(P::SimpleSparsePolynomialZonotope)

Return the number of generators of a simple sparse polynomial zonotope.

Input

• P – simple sparse polynomial zonotope

Output

The number of generators of P.

Notes

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

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)

Create a random simple sparse polynomial zonotope.

Input

• Zonotope – 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
• 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 simple 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 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(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.

linear_map(M::AbstractMatrix, P::SimpleSparsePolynomialZonotope)

Apply the linear map M to a simple sparse polynomial zonotope.

Input

• M – matrix
• P – simple sparse polynomial zonotope

Output

The set resulting from applying the linear map M to P.

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

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{MT}, S1::SimpleSparsePolynomialZonotope,
              S2::SimpleSparsePolynomialZonotope)
    where {N, MT<:AbstractMatrix{N}}

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

Compute the Cartesian product of two simple sparse polynomial zonotopes.

Input

• P1 – simple sparse polynomial zonotope
• P2 – simple sparse polynomial zonotope

Output

The Cartesian product of P1 and P2.

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

Compute the convex hull of two simple sparse polynomial zonotopes.

Input

• P1 : simple sparse polynomial zonotopes
• P2 : simple sparse polynomial zonotopes

Output

Tightest convex simple sparse polynomial zonotope containing P1 and P2.

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

Compute the linear combination of two simple sparse polynomial zonotopes.

Input

• P1 – simple sparse polynomial zonotope
• P2 – simple sparse polynomial zonotope

Output

A SimpleSparsePolynomialZonotope representing the linear combination of P1 and P2.

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.

minkowski_sum(P1::SimpleSparsePolynomialZonotope,
              P2::SimpleSparsePolynomialZonotope)

Compute the Minkowski sum of two simple sparse polynomial zonotopes.

Input

• P1 – simple sparse polynomial zonotope
• P2 – simple sparse polynomial zonotope

Output

The Minkowski sum of P1 and P2.

PolynomialZonotope = SimpleSparsePolynomialZonotope

Alias for SimpleSparsePolynomialZonotope.