document: Semidefinite programming vs. LP relaxations for polynomial programming 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 -LRB- 1990 -RRB- , and recent semidefinite programming -LRB- SDP -RRB- 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
doc_bio_tags: O O O B I O B I O O O B I O O B I O O O O O O O B I O O O O O O O O O O O B I O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I I O O O O O O O O O O O O
extractive_keyphrases: polynomial programming lp relaxations global minimization multivariate polynomial polynomial inequalities real algebraic geometry rlt procedure
abstractive_keyphrases: semidefinite programming relaxations reformulation linearization technique semi-algebraic set constraint products