×

zbMATH — the first resource for mathematics

Semidefinite programming vs. LP relaxations for polynomial programming. (English) Zbl 1082.90554
Summary: 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 H. D. Sherali and W. P. Adams [SIAM J. Discrete Math. 3, No. 3, 411–430 (1990; Zbl 0712.90050)], 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.

MSC:
90C22 Semidefinite programming
90C09 Boolean programming
90C26 Nonconvex programming, global optimization
14P99 Real algebraic and real-analytic geometry
Software:
SDPLR
PDF BibTeX XML Cite
Full Text: DOI