NP-hardness of some linear control design problems

被引：298

作者：

Blondel, V ^{[1
]}

Tsitsiklis, JN ^{[1
]}

机构：

[1] MIT,INFORMAT & DECIS SYST LAB,CAMBRIDGE,MA 02139

来源：

SIAM JOURNAL ON CONTROL AND OPTIMIZATION | 1997年 / 35卷 / 06期

关键词：

control design; complexity; linear control;

D O I：

10.1137/S0363012994272630

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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 NP-hard.

引用

页码：2118 / 2127

页数：10

共 17 条

[1] OUTPUT FEEDBACK STABILIZATION AND RELATED PROBLEMS - SOLUTION VIA DECISION METHODS [J].