Computational complexity and related topics of robustness margin calculation using μ theory: A review of theoretical developments

This paper provides a comprehensive overview of research related to computational complexity of structured singular value (a.k.a. μ) problems. A survey of computational complexity results in μ problems is followed by a concise introduction to computational complexity theory that is useful to characterize the inherent difficulty of solving an optimization. Results on the study for NP-hardness of ϵ-approximation of μ problems are discussed and conservatism of convex μ upper-bounds including ones obtained from absolute stability theory is studied. NP-hardness of μ computation and conservatism of convex upper-bounds open new research trends. In particular, we give an overview of polynomial-time model reduction methods and probabilistic randomized algorithms that have been active research topics since the mid-1990s.