Lower bounds on complexity of Lyapunov functions for switched linear systems

DOI10.1016/J.NAHS.2016.01.003zbMATH Open1382.93028arXiv1504.03761OpenAlexW2964108557MaRDI QIDQ286067FDOQ286067

Authors: Amir Ali Ahmadi, Raphaël M. Jungers 

Publication date: 19 May 2016

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

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.

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

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

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)

Cites Work

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

Cited In (9)

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

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)