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 d, or (ii) a polytopic Lyapunov function with
d facets, or (iii) a piecewise quadratic Lyapunov function with
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 a sum of squares Lyapunov function implies the finiteness property of the optimal product.
By: Amir Ali Ahmadi, Raphaël M. Jungers
Published in: RC25430 in 2013
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .