Abstract
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 H/sup /spl infin// controller design problem, and several other control problems can be formulated as BMIs. 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 output feedback is an NP-hard problem, namely for given n plants, the problem of checking the existence of a static gain matrix, which stabilizes all of the n plants, is NP-hard.
Keywords
MathematicsBilinear interpolationMatrix (chemical analysis)PolynomialOutput feedbackOrder (exchange)Linear matrix inequalityFunction (biology)Control theory (sociology)Applied mathematicsMathematical optimizationControl (management)Computer scienceMathematical analysis
Affiliated Institutions
Related Publications
A New Approach to Manipulator Control: The Cerebellar Model Articulation Controller (CMAC)
CM AC is an adaptive system by which control functions for many degrees of freedom operating simultaneously can be computed by referring to a table rather than by mathematical s...
On the Complexity of Multiple Sequence Alignment
We study the computational complexity of two popular problems in multiple sequence alignment: multiple alignment with SP-score and multiple tree alignment. It is shown that the ...
Stable adaptive controller design, part II: Proof of stability
The paper presents a proof of stability of model reference adaptive control systems using direct control. The structure of the adaptive system is similar to that considered by M...
Co-clustering documents and words using bipartite spectral graph partitioning
Both document clustering and word clustering are well studied problems. Most existing algorithms cluster documents and words separately but not simultaneously. In this paper we ...
On manipulator control by exact linearization
Comments on the application to rigid link manipulators of geometric control theory, resolved acceleration control, operational space control, and nonlinear decoupling theory are...
Publication Info
- Year
- 2005
- Type
- article
- Volume
- 4
- Pages
- 2525-2526
- Citations
- 331
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
331
OpenAlex
Cite This
O. Toker,
Hitay Özbay
(2005).
On the NP-hardness of solving bilinear matrix inequalities and simultaneous stabilization with static output feedback.
, 4
, 2525-2526.
https://doi.org/10.1109/acc.1995.532300
Identifiers
- DOI
- 10.1109/acc.1995.532300