Global optimization of polynomial functions under polynomial constraints will be related to general algorithmic problems in real algebraic geometry and the current existing complexity results discussed. The results in the special case of quadratic polynomials will be described. Main reference for the talk: S. Basu, R. Pollack, M.-F. Roy: Algorithms in real algebraic geometry, Springer, second edition (2006)