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) https://resolver.caltech.edu/CaltechCDSTR:1993.005

[img]
Preview
PDF - Submitted Version
See Usage Policy.

354kB
[img] Postscript - Submitted Version
See Usage Policy.

41kB

Use this Persistent URL to link to this item: https://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)
Related URLs:
URLURL TypeDescription
http://resolver.caltech.edu/CaltechAUTHORS:BRAieeetac94Related ItemJournal Article
http://resolver.caltech.edu/CaltechAUTHORS:20190320-132001216Related ItemConference Paper
ORCID:
AuthorORCID
Doyle, John C.0000-0002-1828-2486
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
Funders:
Funding AgencyGrant Number
Fannie and John Hertz FoundationUNSPECIFIED
Subject Keywords:NP-hard, structured singular value, computational complexity
Record Number:CaltechCDSTR:1993.005
Persistent URL:https://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:03 Oct 2019 03:28

Repository Staff Only: item control page