Probabilistic solutions to some NP-hard matrix problems

DOI10.1016/S0005-1098(01)00089-9zbMath1031.93165WikidataQ127289790 ScholiaQ127289790MaRDI QIDQ5947649

Blondel, Vincent D., Mathukumalli Vidyasagar

Publication date: 4 March 2004

Published in: Automatica (Search for Journal in Brave)

zbMATH Keywords

robust stabilityNP-hardChernoff boundspolynomial inequalitiespolynomial-time randomized algorithmsrobust nonsingularityrobust norm boundednessrobust positive semidefinitenesssimultaneous stabilizationstatistical learning theoryVapnik-Chervonenkis dimension

Mathematics Subject Classification ID

Sensitivity (robustness) (93B35) Learning and adaptive systems in artificial intelligence (68T05) Stabilization of systems by feedback (93D15) Robust stability (93D09) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity and performance of numerical algorithms (65Y20) Randomized algorithms (68W20)

Related Items

A probabilistic framework for problems with real structured uncertainty in systems and control, A survey of randomized algorithms for control synthesis and performance verification, On application of the ray-shooting method for LQR via static-output-feedback, Robust synthesis of a PID controller by uncertain multimodel approach, A randomized approximation algorithm for the minimal-norm static-output-feedback problem, A statistical learning theory approach for uncertain linear and bilinear matrix inequalities, On nonsingularity of a polytope of matrices, A resilience optimization approach for workforce-inventory control dynamics under uncertainty, Randomized sampling for large zero-sum games, A survey of computational complexity results in systems and control, On the binomial confidence interval and probabilistic robust control, Randomized algorithms for robust controller synthesis using statistical learning theory, Statistical Learning Theory: A Pack-based Strategy for Uncertain Feasibility and Optimization Problems, Research on probabilistic methods for control system design, Randomized algorithms for robust controller synthesis using statistical learning theory: a tutorial overview, Discussion on: ``GPC robust design using linear and/or bilinear matrix inequalities, A New Probabilistic Robust Control Approach for System with Uncertain Parameters, Randomized methods for design of uncertain systems: sample complexity and sequential algorithms, Fixed-order stabilising controller design by a mixed randomised/deterministic method, 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, Statistical learning methods in linear algebra and control problems: The example of finite-time control of uncertain linear systems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Polynomial bounds for VC dimension of sigmoidal and general Pfaffian neural networks
• Estimation of dependences based on empirical data. Transl. from the Russian by Samuel Kotz
• Several NP-hard problems arising in robust stability analysis
• Probabilistic robustness analysis: Explicit bounds for the minimum number of samples
• Checking robust nonsingularity is NP-hard
• Randomized algorithms for probabilistic robustness with real and complex structured uncertainty
• Stochastic robustness of linear time-invariant control systems
• Output feedback stabilization and related problems-solution via decision methods
• NP-Hardness of Some Linear Control Design Problems
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• 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