Stability Testing of Matrix Polytopes
Dr Leonid Gurvitz (Los Alamos National Laboratory)
Abstract
Motivated by questions in robust control and switched linear
dynamical systems, we consider the problem checking whether every
element of a polytope of nxn matrices A is stable. Our contributions
are:
(i) we prove that the problem is NP-hard when the number of
extreme points of A is (n/2)-1; this explains why some previous attempts at a
solution in the control literature have failed
(ii) we show that the
NP-hardness of this problem implies that verifying the absolute
asymptotic stability of a continuous-time switched linear system with
n-1 nxn matrices A_i, with A_i + A_i^T nonpositive definite, is
NP-hard
(iii) in the case where A is a line, we propose an algorithm for
stability testing with runtime of O(n^5), in contrast to the O(n^6)
runtime of the best previously known algorithms
(iv) when the number of
extreme points of A is k, we give an algorithm which checks if every
eigenvalue of every matrix in A lies in an open conical set in C (e.g.
the left-half plane) in runtime O(2^{3k}) n^{3 [2^k]}), which is
polynomial for fixed k.
Putting these results together, we have that
the problem of testing the stability of A is solvable in polynomial-time
for constant number of extreme points k, but becomes NP-Hard when k grows
as O(n).
Back to
Control Seminars Page.