### Abstract

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 language | English |
---|---|

Title of host publication | Proceedings of the 20th International Conference on Hybrid Systems: Computation and Control. |

Publisher | Association for Computing Machinery (ACM) |

Pages | 81-90 |

Number of pages | 10 |

ISBN (Print) | 978-1-4503-4590-3 |

DOIs | |

Publication status | Published - 01 May 2017 |

Event | 20th International Conference on Hybrid Systems: Computation and Control - Pittsburgh, United States Duration: 18 Apr 2017 → … |

### Conference

Conference | 20th International Conference on Hybrid Systems: Computation and Control |
---|---|

Abbreviated title | HSCC |

Country | United States |

City | Pittsburgh |

Period | 18/04/2017 → … |

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

## Cite this

Angeli, D., Athanasopoulos, N., Jungers, R. M., & Philippe, M. (2017). Path-Complete Graphs and Common Lyapunov Functions. In

*Proceedings of the 20th International Conference on Hybrid Systems: Computation and Control.*(pp. 81-90). Association for Computing Machinery (ACM). https://doi.org/10.1145/3049797.3049817