Semidefinite programming relaxations for semialgebraic problems

Semidefinite programming relaxations for semialgebraic problems

0.00 Avg rating0 Votes
Article ID: iaor20041759
Country: Germany
Volume: 96
Issue: 2
Start Page Number: 293
End Page Number: 320
Publication Date: Jan 2003
Journal: Mathematical Programming
Authors:
Keywords: semidefinite programming
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.

Reviews

Required fields are marked *. Your email address will not be published.