This thesis is an exposition of ideas and methods that help un- derstanding the problem of minimizing a polynomial over a basic closed semi-algebraic set. After the introduction of some the- ory on mathematical tools such as sums of squares, nonnegative polynomials and moment matrices, several Positivstellensa ̈tze are considered. Positivstellens ̈atze provide sums of squares represen- tations of polynomials, positive on basic closed semi-algebraic sets. Subsequently, semi-definite programming methods, in par- ticular based on Putinar’s Postivstellensatz, are considered. In order to use semi-definite programming, certain degree bounds are set. These bounds give rise to a hierarchy of approximations of the minimum of a polynomial, which will also be discussed. Finally, some new results are given that are obtained by looking at sums of squares representations of a positive polynomial when minimizing over the unit hypercube .
Additional Metadata
Keywords polynomial optimization, sums of squares, semidefinite programming, Positivstellensatz
THEME Logistics (theme 3)
Thesis Advisor M. Laurent (Monique) , A. Schrijver (Alexander)
Citation
van Eeghen, P. (2013, March). Polynomial Optimization Methods.