Stability Testing of Matrix Polytopes

Details Stability Testing of Matrix Polytopes Stability Testing of Matrix Polytopes

2006-11-03

arxiv.org/abs/math/0611092v4

Mathematics

Optimization and Control

journal version

Scientific paper

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 \rceil$ 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.

Affiliated with

Also associated with

No associations

Rating

Stability Testing of Matrix Polytopes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Stability Testing of Matrix Polytopes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Stability Testing of Matrix Polytopes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-76138