Real Algebraic and Analytic Geometry

Preprint Server

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


Submission: 2003, October 9.

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