Polynomial zonotope (DensePolynomialZonotope)

DensePolynomialZonotope{N, VT, VMT, MT} <: AbstractPolynomialZonotope{N}

Type that represents a polynomial zonotope.

Fields

• c – starting point
• E – matrix of multi-indexed generators such that all indices have the same value
• F – matrix of multi-indexed generators such that not all indices have the same value
• G – matrix of single-indexed generators

Notes

Polynomial zonotopes were introduced in [1] and have been applied as non-convex set representation to the reachability problem of nonlinear ODEs.

Mathematically, a polynomial zonotope is defined as the tuple $(c, E, F, G)$, where:

• $c ∈ ℝ^n$ is the starting point (in some particular cases it corresponds to the center of a usual zonotope),

• $E = [E^{[1]} ⋯ E^{[η]}]$ is an $n × p × η$ matrix with column blocks

\[E^{[i]} = [f^{([i], 1, 1, …, 1)} ⋯ f^{([i], p, p, …, p)}], \qquad i = 1,…, η\]

called the matrix of multi-indexed generators with equal indices, where each $f^{([i], k_1, k_2, …, k_i)}$ is an $n$-vector,

• $F = [F^{[2]} ⋯ F^{[η]}]$ is a matrix with column-blocks

\[F^{[i]} = [f^{([i], 1, 1, …, 1, 2)} f^{([i], 1, 1, …, 1, 3)} ⋯ f^{([i], 1, 1, …, 1, p)} \\ f^{([i], 1, 1, …, 2, 2)} f^{([i], 1, 1, …, 2, 3)} ⋯ f^{([i], 1, 1, …, 2, p)} \\ f^{([i], 1, 1, …, 3, 3)} ⋯], \qquad i = 1,…, η\]

called the matrix of multi-indexed generators with unequal indices (or, more accurately, not-all-equal indices), where each $f^{([i], k_1, k_2, …, k_i)}$ is an $n$-vector,

• $G = [G^{[1]} ⋯ G^{[q]}]$ is an $n × q$ matrix with columns

\[G^{[i]} = g^{(i)}, \qquad i = 1,…, q\]

called the matrix of single-indexed generators, where each $g^{(i)}$ is an $n$-vector.

The polynomial zonotope $(c, E, F, G)$ defines the set:

\[\left\{ c + ∑_{j=1}^p β_j f^{([1], j)} + ∑_{j=1}^p ∑_{k=j}^p β_j β_k f^{([2], j, k)} + \\ + … + ∑_{j=1}^p ∑_{k=j}^p ⋯ ∑_{m=ℓ}^p β_j β_k ⋯ β_m f^{([η], j, k, …, m)} + \\ + ∑_{i=1}^q γ_i g^{(i)}, \qquad β_i, γ_i ∈ [-1, 1] \right\},\]

where the number of factors in the final product, $β_j β_k ⋯ β_m$, corresponds to the polynomial order $η$.

[1] M. Althoff in Reachability analysis of nonlinear systems using conservative polynomialization and non-convex sets, Hybrid Systems: Computation and Control, 2013, pp. 173-182.

center(P::DensePolynomialZonotope)

Return the center of a polynomial zonotope.

Input

• P – polynomial zonotope

Output

The center of P.

ngens_dep(P::DensePolynomialZonotope)

Return the number of dependent generators of a polynomial zonotope.

Input

• P – polynomial zonotope

Output

The number of dependent generators of P.

ngens_indep(P::DensePolynomialZonotope)

Return the number of independent generators of a polynomial zonotope.

Input

• P – polynomial zonotope

Output

The number of independent generators of P.

polynomial_order(P::DensePolynomialZonotope)

Polynomial order of a polynomial zonotope.

Input

• P – polynomial zonotope

Output

The polynomial order, defined as the maximal power of the scale factors $β_i$. It is usually denoted $η$.

order(P::DensePolynomialZonotope)

Order of a polynomial zonotope.

Input

• P – polynomial zonotope

Output

The order, a rational number defined as the total number of generators divided by the ambient dimension.

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

Return the linear map of a polynomial zonotope.

Input

• M – matrix
• P – polynomial zonotope

Output

A polynomial zonotope.

Algorithm

The result's starting point and generators are those of P multiplied by the matrix M.

scale!(α::Real, P::DensePolynomialZonotope)

Scale a polynomial zonotope modified by a scale factor in-place.

Input

• α – scaling factor
• P – polynomial zonotope

Output

The modified polynomial zonotope.

Algorithm

The center and generators are scaled by $α$.