Markus Schweighofer
Polynomial Optimization via Semidefinite Programming
Prof. Markus Schweighofer
Fachbereich Mathematik und Statistik
Universität Konstanz
Time & Place
The presentation will be given on April 18, 2013 at 5.30 p.m. and takes place in the seminar room V 0.05/2-3. This is the Max-Planck-Instiute at Sandtorstraße 1.
Abstract
Polynomial optimization is concerned with minimizing or maximizing a polynomial objective function subject to a finite number of polynomial constraints. The constraints are non-strict real polynomial inequalities in several variables. A very successful technique to solve these problems has emerged since the turn of the millennium: The basic idea is to relax the problem by replacing all nonlinear monomials by new variables. As a matter of course, the resulting linear program would in general carry little information about the original problem. To delimit the loss of information during the linearization procedure, one adds infinite families of polynomial inequalities which are redundant in the original polynomial optimization problem but carry important information after being linearized. Each such family is chosen in a way such that it becomes a single linear matrix inequality when linearized. The linearized problem is no longer a linear program but still a semidefinite program and can therefore be solved efficiently. But what exactly do the optimal solutions of the original problem have to do with the original problem?
Short CV
since 09/2009 Universität Konstanz, full professor
09/07--08/09 Université de Rennes 1, maître de conférences
09/03--08/07 Universität Konstanz, scientific employee
09/02--08/03 Université de Rennes 1, post-doc
2002 Ph.D. Universität Konstanz
1999 Diplom Passau