Stability Testing of Matrix Polytopes

arXivmath/0611092MaRDI QIDQ6478166FDOQ6478166

Leonid Gurvits, Alex Olshevsky

Publication date: 3 November 2006

Abstract: Motivated by questions in robust control and switched linear dynamical systems, we consider the problem checking whether all convex combinations of k matrices in R^{n x n} are stable. In particular, we are interested whether there exist algorithms which can solve this problem in time polynomial in n and k. We show that if $k=lceil{n}^{d}ceil$ for any fixed real d>0, then the problem is NP-hard, meaning that no polynomial-time algorithm in n exists provided that P is not NP, a widely believed conjecture in computer science. On the other hand, when k is a constant independent of n, then it is known that the problem may be solved in polynomial time in n. Using these results and the method of measurable switching rules, we prove our main statement: verifying the absolute asymptotic stability of a continuous-time switched linear system with more than n^d matrices A_i in R^{n x n} satisfying 0 >= A_i + A_i^{T} is NP-hard.

Mathematics Subject Classification ID

Popov-type stability of feedback systems (93D10)

This page was built for publication: Stability Testing of Matrix Polytopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6478166)