Markus Schweighofer: Using semidefinite programming for polynomial optimization problems

Abstract: Many polynomial optimization problems can be solved numerically by relaxing them to a semidefinite program. Semidefinite programs are generalizations of linear programs, and like them can be solved very quickly. This idea is underlying some recent software packages like GloptiPoly, SparsePOP, SOSTOOLS and YALMIP. We will present the basic ideas of this method, show how well-known results like the Goemans-Williamson algorithm for the MAXCUT problem fit into its framework, and discuss the most recent aspects like the behaviour of polynomials modulo their gradient ideal.