Lower bounds on complexity of Lyapunov functions for switched linear systems

摘要

We show that for any positive integer d, there are families of switched linear systems in fixed dimension and defined by two matrices only - that are stable under arbitrary switching but do not admit (i) a polynomial Lyapunov function of degree <= d, or (ii) a polytopic Lyapunov function with <= d facets, or (iii) a piecewise quadratic Lyapunov function with <= d pieces. This implies that there cannot be an upper bound on the size of the linear and semidefinite programs that search for such stability certificates.