SimpleSparsePolynomialZonotope

LazySets.SimpleSparsePolynomialZonotopeType
SimpleSparsePolynomialZonotope{N, VN<:AbstractVector{N}, MN<:AbstractMatrix{N}, ME<:AbstractMatrix{<:Integer}} <: AbstractPolynomialZonotope{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} ⊂ \mathbb{R}^n$ is represented by the set

\[\mathcal{PZ} = \left\{x \in \mathbb{R}^n : x = c + \sum_{i=1}^h \left(\prod_{k=1}^p \alpha_k^{E_{k, i}} \right) g_i,~~ \alpha_k \in [-1, 1]~~ \forall i = 1,\ldots,p \right\},\]

where $c ∈ \mathbb{R}^n$ is the offset vector (or center), $G ∈ \mathbb{R}^{n \times 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 [KA21]. The simple variation was defined in [K22].

  • [KA21] N. Kochdumper and M. Althoff. Sparse Polynomial Zonotopes: A Novel Set Representation for Reachability Analysis. Transactions on Automatic Control, 2021.
  • [K21] N. Kochdumper. Challenge Problem 5: Polynomial Zonotopes in Julia. JuliaReach and JuliaIntervals Days 3, 2021.
source
Base.randMethod
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 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 – (optinal, 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 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.

source
LazySets.centerMethod
center(P::SimpleSparsePolynomialZonotope)

Return the center of P.

Input

  • P – simple sparse polynomial zonotope

Output

The center of P.

source
LazySets.genmatMethod
genmat(P::SimpleSparsePolynomialZonotope)

Return the matrix of generators of P.

Input

  • P – simple sparse polynomial zonotope

Output

The matrix of generators of P.

source
LazySets.expmatMethod
expmat(P::SimpleSparsePolynomialZonotope)

Return the matrix of exponents of the 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 definition) and each column 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
source
LazySets.dimMethod
dim(P::SimpleSparsePolynomialZonotope)

Return the dimension of P.

Input

  • P – simple sparse polynomial zonotope

Output

The ambient dimension of P.

source
LazySets.ngensMethod
ngens(P::SimpleSparsePolynomialZonotope)

Return the number of generators of P.

Input

  • P – simple sparse polynomial zonotope

Output

The number of generators of P.

Notes

This is equivalent to the number of monomials in the polynomial representation of P.

source
LazySets.nparamsMethod
nparams(P::SimpleSparsePolynomialZonotope)

Return the number of parameters in the polynomial representation of P.

Input

  • P – simple sparse polynomial zonotope

Output

The number of parameters in the polynomial representation of P.

Notes

This corresponds to the number rows in the exponent matrix $E$ (p in the set definition).

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> nparams(S)
2
source
LazySets.orderMethod
order(P::SimpleSparsePolynomialZonotope)

Return the order of P.

Input

  • P – simple sparse polynomial zonotope

Output

The order of P, defined as the quotient between the number of generators and the ambient dimension.

source
LazySets.linear_mapMethod
linear_map(M::Union{Real, AbstractMatrix, LinearAlgebra.UniformScaling}, P::SimpleSparsePolynomialZonotope)

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

Input

  • M – square matrix with size(M) == dim(P)
  • P – simple sparse polynomial zonotope

Output

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

source
LazySets.minkowski_sumMethod
minkowski_sum(P1::SimpleSparsePolynomialZonotope, P2::SimpleSparsePolynomialZonotope)

computes the Minkowski sum of the simple sparse polynomial zonotopes P1 and P2.

Input

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

Output

The Minkowski sum of P1 and P2

source
LazySets.cartesian_productMethod
cartesian_product(P1::SimpleSparsePolynomialZonotope, P2::SimpleSparsePolynomialZonotope)

computes the cartesian product of the simple sparse polynomial zonotopes P1 and P2.

Input

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

Output

The cartesian product of P1 and P2

source
LazySets.linear_combinationMethod
linear_combination(P1::SimpleSparsePolynomialZonotope, P2::SimpleSparsePolynomialZonotope)

Compute the linear combination of simple sparse polynomial zonotopes P1 and P2.

Input

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

Output

Linear combination of P1 and P2.

Notes

The linear combination of two sets $P₁$ and $P₂$ is defined as

\[\{1/2(1+λ)p₁ + 1/2(1-λ)p₂ | p₁ ∈ P₁, p₂ ∈ P₂, λ ∈ [-1, 1]\}.\]

source
LazySets.convex_hullMethod
convex_hull(P1::SimpleSparsePolynomialZonotope, P2::SimpleSparsePolynomialZonotope)

Computes the convex hull of the simple sparse polynomial zonotopes P1 and P2.

Input

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

Output

Tightest convex simple sparse polynomial zonotope containing P1 and P2.

source
LazySets.convex_hullMethod
convex_hull(P::SimpleSparsePolynomialZonotope)

Computes the convex hull of the simple sparse polynomial zonotope P.

Input

  • P – simple sparse polynomial zonotopes

Output

Tightest convex simple sparse polynomial zonotope containing P.

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

Return an overapproximation of the quadratic map of the given polynomial zonotope.

Input

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

Output

The quadratic map of the given zonotope represented as a 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.

source
LazySets.remove_redundant_generatorsMethod
remove_redundant_generators(S::SimpleSparsePolynomialZonotope)

Remove redundant generators from S.

Input

  • S – simple sparse polynomial zonotope

Output

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

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 eliminated.
  • 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.
source