Joint spectral radius and path-complete graph Lyapunov functions
From MaRDI portal
(Redirected from Publication:5494892)
finite automatajoint spectral radiuslinear difference inclusionsLyapunov methodssemidefinite programmingstability of switched systems
Applications of graph theory (05C90) Stability theory for smooth dynamical systems (37C75) Numerical methods for difference equations (65Q10) Formal languages and automata (68Q45) Semidefinite programming (90C22) Eigenvalue problems (93B60) Control/observation systems governed by functional relations other than differential equations (such as hybrid and switching systems) (93C30) Lyapunov and other classical stabilities (Lagrange, Poisson, (L^p, l^p), etc.) in control theory (93D05) Lyapunov and storage functions (93D30)
Abstract: We introduce the framework of path-complete graph Lyapunov functions for approximation of the joint spectral radius. The approach is based on the analysis of the underlying switched system via inequalities imposed among multiple Lyapunov functions associated to a labeled directed graph. Inspired by concepts in automata theory and symbolic dynamics, we define a class of graphs called path-complete graphs, and show that any such graph gives rise to a method for proving stability of the switched system. This enables us to derive several asymptotically tight hierarchies of semidefinite programming relaxations that unify and generalize many existing techniques such as common quadratic, common sum of squares, and maximum/minimum-of-quadratics Lyapunov functions. We compare the quality of approximation obtained by certain classes of path-complete graphs including a family of dual graphs and all path-complete graphs with two nodes on an alphabet of two matrices. We provide approximation guarantees for several families of path-complete graphs, such as the De Bruijn graphs, establishing as a byproduct a constructive converse Lyapunov theorem for maximum/minimum-of-quadratics Lyapunov functions.
Recommendations
- Analysis of the joint spectral radius via Lyapunov functions on path-complete graphs
- Path-complete graphs and common Lyapunov functions
- Hybrid Systems: Computation and Control
- Certifying unstability of switched systems using sum of squares programming
- Computationally Efficient Approximations of the Joint Spectral Radius
Cited in
(45)- Linear switched dynamical systems on graphs
- Stability analysis of discrete-time switched systems via multi-step multiple Lyapunov-like functions
- A stability criterion for switching Lur'e systems with switching-path restrictions
- Stability and stabilizability of discrete-time dual switching systems with application to sampled-data systems
- Stabilization and control Lyapunov functions for language constrained discrete-time switched linear systems
- Graph Lyapunov function for switching stabilization and distributed computation
- The outer spectral radius and dynamics of completely positive maps
- Continuous-time switched systems with switching frequency constraints: path-complete stability criteria
- Comparison of path-complete Lyapunov functions via template-dependent lifts
- Stability of shuffled switched linear systems: A joint spectral radius approach
- Sum-of-squares methods for controlled invariant sets with applications to model-predictive control
- Distance geometry and data science
- Max-min Lyapunov functions for switched systems and related differential inclusions
- Deciding the boundedness and dead-beat stability of constrained switching systems
- Output feedback stabilization of switching discrete-time linear systems with parameter uncertainties
- Finite-time stability for switched linear systems by Jordan decomposition
- \(p\)-dominant switched linear systems
- Marginally unstable discrete-time linear switched systems with highly irregular trajectory growth
- Stability analysis of time-varying switched systems via indefinite difference Lyapunov functions
- Lower bounds on complexity of Lyapunov functions for switched linear systems
- Graph-based dwell time computation methods for discrete-time switched linear systems
- Analysis of the joint spectral radius via Lyapunov functions on path-complete graphs
- Stability of discrete-time switching systems with constrained switching sequences
- Recent developments on the stability of systems with aperiodic sampling: an overview
- Optimal Switching Sequence for Switched Linear Systems
- Certifying unstability of switched systems using sum of squares programming
- Lyapunov Exponent of Rank-One Matrices: Ergodic Formula and Inapproximability of the Optimal Distribution
- A complete characterization of the ordering of path-complete methods
- Path-complete graphs and common Lyapunov functions
- Linear programming based lower bounds on average dwell-time via multiple Lyapunov functions
- Latency vs precision: stability preserving perception scheduling
- Necessary and Sufficient Conditions for Template-Dependent Ordering of Path-Complete Lyapunov Methods
- Learning stability guarantees for constrained switching linear systems from noisy observations
- Graph-based conditions for feedback stabilization of switched and LPV systems
- Characterization of the ordering of path-complete stability certificates with addition-closed templates
- Converse Lyapunov results for switched systems with lower and upper bounds on switching intervals
- On global exponential stability of discrete-time switching systems with dwell-time ranges: novel induced LMIs for linear systems with delays
- Stability and stabilisability of switched discrete-time systems based on structured Lyapunov functions
- Multiple Lyapunov functions and memory: a symbolic dynamics approach to systems and control
- Computation of invariant sets for complex systems
- Necessary and sufficient conditions for stabilisability of discrete-time time-varying switched systems
- A hybrid approach to joint spectral radius computation
- Feedback stabilization of switched systems under arbitrary switching: a convex characterization
- Analysis and synthesis of switched optimization algorithms
- A convergent hierarchy of non-linear eigenproblems to compute the joint spectral radius of nonnegative matrices
This page was built for publication: Joint spectral radius and path-complete graph Lyapunov functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5494892)
