DocumentCode
294332
Title
NP-hardness of some linear control design problems
Author
Blondel, Vincent ; Tsitsiklis, John N.
Author_Institution
Inst. of Math., Liege, Belgium
Volume
3
fYear
1995
fDate
13-15 Dec 1995
Firstpage
2910
Abstract
We show that some basic linear control design problems are NP-hard, implying that, unless P=NP, they cannot be solved by polynomial time algorithms. The problems that we consider include simultaneous stabilization by output feedback, stabilization by state or output feedback in the presence of bounds on the elements of the gain matrix, and decentralized control. These results are obtained by first showing that checking the existence of a stable matrix in an interval family of matrices is an NP-hard problem
Keywords
closed loop systems; computational complexity; control system synthesis; linear systems; matrix algebra; stability; state feedback; NP-hard problem; bounds; decentralized control; gain matrix; linear control design; linear systems; output feedback; stabilization; state feedback; Closed loop systems; Control design; Control systems; Feedback control; Laboratories; Linear systems; Mathematics; Output feedback; Polynomials; State feedback;
fLanguage
English
Publisher
ieee
Conference_Titel
Decision and Control, 1995., Proceedings of the 34th IEEE Conference on
Conference_Location
New Orleans, LA
ISSN
0191-2216
Print_ISBN
0-7803-2685-7
Type
conf
DOI
10.1109/CDC.1995.478584
Filename
478584
Link To Document