Probabilistic solutions to some NP-hard matrix problems
Chernoff boundsNP-hardpolynomial inequalitiespolynomial-time randomized algorithmsrobust nonsingularityrobust norm boundednessrobust positive semidefinitenessrobust stabilitysimultaneous stabilizationstatistical learning theoryVapnik-Chervonenkis dimension
Complexity and performance of numerical algorithms (65Y20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Learning and adaptive systems in artificial intelligence (68T05) Randomized algorithms (68W20) Sensitivity (robustness) (93B35) Robust stability (93D09) Stabilization of systems by feedback (93D15)
Recently, several authors have shown that a number of problems in matrix theory are NP-hard [see, for example \textit{M. R. Garey} and \textit{D. S. Johnson}, Computers and intractability. A guide to the theory of NP-completeness. San Francisco: Freeman (1979; Zbl 0411.68039), and Papadimitrou (1994)], among them robust positive semidefiniteness, robust stability, robust norm boundedness and robust nonsingularity, constant output feedback stabilization with constraints and simultaneous stabilization using constant output feedback. The authors of the present paper show that it is possible to develop polynomial-time randomized algorithms for each of the above-mentioned NP-hard problems. While in the case of Problems 1-4, which are problems of analysis, the randomized algorithms are based on well-established results on Chernoff bounds, in the case of Problem 6 (Problem 5 is a special case of 6), a problem in synthesis, the randomized algorithm uses recent results from statistical learning theory on the Vapnik-Chervonenkis dimension of a family of sets defined by a finite number of polynomial inequalities. The present paper actually develops a broad framework for deriving polynomial-time randomized algorithms for any problem where the decision question to be answered with yes or no can be posed in terms of a finite number of polynomial inequalities.
- Randomized algorithms for robust controller synthesis using statistical learning theory
- A randomized approximation algorithm for a linear control design problem
- Probabilistic search algorithms for robust stability analysis and their complexity properties
- The real structured singular value is hardly approximable
- Probabilistic approach to the stability of interval matrices
- Checking robust nonsingularity is NP-hard
- scientific article; zbMATH DE number 1031310
- Several NP-hard problems arising in robust stability analysis
- The computational complexity of approximating the minimal perturbation scaling to achieve instability in an interval matrix
- scientific article; zbMATH DE number 733109
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
- A survey of computational complexity results in systems and control
- Checking robust nonsingularity is NP-hard
- Estimation of dependences based on empirical data. Transl. from the Russian by Samuel Kotz
- scientific article; zbMATH DE number 3138903 (Why is no real title available?)
- scientific article; zbMATH DE number 53984 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1263195 (Why is no real title available?)
- scientific article; zbMATH DE number 1322222 (Why is no real title available?)
- scientific article; zbMATH DE number 610968 (Why is no real title available?)
- scientific article; zbMATH DE number 1391397 (Why is no real title available?)
- scientific article; zbMATH DE number 3068536 (Why is no real title available?)
- NP-Hardness of Some Linear Control Design Problems
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- Output feedback stabilization and related problems-solution via decision methods
- Polynomial bounds for VC dimension of sigmoidal and general Pfaffian neural networks
- Probabilistic robustness analysis: Explicit bounds for the minimum number of samples
- Randomized algorithms for probabilistic robustness with real and complex structured uncertainty.
- Several NP-hard problems arising in robust stability analysis
- Stochastic robustness of linear time-invariant control systems
- Computational complexity of randomized algorithms for solving parameter-dependent linear matrix inequalities.
- Statistical learning methods in linear algebra and control problems: The example of finite-time control of uncertain linear systems
- A probabilistic framework for problems with real structured uncertainty in systems and control
- Checking robust nonsingularity is NP-hard
- Research on probabilistic methods for control system design
- Randomized methods for design of uncertain systems: sample complexity and sequential algorithms
- A survey of randomized algorithms for control synthesis and performance verification
- Randomized algorithms for robust controller synthesis using statistical learning theory: a tutorial overview
- On application of the ray-shooting method for LQR via static-output-feedback
- Tight bounds on the radius of nonsingularity
- A new probabilistic robust control approach for system with uncertain parameters
- A randomized approximation algorithm for a linear control design problem
- Statistical learning theory: a pack-based strategy for uncertain feasibility and optimization problems
- A statistical learning theory approach for uncertain linear and bilinear matrix inequalities
- A resilience optimization approach for workforce-inventory control dynamics under uncertainty
- Randomized sampling for large zero-sum games
- A randomised algorithm for computing static-output-feedbacks for large-scale systems
- On a new generalised LMI condition and randomised algorithm for robust stabilisation via static-output-feedback
- Fixed-order stabilising controller design by a mixed randomised/deterministic method
- A survey of computational complexity results in systems and control
- Randomized algorithms for robust controller synthesis using statistical learning theory
- Discussion on: ``GPC robust design using linear and/or bilinear matrix inequalities
- On the binomial confidence interval and probabilistic robust control
- Robust synthesis of a PID controller by uncertain multimodel approach
- Polynomial-time algorithms for probabilistic solutions of parameter-dependent linear matrix inequalities
- A randomized approximation algorithm for the minimal-norm static-output-feedback problem
- On nonsingularity of a polytope of matrices
This page was built for publication: Probabilistic solutions to some NP-hard matrix problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5947649)
