TP4- 3:30 of solving Bilinear Matrix Inequalities and simultaneous stabilization with static output feedback

In this paper, it is shown that the problem of checking the solvability of a bilinear matrix inequality (BMI), is NP-hard. A matrix valued function, F ( X, Y) , is called bilinear if it is linear with respect to each of its arguments, and an inequality of the form, F ( X, Y) > 0 is called a bilinear matrix inequality. Recently, it was shown that, the static output feedback problem, fixed order controller problem, reduced order '?P controller design problem, and several other control problems can be formulated as BMIs [4, 31. Based on the results of [4, 31, BMIs seem to be a potentially powerful tool for the formulation of some important control problems. But the main result of this paper shows that the problem of checking the solvability of BMIs is NP-hard, and hence it is rather unlikely to find a polynomial time algorithm for solving general BMI problems. As an independent result, it is also shown that simultaneous stabilization with static out-put feedback is an NP-hard problem, namely given n plants, the problem of checking the existence of a static gain matrix, K, which stabilizes all of the n plants, is NP-hard. 1