- Lower Bounds on Complexity of Lyapunov Functions for Switched Linear Systems Amir Ali Ahmadi(a_a_aprinceton.edu) Raphael Jungers(raphael.jungersuclouvain.be) 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 $\leq d$, or (ii) a polytopic Lyapunov function with $\leq d$ facets, or (iii) a piecewise quadratic Lyapunov function with $\leq d$ 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. Keywords: stability of switched systems, linear difference inclusions, the finiteness conjecture of the joint spectral radius, convex optimization for Lyapunov analysis Category 1: Convex and Nonsmooth Optimization (Convex Optimization ) Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming ) Category 3: Nonlinear Optimization (Systems governed by Differential Equations Optimization ) Citation: Download: [PDF]Entry Submitted: 04/14/2015Entry Accepted: 04/14/2015Entry Last Modified: 04/14/2015Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.