Approximation of the joint spectral radius using sum of squares

Abstract

We provide an asymptotically tight, computationally efficient approximation of the joint spectral radius of a set of matrices using sum of squares (SOS) programming. The approach is based on a search for an SOS polynomial that proves simultaneous contractibility of a finite set of matrices. We provide a bound on the quality of the approximation that unifies several earlier results and is independent of the number of matrices. Additionally, we present a comparison between our approximation scheme and earlier techniques, including the use of common quadratic Lyapunov functions and a method based on matrix liftings. Theoretical results and numerical investigations show that our approach yields tighter approximations.

18 pages, 1 figure

Cited by in corpus (34)

• Joint Spectral Radius and Path-Complete Graph Lyapunov Functions
• A Characterization of Lyapunov Inequalities for Stability of Switched Systems
• On accuracy of approximation of the spectral radius by the Gelfand formula
• Iterative building of Barabanov norms and computation of the joint spectral radius for matrix sets
• Algebraic Relaxations and Hardness Results in Polynomial Optimization and Lyapunov Analysis
• Semi-definite programming and quantum information
• Optimization over Nonnegative and Convex Polynomials With and Without Semidefinite Programming
• An explicit Lipschitz constant for the joint spectral radius
• Stability of Markov regenerative switched linear systems
• Rank-one Characterization of Joint Spectral Radius of Finite Matrix Family
• Asymptotic stability of stochastic LTV systems with applications to distributed dynamic fusion
• Stability analysis of linear systems subject to regenerative switchings
• Improved invariant polytope algorithm and applications
• A relaxation scheme for computation of the joint spectral radius of matrix sets
• The Local to Unity Dynamic Tobit Model
• A limit formula for joint spectral radius with $p$-radius of probability distributions
• SOS-Convex Lyapunov Functions and Stability of Difference Inclusions
• An entropy-based bound for the computational complexity of a switched system
• Engineering and Business Applications of Sum of Squares Polynomials
• Lyapunov Exponent of Rank One Matrices: Ergodic Formula and Inapproximability of the Optimal Distribution
• Chance-constrained quasi-convex optimization with application to data-driven switched systems control
• On explicit a priori estimates of the joint spectral radius by the generalized Gelfand formula
• Computation of invariant sets via immersion for discrete-time nonlinear systems
• SparseJSR: A Fast Algorithm to Compute Joint Spectral Radius via Sparse SOS Decompositions
• Max-relaxation iteration procedure for building of Barabanov norms: convergence and examples
• Optimal switching sequence for switched linear systems
• Approximation of The Constrained Joint Spectral Radius via Algebraic Lifting
• Lifted polytope methods for stability analysis of switching systems
• Computing the domain of attraction of switching systems subject to non-convex constraints
• Stability of discrete-time switching systems with constrained switching sequences
• An Application of Joint Spectral Radius in Power Control Problem for Wireless Communications
• Finding Matrix Sequences with a High Asymptotic Growth Rate for Linear Constrained Switching Systems
• Matrix compression along isogenic blocks
• Mode Reduction for Markov Jump Systems