Approximability of the Containment Problem for Zonotopes and Ellipsotopes

• 成果类型: Article
• 署名作者: Kulmburg, Adrian; Schafer, Lukas; Althoff, Matthias
• 署名单位: Technical University of Munich
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2025.3583624
• 发表日期: 2025
• 关键词: invariance; sets

摘要

The zonotope containment problem, i.e., whether one zonotope is contained in another, is a central problem in control theory. Applications include detecting faults and robustifying controllers by computing invariant sets, and obtaining fixed points in reachability analysis. Despite the inherent $\mathsf {co}\text{-}\mathsf {NP}$-hardness of this problem, an approximation algorithm developed by Sadraddini and Tedrake (2019) has gained widespread recognition for its swift execution and consistent reliability in practice. In our study, we substantiate the precision of the algorithm with a definitive proof, elucidating the empirical accuracy observed in practice. Our proof hinges on establishing a connection between the containment problem and the computation of matrix norms, thereby enabling the extension of the approximation algorithm to encompass ellipsotopes-a broader class of sets derived from zonotopes. We also explore the computational complexity of the ellipsotope containment problem with a focus on approximability. Finally, we present new methods to compute safe sets for linear dynamical systems, demonstrating the practical relevance of approximating the ellipsotope containment problem.