On complexity of Lyapunov functions for switched linear systems

Amir Ali Ahmadi, Raphaël M. Jungers

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations


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. Several constructive and non-constructive arguments are presented which connect our problem to known (and rather classical) results in the literature regarding the finiteness conjecture, undecidability, and non-algebraicity of the joint spectral radius. In particular, we show that existence of a sum of squares Lyapunov function implies the finiteness property of the optimal product.

Original languageEnglish (US)
Title of host publication19th IFAC World Congress IFAC 2014, Proceedings
EditorsEdward Boje, Xiaohua Xia
PublisherIFAC Secretariat
Number of pages6
ISBN (Electronic)9783902823625
StatePublished - 2014
Externally publishedYes
Event19th IFAC World Congress on International Federation of Automatic Control, IFAC 2014 - Cape Town, South Africa
Duration: Aug 24 2014Aug 29 2014

Publication series

NameIFAC Proceedings Volumes (IFAC-PapersOnline)
ISSN (Print)1474-6670


Other19th IFAC World Congress on International Federation of Automatic Control, IFAC 2014
Country/TerritorySouth Africa
CityCape Town

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering


  • Convex optimization for Lyapunov analysis
  • Linear difference inclusions
  • Stability of switched systems
  • The finiteness conjecture of the joint spectral radius


Dive into the research topics of 'On complexity of Lyapunov functions for switched linear systems'. Together they form a unique fingerprint.

Cite this