Semidefinite programming relaxations for semialgebraic problems |
| |
Authors: | Pablo A Parrilo |
| |
Institution: | (1) Automatic Control Laboratory, Swiss Federal Institute of Technology (ETH), CH-8092 Zurich, Switzerland, e-mail: parrilo@aut.ee.ethz.ch, CH |
| |
Abstract: | A hierarchy of convex relaxations for semialgebraic problems is introduced. For questions reducible to a finite number of
polynomial equalities and inequalities, it is shown how to construct a complete family of polynomially sized semidefinite
programming conditions that prove infeasibility. The main tools employed are a semidefinite programming formulation of the
sum of squares decomposition for multivariate polynomials, and some results from real algebraic geometry. The techniques provide
a constructive approach for finding bounded degree solutions to the Positivstellensatz, and are illustrated with examples
from diverse application fields.
Received: May 10, 2001 / Accepted May 2002
Published online: April 10, 2003
Key Words. semidefinite programming – convex optimization – sums of squares – polynomial equations – real algebraic geometry
The majority of this research has been carried out while the author was with the Control & Dynamical Systems Department,
California Institute of Technology, Pasadena, CA 91125, USA. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|