The computational complexity of approximating the minimal perturbation scaling to achieve instability in an interval matrix
A typical approach to characterizing robust stability (regularity) of an interval matrix with a stable (nonsingular) center matrix is to compute the minimum scaling of the nonnegative error matrix (specifying maximum elementwise perturbations from the center matrix) for which instability (singularity) is achieved. Here, it is shown that approximating this minimum scaling is a MAX-SNP-hard problem. This implies that in general, unless the class of deterministic polynomial-time decision problems equals the class of nondeterministic polynomial-time decision problems (not likely), this minimum scaling cannot be approximated with a ratio arbitrarily close to unity in polynomial time. As an intermediate step in deriving this result, a class of interval matrix families is exhibited for which regularity and robust stability are equivalent. This is a generalization of an earlier result [\textit{A. Nemirovskij}, Math. Control Signals Syst. 6, 99-105 (1993; Zbl 0792.93100)], and may be of independent interest in the study of robust stability problems for interval matrices.
- Checking robust nonsingularity is NP-hard
- Computational complexity of μ calculation
- scientific article; zbMATH DE number 3138903 (Why is no real title available?)
- scientific article; zbMATH DE number 3474957 (Why is no real title available?)
- scientific article; zbMATH DE number 1256636 (Why is no real title available?)
- scientific article; zbMATH DE number 3797626 (Why is no real title available?)
- Interval Methods for Systems of Equations
- Several NP-hard problems arising in robust stability analysis
- Some simplified NP-complete graph problems
- The Componentwise Distance to the Nearest Singular Matrix
- On computational complexity of invalidating structured uncertainty models
- Several NP-hard problems arising in robust stability analysis
- Complexity issues in robust stability of linear delay-differential systems
- Randomized algorithms for robust controller synthesis using statistical learning theory: a tutorial overview
- Normality, scaling and eigenvalue inclusion regions
- A survey of computational complexity results in systems and control
- Randomized algorithms for robust controller synthesis using statistical learning theory
- Probabilistic solutions to some NP-hard matrix problems
This page was built for publication: The computational complexity of approximating the minimal perturbation scaling to achieve instability in an interval matrix
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1894653)
