SIAM Journal on Control and Optimization · 1997 · 440 citations · 11 references
EngineeringSystems EngineeringDecentralizationDistributed SystemsProcess ControlControl Of Dynamical SystemsControl SystemsControl TheoryController DesignDecentralized ControlFeedback ControlDecentralized Control DesignLinear ControlNp-hardnessOutput Feedback ControlPolynomial Time ComplexityPolynomial-time Algorithms
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.
11
Computational complexity of μ calculation
Richard P. Braatz, Peter M. Young, John C. Doyle et al. · IEEE Transactions on Automatic Control · 1994 · 327 citations