Extended formulations for control languages defined by finite-state automata

Abstract Many discrete optimal control problems feature combinatorial constraints on the possible switching patterns, a common example being minimum dwell-time constraints. After discretizing to a finite time grid, it is sometimes possible to give a description of the convex hull of feasible (finite-dimensional) binary controls via flow-based extended formulations. For example, this is the case if the feasible set can be characterized via finite-state automata. In this work, we aim to transfer such descriptions to function space, by determining extended formulations for the closed convex hull of feasible control functions. In order to formally characterize the class of constraints our result applies to, we introduce finite-state control automata, a generalization of finite-state automata to infinite-dimensional input data. Roughly speaking, finite-state control automata describe feasible sets of controls that are combinations of predefined input patterns and constant parts in a way that can be described using finitely many states. Starting from a given automaton, our construction can serve as a recipe for obtaining tight formulations in function space as well as for any discretization. Moreover, we contribute two pumping lemmas, thus providing tools for proving non-representability under this new automaton model.