Martin Mevissen, ETH Zurich
Abstract:
Polynomial optimization problems are in general nonconvex and therefore difficult to solve. New developments in real algebra and methods based on semidefinite programming are applied to attempt polynomial optimization problems. We present the results from real algebra, in particular a Positivstellensatz by Putinar, that lay the foundation for the recent approaches to polynomial optimization. Also, we introduce the semidefinite programming procedures by Parrilo to obtain sum of squares decompositions and infeasibility certificates for semialgebraic sets. The moment theory is mentioned which is closely related to nonnegativity of polynomials and sum of squares decompositions. As a focus of this talk we discuss Lasserre's approach to convexify a general polynomial optimization problem. This approach is based on applying Putinar's Positivstellensatz and results from moment theory to approximate the polynomial optimization problem by a convergent sequence of semidefinite programs. We show how to take into account structured sparsity in polynomial optimization problems in order to improve the numerical efficiency of Lasserre's approach.