×

Lower bounds on complexity of Lyapunov functions for switched linear systems. (English) Zbl 1382.93028

Summary: 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 J. C. Lagarias and Y. Wang [Linear Algebra Appl. 214, 17–42 (1995; Zbl 0818.15007)]. 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.

MSC:

93D30 Lyapunov and storage functions
90C90 Applications of mathematical programming

Citations:

Zbl 0818.15007

Software:

SeDuMi; JSR
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[2] Han, T.; Ge, S.; Lee, T., Persistent dwell-time switched nonlinear systems: variation paradigm and gauge design, IEEE Trans. Automat. Control, 55, 2, 321-337 (2010) · Zbl 1368.93626
[3] Zhang, L.; Zhuang, S.; Shi, P., Non-weighted quasi-time-dependent filtering for switched linear systems with persistent dwell-time, Automatica, 54, 201-209 (2015) · Zbl 1318.93094
[4] Liberzon, D., Switching in Systems and Control (2003), Birkhäuser: Birkhäuser Boston, MA · Zbl 1036.93001
[5] Shorten, R.; Wirth, F.; Mason, O.; Wulff, K.; King, C., Stability criteria for switched and hybrid systems, SIAM Rev., 49, 4, 545-592 (2007) · Zbl 1127.93005
[6] Jungers, R. M., (The Joint Spectral Radius: Theory and Applications. The Joint Spectral Radius: Theory and Applications, Lecture Notes in Control and Information Sciences, vol. 385 (2009), Springer)
[7] Ando, T.; Shih, M.-H., Simultaneous contractibility, SIAM J. Matrix Anal. Appl., 19, 487-498 (1998) · Zbl 0912.15033
[8] Dayawansa, W. P.; Martin, C. F., A converse Lyapunov theorem for a class of dynamical systems which undergo switching, IEEE Trans. Automat. Control, 44, 4, 751-760 (1999) · Zbl 0960.93046
[9] Mason, O.; Shorten, R., On common quadratic Lyapunov functions for stable discrete time LTI systems, IMA J. Appl. Math, 59, 271-283 (2004) · Zbl 1067.93057
[10] Olshevsky, A.; Tsitsiklis, J. N., On the nonexistence of quadratic Lyapunov functions for consensus algorithms, IEEE Trans. Automat. Control, 53, 11, 2642-2645 (2008) · Zbl 1367.93611
[12] Parrilo, P. A.; Jadbabaie, A., Approximation of the joint spectral radius using sum of squares, Linear Algebra Appl., 428, 10, 2385-2402 (2008) · Zbl 1151.65032
[13] Polański, A., Lyapunov function construction by linear programming, IEEE Trans. Automat. Control, 42, 7, 1013-1016 (1997) · Zbl 0885.93050
[14] Blanchini, Franco; Miani, Stefano, Set-theoretic Methods in Control (2007), Springer · Zbl 1417.93008
[15] Polański, A., On absolute stability analysis by polyhedral Lyapunov functions, Automatica, 36, 4, 573-578 (2000) · Zbl 0980.93073
[17] Goebel, R.; Teel, A. R.; Hu, T.; Lin, Z., Conjugate convex Lyapunov functions for dual linear differential inclusions, IEEE Trans. Automat. Control, 51, 4, 661-666 (2006) · Zbl 1366.34030
[18] Ahmadi, A. A.; Jungers, R. M.; Parrilo, P. A.; Roozbehani, M., Joint spectral radius and path-complete graph Lyapunov functions, SIAM J. Control Optim., 52, 687-917 (2014) · Zbl 1292.93093
[19] Ahmadi, A. A.; Jungers, R. M.; Parrilo, P. A.; Roozbehani, M., Analysis of the joint spectral radius via Lyapunov functions on path-complete graphs, (Hybrid Systems: Computation and Control 2011. Hybrid Systems: Computation and Control 2011, Lecture Notes in Computer Science (2011), Springer) · Zbl 1364.93376
[21] Kozyakin, V. A., Algebraic unsolvability of problem of absolute stability of desynchronized systems, Autom. Remote Control, 51, 754-759 (1990) · Zbl 0737.93056
[22] Blondel, V. D.; Theys, J.; Vladimirov, A. A., An elementary counterexample to the finiteness conjecture, SIAM J. Matrix Anal. Appl., 24, 4, 963-970 (2003) · Zbl 1043.15007
[23] Hare, K. G.; Morris, I. D.; Sidorov, N.; Theys, J., An explicit counterexample to the Lagarias-Wang finiteness conjecture, Adv. Math., 226, 6, 4667-4701 (2011) · Zbl 1218.15005
[24] Lagarias, J. C.; Wang, Y., The finiteness conjecture for the generalized spectral radius of a set of matrices, Linear Algebra Appl., 214, 17-42 (1995) · Zbl 0818.15007
[25] Gurvits, L., Stability of discrete linear inclusions, Linear Algebra Appl., 231, 47-85 (1992)
[26] Mason, P.; Boscain, U.; Chitour, Y., Common polynomial Lyapunov functions for linear switched systems, SIAM J. Optim. Control, 45, 1 (2006) · Zbl 1132.93038
[27] Blondel, V. D.; Tsitsiklis, J. N., The boundedness of all products of a pair of matrices is undecidable, Systems Control Lett., 41, 135-140 (2000) · Zbl 0985.93042
[28] Blondel, V.; Gevers, M., Simultaneous stabilizability of three linear systems is rationally undecidable, Math. Control Signals Systems, 6, 2, 135-145 (1993) · Zbl 0792.93109
[29] Tarski, A., A Decision Method for Elementary Algebra and Geometry (1951), University of California Press: University of California Press Berkeley and Los Angeles, Calif · Zbl 0044.25102
[30] Seidenberg, A., A new decision method for elementary algebra, Ann. of Math. (2), 60, 365-374 (1954) · Zbl 0056.01804
[31] Blekherman, G.; Parrilo, P. A.; Thomas, R., (Semidefinite Optimization and Convex Algebraic Geometry. Semidefinite Optimization and Convex Algebraic Geometry, SIAM Series on Optimization (2013)) · Zbl 1260.90006
[32] Caviness, B. F.; Johnson, J. R., Quantifier Elimination and Cylindrical Algebraic Decomposition (1998), Springer Verlag · Zbl 0906.03033
[33] Reznick, B., Some concrete aspects of Hilbert’s 17th problem, (Contemporary Mathematics, Vol. 253 (2000), American Mathematical Society), 251-272 · Zbl 0972.11021
[35] Rota, G. C.; Strang, W. G., A note on the joint spectral radius, Indag. Math., 22, 379-381 (1960) · Zbl 0095.09701
[36] Theys, J., Joint Spectral Radius: theory and approximations (2005), Universite catholique de Louvain, (Ph.D. thesis)
[37] Bousch, T.; Mairesse, J., Asymptotic height optimization for topical IFS, Tetris heaps, and the finiteness conjecture, J. Amer. Math. Soc., 15, 1, 77-111 (2002) · Zbl 1057.49007
[38] Kozyakin, V., A dynamical systems construction of a counterexample to the finiteness conjecture, (44th IEEE Conference on Decision and Control, 2005 and 2005 European Control Conference. 44th IEEE Conference on Decision and Control, 2005 and 2005 European Control Conference, CDC-ECC’05 (2005), IEEE), 2338-2343
[39] Jungers, R. M.; Blondel, V. D., On the finiteness property for rational matrices, Linear Algebra Appl., 428, 10, 2283-2295 (2008) · Zbl 1148.15004
[41] Blondel, V. D.; Canterini, V., Undecidable problems for probabilistic automata of fixed dimension, Theory Comput. Syst., 36, 3, 231-245 (2003) · Zbl 1039.68061
[42] Jungers, R. M.; Protasov, V. Yu.; Blondel, V. D., Efficient algorithms for deciding the type of growth of products of integer matrices, Linear Algebra Appl., 428, 10, 2296-2311 (2008) · Zbl 1145.65030
[43] Parrilo, P. A., Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization (2000), California Institute of Technology, (Ph.D. thesis)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.