Legat, Benoît
[UCL]
Jungers, Raphaël M.
[UCL]
Parrilo, Pablo A.
[Massachussets Institute of Technology, Cambridge, MA, USA]
The joint spectral radius (JSR) of a set of matrices characterizes the maximal asymptotic growth rate of an infinite product of matrices of the set. This quantity appears in a number of applications including the stability of switched and hybrid systems. Many algorithms exist for estimating the JSR but not much is known about how to generate an infinite sequence of matrices with an optimal asymptotic growth rate. To the best of our knowledge, the currently known algorithms select a small sequence with large spectral radius using brute force (or branch-and-bound variants) and repeats this sequence infinitely. In this paper we introduce a new approach to this question, using the dual solution of a sum of squares optimization program for JSR approximation. Our algorithm produces an infinite sequence of matrices with an asymptotic growth rate arbitrarily close to the JSR. The algorithm naturally extends to the case where the allowable switching sequences are determined by a graph or finite automaton. Unlike the brute force approach, we provide a guarantee on the closeness of the asymptotic growth rate to the JSR. This, in turn, provides new bounds on the quality of the JSR approximation. We provide numerical examples illustrating the good performance of the algorithm.
- Rota Gian–Carlo, Gilbert Strang W., A note on the joint spectral radius, 10.1016/s1385-7258(60)50046-1
- M. Philippe, R. Essick, G. Dullerud, and R. M. Jungers. Stability of discrete-time switching systems with constrained switching sequences. arXiv preprint arXiv:1503.06984, 2015.
- Parrilo Pablo A., Jadbabaie Ali, Approximation of the joint spectral radius using sum of squares, 10.1016/j.laa.2007.12.027
- Lee Ji-Woong, Dullerud Geir E., Uniform stabilization of discrete-time switched and Markovian jump linear systems, 10.1016/j.automatica.2005.08.019
- Kozyakin Victor, The Berger–Wang formula for the Markovian joint spectral radius, 10.1016/j.laa.2014.01.022
- Jungers Raphaël M., Cicone Antonio, Guglielmi Nicola, Lifted Polytope Methods for Computing the Joint Spectral Radius, 10.1137/130907811
- Jungers Raphaël, The Joint Spectral Radius, ISBN:9783540959793, 10.1007/978-3-540-95980-9
- Guglielmi Nicola, Zennaro Marino, An algorithm for finding extremal polytope norms of matrix families, 10.1016/j.laa.2007.07.009
- Gripenberg Gustaf, Computing the joint spectral radius, 10.1016/0024-3795(94)00082-4
- Dai Xiongping, A Gel’fand-type spectral radius formula and stability of linear constrained switching systems, 10.1016/j.laa.2011.07.029
- L. Cambier, M. Philippe, and R. Jungers. The CSSystem toolbox. http://www.mathworks.com/matlabcentral/fileexchange/52723-the-cssystem-toolbox, August 2015.
- Blondel Vincent D., Tsitsiklis John N., The boundedness of all products of a pair of matrices is undecidable, 10.1016/s0167-6911(00)00049-9
- Blondel Vincent D., Nesterov Yurii, Computationally Efficient Approximations of the Joint Spectral Radius, 10.1137/040607009
- Barak Boaz, Brandao Fernando G.S.L., Harrow Aram W., Kelner Jonathan, Steurer David, Zhou Yuan, Hypercontractivity, sum-of-squares proofs, and their applications, 10.1145/2213977.2214006
- Ahmadi Amir Ali, Parrilo Pablo A., Joint spectral radius of rank one matrices and the maximum cycle mean problem, 10.1109/cdc.2012.6425992
- Ahmadi Amir Ali, Jungers Raphaël M., Parrilo Pablo A., Roozbehani Mardavij, Joint Spectral Radius and Path-Complete Graph Lyapunov Functions, 10.1137/110855272
Bibliographic reference |
Legat, Benoît ; Jungers, Raphaël M. ; Parrilo, Pablo A.. Generating unstable trajectories for switched systems via Dual Sum-Of-Squares techniques.The 19th International Conference on Hybrid Systems : Computation and Control (Vienna, Austria, du 12/04/2016 au 14/04/2016). In: Proceeding HSCC '16 Proceedings of the 19th International Conference on Hybrid Systems : Computation and Control, p. 51-60 |
Permanent URL |
http://hdl.handle.net/2078.1/180245 |