CaltechAUTHORS
  A Caltech Library Service

Computational Complexity of μ Calculation

Braatz, Richard D. and Young, Peter M. and Doyle, John C. and Morari, Manfred (1993) Computational Complexity of μ Calculation. California Institute of Technology , Pasadena, CA. (Unpublished) http://resolver.caltech.edu/CaltechCDSTR:1993.005

[img]
Preview
PDF
See Usage Policy.

345Kb
[img] Postscript
See Usage Policy.

40Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechCDSTR:1993.005

Abstract

The structured singular value μ measures the robustness of uncertain systems. Numerous researchers over the last decade have worked on developing efficient methods for computing μ. This paper considers the complexity of calculating μ with general mixed real/complex uncertainty in the framework of combinatorial complexity theory. In particular, it is proved that the μ 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 μ of general systems with pure real or mixed uncertainty for other than small problems.


Item Type:Report or Paper (Technical Report)
Additional Information:The authors thank Professor John Tsitsiklis at MIT for his comments. [R.D.B. was] supported by the Fannie and John Hertz Foundation.
Group:Control and Dynamical Systems Technical Reports
Subject Keywords:NP-hard, structured singular value, computational complexity
Record Number:CaltechCDSTR:1993.005
Persistent URL:http://resolver.caltech.edu/CaltechCDSTR:1993.005
Usage Policy:You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.
ID Code:28063
Collection:CaltechCDSTR
Deposited By: Imported from CaltechCDSTR
Deposited On:01 Sep 2006
Last Modified:26 Dec 2012 14:29

Repository Staff Only: item control page