Semidefinite programming relaxations for semialgebraic problems
作者： Pablo A. Parrilo
DOI: 10.1007/S10107-003-0387-5
关键词:
摘要: A hierarchy of convex relaxations for semialgebraic problems is introduced. For questions reducible to a finite number of polynomial equalities and inequalities, it is shown how to construct a complete family of polynomially sized semidefinite programming conditions that prove infeasibility. The main tools employed are a semidefinite programming formulation of the sum of squares decomposition for multivariate polynomials, and some results from real algebraic geometry. The techniques provide a constructive approach for finding bounded …
core.ac.uk
springer.com
sci-hub.se 参考文章(46)
B. Reznick, T. Y. Lam, M. D. Choi, Sums of squares of real polynomials Amer. Math. Soc., Providence, R.I.. pp. 103- 126 ,(1995)
Saugata Basu, Laureano Gonzalez-Vega, Algorithmic and Quantitative Real Algebraic Geometry: DIMACS Workshop, Algorithmic and Quantitative Aspects of Real Algebraic, Geometry in Mathematics and Computer Science, March 12-16, 2001, DIMACS Center American Mathematical Society. ,(2003)
John Little, David A. Cox, Donal O'Shea, Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra ,(1992)
Nirmal K. Bose, Applied multidimensional systems theory ,(1981)
Jacek Bochnak, Marie-Françoise Roy, Michel Coste, Real Algebraic Geometry ,(2017)
Hanif D. Sherali, Warren P. Adams, A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems ,(1998)
Bruce Reznick, Some concrete aspects of Hilbert's 17th Problem Amer. Math. Soc., Providence, R.I.. pp. 251- 272 ,(2000) , 10.1090/CONM/253/03936
Yurii Nesterov, Squared Functional Systems and Optimization Problems Springer US. pp. 405- 440 ,(2000) , 10.1007/978-1-4757-3216-0_17
Jean B. Lasserre, Global Optimization with Polynomials and the Problem of Moments Siam Journal on Optimization. ,vol. 11, pp. 796- 817 ,(2000) , 10.1137/S1052623400366802
P. H. Diananda, On non-negative forms in real variables some or all of which are non-negative Mathematical Proceedings of the Cambridge Philosophical Society. ,vol. 58, pp. 17- 25 ,(1962) , 10.1017/S0305004100036185