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

7 Scopus citations

Abstract

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
Pages5992-5997
Number of pages6
ISBN (Electronic)9783902823625
DOIs
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)
Volume19
ISSN (Print)1474-6670

Other

Other19th IFAC World Congress on International Federation of Automatic Control, IFAC 2014
Country/TerritorySouth Africa
CityCape Town
Period8/24/148/29/14

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering

Keywords

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

Fingerprint

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

Cite this