research-article

Path-Complete Graphs and Common Lyapunov Functions

Authors:

Nikolaos Athanasopoulos,

Raphaël M. Jungers,

Matthew PhilippeAuthors Info & Claims

HSCC '17: Proceedings of the 20th International Conference on Hybrid Systems: Computation and Control

Pages 81 - 90

https://doi.org/10.1145/3049797.3049817

Published: 13 April 2017 Publication History

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.

References

[1]

Amir Ali Ahmadi, Raphaël M Jungers, Pablo A Parrilo, and Mardavij Roozbehani. Joint spectral radius and path-complete graph lyapunov functions. SIAM Journal on Control and Optimization, 52(1):687--717, 2014.

[2]

Nikolaos Athanasopoulos and Mircea Lazar. Alternative stability conditions for switched discrete time linear systems. In IFAC World Congress, pages 6007--6012, 2014.

[3]

Pierre-Alexandre Bliman and Giancarlo Ferrari-Trecate. Stability analysis of discrete-time switched systems through lyapunov functions with nonminimal state. In Proceedings of IFAC Conference on the Analysis and Design of Hybrid Systems, pages 325--330, 2003.

[4]

Vincent D Blondel and John N Tsitsiklis. The boundedness of all products of a pair of matrices is undecidable. Systems & Control Letters, 41(2):135--140, 2000.

[5]

Michael S Branicky. Multiple lyapunov functions and other analysis tools for switched and hybrid systems. IEEE Transactions on Automatic Control, 43(4):475--482, 1998.

[6]

Christos G Cassandras and Stephane Lafortune. Introduction to discrete event systems. Springer Science & Business Media, 2009.

Digital Library

[7]

Jamal Daafouz, Pierre Riedinger, and Claude Iung. Stability analysis and control synthesis for switched systems: a switched lyapunov function approach. IEEE Transactions on Automatic Control, 47(11):1883--1887, 2002.

[8]

Ray Essick, Ji-Woong Lee, and Geir E Dullerud. Control of linear switched systems with receding horizon modal information. IEEE Transactions on Automatic Control, 59(9):2340--2352, 2014.

[9]

Rafal Goebel, Tingshu Hu, and Andrew R Teel. Dual matrix inequalities in stability and performance analysis of linear differential/difference inclusions. In Current trends in nonlinear systems and control, pages 103--122. Springer, 2006.

[10]

Mikael Johansson, Anders Rantzer, et al. Computation of piecewise quadratic lyapunov functions for hybrid systems. IEEE transactions on automatic control, 43(4):555--559, 1998.

[11]

Raphaël Jungers. The joint spectral radius. Lecture Notes in Control and Information Sciences, 385, 2009.

[12]

Raphael M Jungers, Amirali Ahmadi, Pablo Parrilo, and Mardavij Roozbehani. A characterization of lyapunov inequalities for stability of switched systems. arXiv preprint arXiv:1608.08311, 2016.

[13]

Raphael M Jungers, WPMH Heemels, and Atreyee Kundu. Observability and controllability analysis of linear systems subject to data losses. arXiv preprint arXiv:1609.05840, 2016.

[14]

Victor Kozyakin. The Berger--Wang formula for the markovian joint spectral radius. Linear Algebra and its Applications, 448:315--328, 2014.

[15]

Ji-Woong Lee and Geir E Dullerud. Uniform stabilization of discrete-time switched and markovian jump linear systems. Automatica, 42(2), 205--218, 2006.

Digital Library

[16]

Daniel Liberzon and Stephen A Morse. Basic problems in stability and design of switched systems. IEEE Control Systems Magazine, 19(5):59--70, 1999.

[17]

Hai Lin and Panos J Antsaklis. Stability and stabilizability of switched linear systems: a survey of recent results. IEEE Transactions on Automatic control, 54(2):308--322, 2009.

[18]

Pablo A Parrilo and Ali Jadbabaie. Approximation of the joint spectral radius using sum of squares. Linear Algebra and its Applications, 428(10):2385--2402, 2008.

[19]

Matthew Philippe, Ray Essick, Geir Dullerud, and Raphaël M Jungers. Stability of discrete-time switching systems with constrained switching sequences. Automatica, 72:242--250, 2016.

Digital Library

[20]

Robert Shorten, Fabian Wirth, Oliver Mason, Kai Wulff, and Christopher King. Stability criteria for switched and hybrid systems. SIAM review, 49(4):545--592, 2007.

Digital Library

Cited By

Anand MJungers RZamani MAllgöwer F(2024)Path-Complete Barrier Functions for Safety of Switched Linear Systems2024 IEEE 63rd Conference on Decision and Control (CDC)10.1109/CDC56724.2024.10886799(7423-7428)Online publication date: 16-Dec-2024
https://doi.org/10.1109/CDC56724.2024.10886799
Movahedi HZemouche ARajamani R(2021)Magnetic position estimation using optimal sensor placement and nonlinear observer for smart actuatorsControl Engineering Practice10.1016/j.conengprac.2021.104817112(104817)Online publication date: Jul-2021
https://doi.org/10.1016/j.conengprac.2021.104817
Berger GJungers R(2021) p-dominant switched linear systemsAutomatica (Journal of IFAC)10.1016/j.automatica.2021.109801132:COnline publication date: 23-Aug-2021
https://dl.acm.org/doi/10.1016/j.automatica.2021.109801
Show More Cited By

