Article

Computational complexity of μ calculation

Richard P. BraatzDepartment of Chemical Engineering, California Institute of Technology, Pasadena, CA, USAPeter M. YoungDepartment of Electrical Engineering, California Institute of Technology, Pasadena, CA, USAJohn C. DoyleDepartment of Electrical Engineering, California Institute of Technology, Pasadena, CA, USAManfred MorariDepartment of Chemical Engineering, California Institute of Technology, Pasadena, CA, USA

1994en

ABI

Abstract

The structured singular value /spl mu/ measures the robustness of uncertain systems. Numerous researchers over the last decade have worked on developing efficient methods for computing /spl mu/. This paper considers the complexity of calculating /spl mu/ with general mixed real/complex uncertainty in the framework of combinatorial complexity theory. In particular, it is proved that the /spl mu/ recognition problem with either pure real or mixed real/complex uncertainty is NP-hard. This strongly suggests that it is futile to pursue exact methods for calculating /spl mu/ of general systems with pure real or mixed uncertainty for other than small problems.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>

Identifiers

DOI: 10.1109/9.284879

Citations and references

Cited by 60 references

Metrics — AkademScholar · Coming soon