TY - GEN
T1 - On complexity of Lyapunov functions for switched linear systems
AU - Ahmadi, Amir Ali
AU - Jungers, Raphaël M.
N1 - Publisher Copyright:
© IFAC.
PY - 2014
Y1 - 2014
N2 - 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.
AB - 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.
KW - Convex optimization for Lyapunov analysis
KW - Linear difference inclusions
KW - Stability of switched systems
KW - The finiteness conjecture of the joint spectral radius
UR - http://www.scopus.com/inward/record.url?scp=84929832414&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84929832414&partnerID=8YFLogxK
U2 - 10.3182/20140824-6-za-1003.02484
DO - 10.3182/20140824-6-za-1003.02484
M3 - Conference contribution
AN - SCOPUS:84929832414
T3 - IFAC Proceedings Volumes (IFAC-PapersOnline)
SP - 5992
EP - 5997
BT - 19th IFAC World Congress IFAC 2014, Proceedings
A2 - Boje, Edward
A2 - Xia, Xiaohua
PB - IFAC Secretariat
T2 - 19th IFAC World Congress on International Federation of Automatic Control, IFAC 2014
Y2 - 24 August 2014 through 29 August 2014
ER -