Adrian Kulmburg

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 coNP-hardness of this problem, an approximation algorithm developed by S. Sadraddini and R. Tedrake 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.

We introduce new techniques to check whether a zonotope is contained in another zonotope. This fundamental problem in control theory has many applications, such as the verification of invariant sets, formal verification of controllers, and fault detection. Our first method uses a search-based vertex enumeration to quickly and efficiently check containment. We also propose two stochastic methods that are able to rapidly disprove or confirm containment with a certain probability. Furthermore, we generalize the first approach to the case where the circumbody is an ellipsotope and generalize the stochastic methods to the case where both the inbody and the circumbody are ellipsotopes. We conclude by comparing the efficiency of our algorithms to currently available ones.

We study the computability of the operator norm of a matrix with respect to norms induced by linear operators. Our findings reveal that this problem can be solved in polynomial time in certain situations, and we discuss how it can be approximated in other cases. Along the way, we investigate the concept of push-forward and pull-back of seminorms, which leads us to uncover novel duality principles that come into play when optimizing over the unit ball of norms.

We introduce a new type of norm for non-degenerate zonotopes to solve the point containment problem, i.e., whether a point lies in a zonotope. With this norm we prove the co-NP-completeness of the zonotope containment problem, i.e., whether a zonotope is contained within another one. We propose novel algorithms to solve the zonotope containment problem exactly in polynomial time when fixing the dimension or the number of generators of either of the two zonotopes. In addition, we propose an optimisation-based algorithm, that is particularly suitable for disproving containment for zonotopes.