Computational complexity of a problem arising in fixed order output feedback design

This paper is concerned with a matrix inequality problem which arises in fixed order output feedback control design. This problem involves finding two symmetric and positive definitive matrices X and Y such that each satisfies a linear matrix inequality and that XY=I. It is well-known that many control problems such as fixed order output feedback stabilization, H_∞ control, guaranteed H₂ control, and mixed H₂/H_∞ control can all be converted into the matrix inequality problem above, including static output feedback problems as a special case. We show, however, that this matrix inequality problem is NP-hard.