Path-Complete Graphs and Common Lyapunov Functions

David Angeli, Nikolaos Athanasopoulos, Raphael M. Jungers, Matthew Philippe

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

11 Citations (Scopus)
389 Downloads (Pure)


A Path-Complete Lyapunov Function is an algebraic criterion composed of a finite number of functions, called pieces, and a directed, labeled graph defining Lyapunov inequalities between these pieces. It provides a stability certificate for discrete-time arbitrary switching systems. In this paper, we prove that the satisfiability of such a criterion implies the existence of a Common Lyapunov Function, expressed as the composition of minima and maxima of the pieces of the Path-Complete Lyapunov function. the converse however is not true even for discrete-time linear systems: we present such a system where a max-of-2 quadratics Lyapunov function exists while no corresponding Path-Complete Lyapunov function with 2 quadratic pieces exists. In light of this, we investigate when it is possible to decide if a Path- Complete Lyapunov function is less conservative than another. By analyzing the combinatorial and algebraic structure of the graph and the pieces respectively, we provide simple tools to decide when the existence of such a Lyapunov function implies that of another.

Original languageEnglish
Title of host publicationProceedings of the 20th International Conference on Hybrid Systems: Computation and Control.
PublisherAssociation for Computing Machinery
Number of pages10
ISBN (Print)978-1-4503-4590-3
Publication statusPublished - 01 May 2017
Event20th International Conference on Hybrid Systems: Computation and Control - Pittsburgh, United States
Duration: 18 Apr 2017 → …


Conference20th International Conference on Hybrid Systems: Computation and Control
Abbreviated titleHSCC
Country/TerritoryUnited States
Period18/04/2017 → …


Dive into the research topics of 'Path-Complete Graphs and Common Lyapunov Functions'. Together they form a unique fingerprint.

Cite this