Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, November 15, 2001, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Pablo A. Parrilo (Institut für Automatik, ETH)
Many applied math problems can be completely characterized with a finite number of polynomial inequalities and inequalities. A few concrete examples are geometric theorems, graph theoretic problems, and issues of network survivability and reliability. In general, this class of problems have bad complexity properties, and exact algorithms to solve them are usually computationally infeasible.
As a consequence, considerable research efforts have been directed towards the efficient computation of approximate solutions (or bounds). In this talk, we present a new convex optimization framework for polynomial-based problems. The key element is the interaction of concepts from real algebra and convex optimization, in particular a semidefinite programming formulation for the sums of squares decomposition for multivariable polynomials.
The developed techniques unify and generalize many well-known existing results. The ideas and algorithms will be illustrated with examples from a broad range of application domains.
Automatic MiSe System Software Version 1.4803M | admin login