SOS-Convex Lyapunov Functions and Stability of Difference Inclusions

We introduce the concept of sos-convex Lyapunov functions for stability analysis of both linear and nonlinear difference inclusions (also known as discrete-time switched systems). These are polynomial Lyapunov functions that have an algebraic certificate of convexity and that can be efficiently found via semidefinite programming. We prove that sos-convex Lyapunov functions are universal (i.e., necessary … Read more

Lower Bounds on Complexity of Lyapunov Functions for Switched Linear Systems

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 $\leq d$, or (ii) a polytopic Lyapunov function with $\leq d$ facets, or (iii) a piecewise … Read more

Joint Spectral Radius and Path-Complete Graph Lyapunov Functions

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 … Read more