On the NP-Hardness of Checking Matrix Polytope Stability and Continuous-Time Switching Stability
Lists
Only you see this
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 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">ntimesn</sup> 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=n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">d</sup> for any fixed real d > 0, then the problem is NP-hard, meaning that no polynomial-time algorithm in n exists provided that P ne 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 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">d</sup> matrices A <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</sub> isin R <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">ntimesn</sup> satisfying 0 ges A <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</sub> + A <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</sub> <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">T</sup> is NP-hard.
BibTeX
@article{gurvits2009np,
author = {Leonid Gurvits and Alexander Olshevsky},
title = {{On the NP-Hardness of Checking Matrix Polytope Stability and Continuous-Time Switching Stability}},
journal = {IEEE Trans. Automatic Control},
year = {2009},
url = {https://openreview.net/forum?id=Es7q4vEwSuq},
}Loading related content...