Checking robust nonsingularity is NP-hard

DOI10.1007/BF01213466zbMath0780.93027OpenAlexW2022602688WikidataQ92958254 ScholiaQ92958254MaRDI QIDQ1802197

Jiří Rohn, Svatopluk Poljak

Publication date: 26 January 1994

Published in: MCSS. Mathematics of Control, Signals, and Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01213466

zbMATH Keywords

interval matricesrobust nonsingularityradius of nonsingularity

Mathematics Subject Classification ID

Sensitivity (robustness) (93B35)

Related Items (89)

A probabilistic framework for problems with real structured uncertainty in systems and control ⋮ Regularity radius and real eigenvalue range ⋮ The P-matrix problem is co-NP-complete ⋮ Radii of solvability and unsolvability of linear systems ⋮ On the stability of a convex set of matrices ⋮ Helly-type theorems and generalized linear programming ⋮ A survey of randomized algorithms for control synthesis and performance verification ⋮ Enclosing solutions of linear interval equations is NP-hard ⋮ Worst-case and average \(\mathcal{H}_2\) performance analysis against real constant parametric uncertainty ⋮ Inversion error, condition number, and approximate inverses of uncertain matrices ⋮ Checking bounds on solutions of linear interval equations is NP-hard ⋮ The computational complexity of approximating the minimal perturbation scaling to achieve instability in an interval matrix ⋮ Characteristic polynomial assignment for plants with semialgebraic uncertainty: A robust diophantine equation approach ⋮ Static output feedback -- a survey ⋮ Complexity issues in robust stability of linear delay-differential systems ⋮ Real eigenvalue bounds of standard and generalized real interval eigenvalue problems ⋮ On Relation Between P-Matrices and Regularity of Interval Matrices ⋮ On distributional robustness of systems with complex uncertainty ⋮ A bright side of NP-hardness of interval computations: Interval heuristics applied to NP-problems ⋮ Approximate linear algebra is intractable ⋮ Minimum phase robustness for uncertain state-space systems ⋮ Theorems of Perron-Frobenius type for matrices without sign restrictions ⋮ Checking robust nonsingularity of tridiagonal matrices in linear time ⋮ Mixed robustness: analysis of systems with uncertain deterministic and random parameters by the example of linear systems ⋮ Verified inclusions for a nearest matrix of specified rank deficiency via a generalization of Wedin's \(\sin (\theta)\) theorem ⋮ Guardian map approach to robust stability of interval systems ⋮ On computational complexity of invalidating structured uncertainty models ⋮ On the complexity of the robust stability problem for linear parameter varying systems ⋮ Relations between various methods for solving linear interval and parametric equations ⋮ Generalized eigenvalue for even order tensors via Einstein product and its applications in multilinear control systems ⋮ A note on checking regularity of interval matrices ⋮ Performance and accuracy of the basic closure algorithm of quadrature-based moment methods ⋮ Sufficient regularity conditions for complex interval matrices and approximations of eigenvalues sets ⋮ On real structured controllability/stabilizability/stability radius: complexity and unified rank-relaxation based methods ⋮ An algorithm for addressing the real interval eigenvalue problem ⋮ Computing nearby non-trivial Smith forms ⋮ A note on regularity and positive definiteness of interval matrices ⋮ How to determine basis stability in interval linear programming ⋮ Almost Sharp Bounds for the Componentwise Distance to the Nearest Singular Matrix ⋮ Fast interval matrix multiplication ⋮ A nonlinear programming technique to compute a~tight~lower bound for the real structured singular value ⋮ Complexity of computing interval matrix powers for special classes of matrices. ⋮ Tolerances, robustness and parametrization of matrix properties related to optimization problems ⋮ Structured singular value approach for systems with parametric uncertainty ⋮ Strong NP-completeness of a matrix similarity problem ⋮ Computing the spectral decomposition of interval matrices and a study on interval matrix powers ⋮ Branch and bound algorithm with applications to robust stability ⋮ Nonsingularity, positive definiteness, and positive invertibility under fixed-point data rounding. ⋮ A survey of computational complexity results in systems and control ⋮ A theorem of the alternatives for the equationAx+B|x| =b ⋮ Rank one interval enclosure of the parametric united solution set ⋮ A theorem of the alternatives for the equation \(|Ax|-|B||x|=b\) ⋮ On the computation of structured singular values and pseudospectra ⋮ On solving vague systems of linear equations with pattern-shaped columns ⋮ Positively regular vague matrices ⋮ Worst‐case stability and performance with mixed parametric and dynamic uncertainties ⋮ On the complexity of matrix rank and rigidity ⋮ Randomized algorithms for robust controller synthesis using statistical learning theory ⋮ Probabilistic solutions to some NP-hard matrix problems ⋮ Low-rank matrix approximation in the infinity norm ⋮ Linear interval parametric approach to testing pseudoconvexity ⋮ Computing lower rank approximations of matrix polynomials ⋮ Calculation of exact bounds for the solution set of linear interval systems ⋮ Verified error bounds for multiple roots of systems of nonlinear equations ⋮ Monte Carlo and Las Vegas randomized algorithms for systems and control. An introduction ⋮ Randomized algorithms for robust controller synthesis using statistical learning theory: a tutorial overview ⋮ Tight Bounds on the Radius of Nonsingularity ⋮ Letter to the editor ⋮ A survey of extreme point results for robustness of control systems ⋮ A new vertex result for robustness problems with interval matrix uncertainty ⋮ Discussion on: ``Why is resorting to fate wise? A critical look at randomized algorithms in systems and control ⋮ Stability of the linear complementarity problem properties under interval uncertainty ⋮ Regularity radius: Properties, approximation and a not a priori exponential algorithm ⋮ On the Complexity of Robust PCA and ℓ₁-Norm Low-Rank Matrix Approximation ⋮ Worst-case properties of the uniform distribution and randomized algorithms for robustness analysis ⋮ Componentwise pseudospectrum of a matrix ⋮ The maximum row length nonsingularity radius ⋮ Eigenvectors of interval matrices over max--plus algebra ⋮ Challenges of symbolic computation: My favorite open problems. With an additional open problem by Robert M. Corless and David J. Jeffrey ⋮ How strong is strong regularity? ⋮ The boundedness of all products of a pair of matrices is undecidable ⋮ A characterization of convex cones of matrices with constant regular inertia ⋮ Computing the norm ∥A∥∞,1 is NP-hard^∗ ⋮ Linear Programming with Inexact Data is NP‐Hard ⋮ Several NP-hard problems arising in robust stability analysis ⋮ A pair of matrices sharing common Lyapunov solutions--A closer look ⋮ Regularity of interval matrices and theorems of the alternatives ⋮ Nonsmooth bundle trust-region algorithm with applications to robust stability ⋮ On \(P\)-matrices

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Systems of linear interval equations
• A polynomial time heuristic for certain subgraph optimization problems with guaranteed worst case bound
• A solvable case of quadratic 0-1 programming
• Facets for the cut cone. I
• Laplacian eigenvalues and the maximum cut problem
• Tournament Ranking with Expected Profit in Polynomial Time
• Complexity of Partial Satisfaction
• Minimization of ±1 matrices under line shifts

This page was built for publication: Checking robust nonsingularity is NP-hard