Lower bounds on complexity of Lyapunov functions for switched linear systems

DOI10.1016/J.NAHS.2016.01.003MaRDI QIDQ286067zbMATH OpenOpenAlexFDO

Authors Amir Ali Ahmadi, Raphaël M. Jungers

Publication date 19 May 2016

Published in Nonlinear Analysis. Hybrid Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1504.03761

zbMATH Keywords

convex optimization for Lyapunov analysislinear difference inclusionsstability of switched systemsthe finiteness conjecture of the joint spectral radius

Mathematics Subject Classification ID

Applications of mathematical programming (90C90) Lyapunov and storage functions (93D30)

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 $leqd$, or (ii) a polytopic Lyapunov function with $leqd$ facets, or (iii) a piecewise quadratic Lyapunov function with $leqd$ 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 an extremal piecewise algebraic Lyapunov function implies the finiteness property of the optimal product, generalizing a result of Lagarias and Wang. As a corollary, we prove that the finiteness property holds for sets of matrices with an extremal Lyapunov function belonging to some of the most popular function classes in controls.

Recommendations

• On universal classes of Lyapunov functions for linear switched systems
• Common Polynomial Lyapunov Functions for Linear Switched Systems
• Stabilizability of switched linear systems does not imply the existence of convex Lyapunov functions
• On common linear/quadratic Lyapunov functions for switched linear systems
• Switching and Learning in Feedback Systems

Cites work

• scientific article; zbMATH DE number 3155071 (Why is no real title available?)
• scientific article; zbMATH DE number 1490041 (Why is no real title available?)
• scientific article; zbMATH DE number 3068536 (Why is no real title available?)
• A new decision method for elementary algebra
• Algebraic unsolvability of problem of absolute stability of desynchronized systems
• An Elementary Counterexample to the Finiteness Conjecture
• An explicit counterexample to the Lagarias-Wang finiteness conjecture
• Analysis of the joint spectral radius via Lyapunov functions on path-complete graphs
• Approximation of the joint spectral radius using sum of squares
• Asymptotic height optimization for topical IFS, Tetris heaps, and the finiteness conjecture
• Common Polynomial Lyapunov Functions for Linear Switched Systems
• Conjugate Convex Lyapunov Functions for Dual Linear Differential Inclusions
• Dynamical systems which undergo switching
• Efficient algorithms for deciding the type of growth of products of integer matrices
• Graph diameter, eigenvalues, and minimum-time consensus
• Joint spectral radius and path-complete graph Lyapunov functions
• Lower bounds on complexity of Lyapunov functions for switched linear systems
• Lyapunov function construction by linear programming
• Non-weighted quasi-time-dependent \(H_\infty\) filtering for switched linear systems with persistent dwell-time
• On absolute stability analysis by polyhedral Lyapunov functions
• On common quadratic Lyapunov functions for stable discrete-time LTI systems
• On the Nonexistence of Quadratic Lyapunov Functions for Consensus Algorithms
• On the finiteness property for rational matrices
• Persistent Dwell-Time Switched Nonlinear Systems: Variation Paradigm and Gauge Design
• Quantifier elimination and cylindrical algebraic decomposition. Proceedings of a symposium, Linz, Austria, October 6--8, 1993
• Semidefinite Optimization and Convex Algebraic Geometry
• Set-theoretic methods in control
• Simultaneous Contractibility
• Simultaneous stabilizability of three linear systems is rationally undecidable
• Stability Criteria for Switched and Hybrid Systems
• Stability of discrete linear inclusion
• Switching in systems and control
• The boundedness of all products of a pair of matrices is undecidable
• The finiteness conjecture for the generalized spectral radius of a set of matrices
• Undecidable problems for probabilistic automata of fixed dimension

Cited in

(9)

• Comprehensive Lyapunov functions for linear switching systems
• Polytope Lyapunov functions for stable and for stabilizable LSS
• Lower bounds on complexity of Lyapunov functions for switched linear systems
• Robust \(H_\infty\) finite-time control for discrete-time polytopic uncertain switched linear systems
• Polynomial norms
• Counterexample-guided computation of polyhedral Lyapunov functions for piecewise linear systems
• On universal classes of Lyapunov functions for linear switched systems
• Robust stability of polytopic time-inhomogeneous Markov jump linear systems
• On random walks and switched random walks on homogeneous spaces

Describes a project that uses

Uses Software

• SeDuMi
• JSR

This page was built for publication: Lower bounds on complexity of Lyapunov functions for switched linear systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q286067)