Title :
NP-hardness of some linear control design problems
Author :
Blondel, Vincent ; Tsitsiklis, John N.
Author_Institution :
Inst. of Math., Liege, Belgium
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;
Conference_Titel :
Decision and Control, 1995., Proceedings of the 34th IEEE Conference on
Conference_Location :
New Orleans, LA
Print_ISBN :
0-7803-2685-7
DOI :
10.1109/CDC.1995.478584
