Constrained polynomial zonotopes

Niklas Kochdumper, Matthias Althoff

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

Abstract

We introduce constrained polynomial zonotopes, a novel non-convex set representation that is closed under linear map, Minkowski sum, Cartesian product, convex hull, intersection, union, and quadratic as well as higher-order maps. We show that the computational complexity of the above-mentioned set operations for constrained polynomial zonotopes is at most polynomial in the representation size. The fact that constrained polynomial zonotopes are generalizations of zonotopes, polytopes, polynomial zonotopes, Taylor models, and ellipsoids further substantiates the relevance of this new set representation. In addition, the conversion from other set representations to constrained polynomial zonotopes is at most polynomial with respect to the dimension, and we present efficient methods for representation size reduction and for enclosing constrained polynomial zonotopes by simpler set representations.

Original languageEnglish
Pages (from-to)279-316
Number of pages38
JournalActa Informatica
Volume60
Issue number3
DOIs
StatePublished - Sep 2023

Fingerprint

Dive into the research topics of 'Constrained polynomial zonotopes'. Together they form a unique fingerprint.

Cite this