Probabilistic solutions to some NP-hard matrix problems. (English) Zbl 1031.93165
Recently, several authors have shown that a number of problems in matrix theory are NP-hard [see, for example M. R. Garey and 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.
Reviewer: R.Buckdahn (Brest)
MSC:
| 93E25 | Computational methods in stochastic control (MSC2010) |
| 65Y20 | Complexity and performance of numerical algorithms |
| 93B35 | Sensitivity (robustness) |
| 68T05 | Learning and adaptive systems in artificial intelligence |
| 93B40 | Computational methods in systems theory (MSC2010) |
| 93D09 | Robust stability |
| 93D15 | Stabilization of systems by feedback |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68W20 | Randomized algorithms |
Keywords:
NP-hard; robust positive semidefiniteness; robust stability; robust norm boundedness; robust nonsingularity; simultaneous stabilization; polynomial-time randomized algorithms; Chernoff bounds; statistical learning theory; Vapnik-Chervonenkis dimension; polynomial inequalitiesCitations:
Zbl 0411.68039References:
| [1] | Anderson, B. D.O.; Bose, N. K.; Jury, E. I., Output feedback stabilization and related problems—Solution via decision methods, IEEE Transactions on Automatic Control, AC-20, 53-66 (1975) · Zbl 0302.93026 |
| [2] | Anthony, M.; Biggs, N., Computational learning theory (1992), Cambridge University Press: Cambridge University Press Cambridge, UK · Zbl 0755.68115 |
| [3] | Blondel, V. D.; Tsitsiklis, J. N., NP-hardness of some linear control design problems, SIAM Journal on Control and Optimization, 35, 2118-2127 (1997) · Zbl 0892.93050 |
| [4] | Blondel, V. D.; Tsitsiklis, J. N., A survey of computational complexity results in systems and control, Automatica, 36, 9, 1249-1274 (2000) · Zbl 0989.93006 |
| [5] | Calafiore, G., Dabbene, F., & Tempo, R. (1999). Randomized algorithms and probabilistic robustness with real and complex structured uncertainty, preprint.; Calafiore, G., Dabbene, F., & Tempo, R. (1999). Randomized algorithms and probabilistic robustness with real and complex structured uncertainty, preprint. · Zbl 1056.93599 |
| [6] | Chernoff, H., A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations, Annals of Mathematical Statistics, 23, 493-507 (1952) · Zbl 0048.11804 |
| [7] | Gantmacher, F. R., Matrix theory. Vol. II (1959), Chelsea: Chelsea New York · Zbl 0085.01001 |
| [8] | Garey, M. R.; Johnson, D. S., Computers and intractability: A guide to the theory of NP-completeness (1979), Freeman: Freeman New York · Zbl 0411.68039 |
| [9] | Karpinski, M., & Macintyre, A. J. (1995). Polynomial bounds for VC dimension of sigmoidal neural networks. Proceedings of the 27th ACM Symposium Theories of Computing; Karpinski, M., & Macintyre, A. J. (1995). Polynomial bounds for VC dimension of sigmoidal neural networks. Proceedings of the 27th ACM Symposium Theories of Computing · Zbl 0978.68562 |
| [10] | Karpinski, M.; Macintyre, A. J., Polynomial bounds for VC dimension of sigmoidal and general Pfaffian neural networks, Journal of Computer System and Sciences, 54, 169-176 (1997) · Zbl 0869.68088 |
| [11] | Kearns, M.; Vazirani, U., Introduction to computational learning theory (1994), MIT Press: MIT Press Cambridge |
| [12] | Khargonekar, P. P., & Tikku, A. (1996). Randomized algorithms for robust control analysis have polynomial complexity. Proceeding Conference on Decision and Control; Khargonekar, P. P., & Tikku, A. (1996). Randomized algorithms for robust control analysis have polynomial complexity. Proceeding Conference on Decision and Control |
| [13] | Marrison, C., & Stengel, R. (1994). The use of random search and genetic algorithms to optimize stochastic robustness functions. Proceedings of the American Control Conference; Marrison, C., & Stengel, R. (1994). The use of random search and genetic algorithms to optimize stochastic robustness functions. Proceedings of the American Control Conference |
| [14] | Nemirovskii, A., Several NP-hard problems arising in robust stability analysis, Mathematics of Control, Signals, and Systems, 6, 2, 99-105 (1993) · Zbl 0792.93100 |
| [15] | Papadimitrou, C., Computational complexity (1994), Addison-Wesley: Addison-Wesley Reading, MA, USA · Zbl 0833.68049 |
| [16] | Poljak, S.; Rohn, J., Checking robust nonsingularity is NP-hard, Mathematics of Control, Signals, and Systems, 6, 1, 1-9 (1993) · Zbl 0780.93027 |
| [17] | Ray, L. R.; Stengel, R. F., Stochastic robustness of linear time-invariant control systems, IEEE Transactions on Automatic Control, 36, 82-87 (1991) · Zbl 0722.93017 |
| [18] | Tarski, A., A decision method for elementary algebra and geometry (1951), University of California Press: University of California Press Berkeley, USA · Zbl 0044.25102 |
| [19] | Tempo, R. E.; Bai, W.; Dabbene, F., Probabilistic robustness analysis: Explicit bounds for the minimum number of sampling points, Systems & Control Letters, 30, 237-242 (1997) · Zbl 0901.93017 |
| [20] | Vapnik, V. N., Estimation of dependences based on empirical data (1982), Springer-Verlag: Springer-Verlag New York · Zbl 0499.62005 |
| [21] | Vapnik, V. N., The nature of statistical learning theory (1995), Springer-Verlag: Springer-Verlag New York · Zbl 0934.62009 |
| [22] | Vapnik, V. N.; Chervonenkis, A. Ya., On the uniform convergence of relative frequencies to their probabilities, Theory of Probability and its Applications, 16, 2, 264-280 (1971) · Zbl 0247.60005 |
| [23] | Vidyasagar, M., A theory of learning and generalization: with applications to neural networks and control systems (1997), Springer-Verlag: Springer-Verlag London · Zbl 0928.68061 |
| [24] | Vidyasagar, M. (1997b). Statistical learning theory and its applications to randomized algorithms for robust controller synthesis. (Semi-Plenary Talk), European Control Conference, Brussels, Belgium.; Vidyasagar, M. (1997b). Statistical learning theory and its applications to randomized algorithms for robust controller synthesis. (Semi-Plenary Talk), European Control Conference, Brussels, Belgium. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
