Underapproximative Methods for the Order Reduction of Zonotopes

Zonotopes are a widely used set representation in set-based computations due to their compact representation size and their closure under many relevant set operations. However, certain set operations, such as the Minkowski sum, increase the zonotope order, which in turn increases the computational cost of further computations. To address this issue, various order reduction techniques have been proposed, most of which focus on overapproximating the original zonotope. While overapproximations are crucial for safety verification, some applications – such as reachset-conformant identification and backward reachability analysis – require underapproximations (also referred to as inner-approximations). Besides providing a comprehensive survey of existing underapproximative order reduction methods, we propose four novel reduction methods in this paper. We analyze the computational cost of all methods and evaluate the tightness of the resulting underapproximations through numerical experiments on more than 2000 randomly generated zonotopes. The results demonstrate that our proposed methods achieve a favorable balance between computational efficiency and approximation accuracy, making them well-suited for applications in control, estimation, and system identification.