SDP and LP relaxations for polynomial programming
Jean B. Lasserre
LAAS-CNRS, Toulouse, France
We consider the global minimization of a multivariate polynomial on a compact semi-algebraic set. Recently, results of real algebraic geometry have permitted to define a hierarchy of SDP-relaxations whose monotone sequence of optimal values converges to the global optimum. Alternatively, using a recent result of Vasilescu, we show that one may also define a hierarchy of LP-relaxations with the same convergence property. This results validates the Sherali-Adams RLT technique whose convergence was known for 0-1 programs and for problems with polytope as feasible set. Relative merits of SDP and LP relaxations are also discussed.