Real Algebraic and Analytic Geometry

Preprint Server

RAAG_NETWORK.gif
Previous   Next
10. Markus Schweighofer:
On the complexity of Schmüdgen's Positivstellensatz.

e-mail:
homepage: http://perso.univ-rennes1.fr/markus.schweighofer/

Submission: 2003, October 9.

Abstract:
We prove complexity bounds for Schmüdgen's Positivstellensatz and investigate the recently popular approximation of nonconvex polynomial optimization problems by semidefinite programs.

Mathematics Subject Classification (2000): 11E25, 13J30, 14P10, 44A60, 68W40, 90C26.

Keywords and Phrases: Positivstellensatz, complexity, positive polynomial, sum of squares, preordering, moment problem, optimization of polynomials.

Full text, 16p.: dvi 61k, ps.gz 92k, pdf 200k.


Server Home Page