4.4 Article

Semidefinite programming vs. LP relaxations for polynomial programming

Journal

MATHEMATICS OF OPERATIONS RESEARCH
Volume 27, Issue 2, Pages 347-360

Publisher

INST OPERATIONS RESEARCH MANAGEMENT SCIENCES
DOI: 10.1287/moor.27.2.347.322

Keywords

global optimization; real algebraic geometry; semidefinite relaxations; LP relaxations

Ask authors/readers for more resources

We consider the global minimization of a multivariate polynomial on a semi-algebraic set Omega 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 (1990), 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.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.4
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available