Convex computation of the maximum controlled invariant set for discrete-time polynomial control systems

We characterize the maximum controlled invariant (MCI) set for discrete-time systems as the solution of an infinite-dimensional linear programming problem. In the case of systems with polynomial dynamics and semialgebraic state and control constraints, we describe a hierarchy of finite-dimensional linear matrix inequality relaxations of this problem that provides outer approximations with guaranteed set-wise convergence to the MCI set. The approach is compact and readily applicable in the sense that the approximations are the outcome of a single semidefinite program with no additional input apart from the problem description.