Norm Overapproximation

overapproximate_norm(Z::AbstractZonotope, [p]::Real=1)

Compute an upper bound on the $p$-norm of a zonotopic set.

Input

• Z – Zonotopic set
• p – (optional, default: 1) norm

Output

An upper bound on $\max_{x ∈ Z} ‖x‖_p$.

Notes

The norm of a set is the norm of the enclosing ball (of the given $p$-norm) of minimal volume that is centered in the origin.

overapproximate_norm(MZ::MatrixZonotope, [p]::Real=Inf)

Compute an upper bound on the $p$-norm of a matrix zonotope.

Input

• MZ – Matrix zonotope
• p – (optional, default: Inf) norm

Output

An upper bound on $\sup_{A ∈ \mathcal{A} } ‖A‖_p$.

overapproximate_norm(MZP::MatrixZonotopeProduct, [p]::Real=Inf)

Compute an upper bound on the $p$-norm of a product of matrix zonotopes.

Input

• MZP – Matrix zonotope product
• p – (optional, default: Inf) norm

Output

An upper bound on $\sup_{M ∈ \mathcal{A*B*…} } \|M\|_p$.

_overapproximate_l1_norm(Z::AbstractZonotope{N}) where {N}

Compute an upper bound on the 1-norm of a zonotopic set.

Notes

The problem $\max_{z ∈ Z} ‖z‖_1$ is NP-hard in general.

Algorithm

This method computes a convex relaxation by combining the MILP formulation described in Jordan and Dimakis [JD21], Theorem 5 with the convex-hull construction in the supplement section §C.3. We replace each coordinate's absolute value

\[|z_i|\quad z_i ∈ [ℓ_i, u_i]\]

by its convex-hull secant upper envelope: the line through the two points $((ℓ_i,|ℓ_i|)$ and $((u_i,|u_i|)$. This yields a linear-programming relaxation of complexity (O(p·n)), where p is the number of generators and n the ambient dimension.