Computational complexity of robust stability and regularity in families of linear systems
Gregory Emmett Coxson, Christopher L. DeMarco · 1993
In an engineering system modeled by linear ordinary differential equations, the location of eigenvalues is a useful indicator of time domain response for analysis and design. For many engineering applications, a typical specification might require that all eigenvalues have negative real part, or are confined to some specified region of the complex plane. When the system model depends on unknown constants, one would like to test whether the desired eigenvalue locations are maintained for all possible values of the constant parameters. This type of computation is refered to as a stability test. This dissertation delineates forms of parameter dependence in the system matrix that allow tractable tests of robust stability, versus those forms of parameter dependence that lead to intractable computations in the worst case. Similar conclusions for the corresponding tests of matrix regularity, or robust nonsingularity, are provided as well. In order to achieve algorithm-independent determinations of computational complexity, use is made of NP-completeness theory and the theory of approximation complexity for NP-hard optimization problems. The key finding is that testing robust or regularity of matrix families with characteristic polynomials having coefficients that are bilinear functions of parameters is NP-hard. This implies that unless P = NP, which is widely believed to be false, worst-case computation time for any such test will be exponential in input size. For the same class of matrix families, it is proven that computing the rightmost eigenvalue is MAX-SNP-hard, which means that unless P = NP there can be no polynomial-time approximation scheme which achieves worst-case approximation ratio arbitrarily close to 1. Combining these determinations with results in the literature, the class of matrix families with characteristic polynomials having coefficients dependent in an affine fashion on parameters is established as the most general for which practical robust or regularity tests are possible.