TY - JOUR
T1 - Constrained polynomial zonotopes
AU - Kochdumper, Niklas
AU - Althoff, Matthias
N1 - Publisher Copyright:
© 2023, The Author(s).
PY - 2023/9
Y1 - 2023/9
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85158132122&partnerID=8YFLogxK
U2 - 10.1007/s00236-023-00437-5
DO - 10.1007/s00236-023-00437-5
M3 - Article
AN - SCOPUS:85158132122
SN - 0001-5903
VL - 60
SP - 279
EP - 316
JO - Acta Informatica
JF - Acta Informatica
IS - 3
ER -