Semidefinite programming vs. linear programming relaxations for polynomial programming

Semidefinite programming vs. linear programming relaxations for polynomial programming

0.00 Avg rating0 Votes
Article ID: iaor2004402
Country: United States
Volume: 27
Issue: 2
Start Page Number: 347
End Page Number: 360
Publication Date: May 2002
Journal: Mathematics of Operations Research
Authors:
Keywords: programming: linear
Abstract:

We consider the global minimization of a multivariate polynomial on a semi-algebraic set Ω defined with polynomial inequalities. We then compare two hierarchies of relaxations, namely, LP relaxations based on products of the original constraints, in the spirit of the RLT procedure of Sherali and Adams, and recent semidefinite programming (SDP) relaxations introduced by the author. The comparison is analyzed in light of recent results in real algebraic geometry on various representations of polynomials, positive on a compact semi-algebraic set.

Reviews

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