Index Terms

Path-Complete Graphs and Common Lyapunov Functions
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms

Recommendations

Robust H∞ control for discrete-time fuzzy systems via basis-dependent Lyapunov functions

This paper deals with the robust H"~ control problem for a class of discrete-time fuzzy systems with uncertainty. The uncertainty is assumed to be of structured linear fractional form. By using basis-dependent Lyapunov function, an H"~ control design ...
Robust H∞ control for discrete-time fuzzy systems via basis-dependent Lyapunov functions

This paper deals with the robust H_∞ control problem for a class of discrete-time fuzzy systems with uncertainty. The uncertainty is assumed to be of structured linear fractional form. By using basis-dependent Lyapunov function, an H_∞ control design ...
Lyapunov-Based Stability and Construction of Lyapunov Functions for Boolean Networks

This paper investigates the Lyapunov-based stability analysis and the construction of Lyapunov functions for Boolean networks (BNs) and establishes a new framework of Lyapunov theory for BNs via the semitensor product of matrices. First, we study how to ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

HSCC '17: Proceedings of the 20th International Conference on Hybrid Systems: Computation and Control

April 2017

288 pages

ISBN:9781450345903

DOI:10.1145/3049797

Program Chairs:
Goran Frehse
University Grenoble Alpes
,
Sayan Mitra
University of Illinois at Urbana Champaign

Copyright © 2017 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGBED: ACM Special Interest Group on Embedded Systems

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 April 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

HSCC '17

Sponsor:

SIGBED

HSCC '17: 20th International Conference on Hybrid Systems: Computation and Control

April 18 - 20, 2017

Pennsylvania, Pittsburgh, USA

Acceptance Rates

HSCC '17 Paper Acceptance Rate 29 of 76 submissions, 38%;

Overall Acceptance Rate 153 of 373 submissions, 41%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
228
Total Downloads

Downloads (Last 12 months)14
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Anand MJungers RZamani MAllgöwer F(2024)Path-Complete Barrier Functions for Safety of Switched Linear Systems2024 IEEE 63rd Conference on Decision and Control (CDC)10.1109/CDC56724.2024.10886799(7423-7428)Online publication date: 16-Dec-2024
https://doi.org/10.1109/CDC56724.2024.10886799
Movahedi HZemouche ARajamani R(2021)Magnetic position estimation using optimal sensor placement and nonlinear observer for smart actuatorsControl Engineering Practice10.1016/j.conengprac.2021.104817112(104817)Online publication date: Jul-2021
https://doi.org/10.1016/j.conengprac.2021.104817
Berger GJungers R(2021) p-dominant switched linear systemsAutomatica (Journal of IFAC)10.1016/j.automatica.2021.109801132:COnline publication date: 23-Aug-2021
https://dl.acm.org/doi/10.1016/j.automatica.2021.109801
Berger GJungers R(2019)A Converse Lyapunov Theorem for p-dominant Switched Linear Systems2019 18th European Control Conference (ECC)10.23919/ECC.2019.8795923(1263-1268)Online publication date: Jun-2019
https://doi.org/10.23919/ECC.2019.8795923
Philippe MJungers ROzay NPrabhakar P(2019)A complete characterization of the ordering of path-complete methodsProceedings of the 22nd ACM International Conference on Hybrid Systems: Computation and Control10.1145/3302504.3311803(138-146)Online publication date: 16-Apr-2019
https://dl.acm.org/doi/10.1145/3302504.3311803
Philippe MAthanasopoulos NAngeli DJungers R(2019)On Path-Complete Lyapunov Functions: Geometry and ComparisonIEEE Transactions on Automatic Control10.1109/TAC.2018.286338064:5(1947-1957)Online publication date: May-2019
https://doi.org/10.1109/TAC.2018.2863380
Jin YSong YYang THou WSchuller M(2019)Exponential Stabilizability Analysis for Constrained Switched System2019 IEEE 8th Data Driven Control and Learning Systems Conference (DDCLS)10.1109/DDCLS.2019.8908856(934-938)Online publication date: May-2019
https://doi.org/10.1109/DDCLS.2019.8908856
Deng MSong YJin YLiu Y(2019)Recent Advance on the Stability of Switched Systems based on Formal Methods2019 Chinese Automation Congress (CAC)10.1109/CAC48633.2019.8996607(3561-3566)Online publication date: Nov-2019
https://doi.org/10.1109/CAC48633.2019.8996607
Della Rossa MTanwani AZaccarian L(2018)Max-Min Lyapunov Functions for Switching Differential Inclusions2018 IEEE Conference on Decision and Control (CDC)10.1109/CDC.2018.8619690(5664-5669)Online publication date: Dec-2018
https://doi.org/10.1109/CDC.2018.8619690

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten