Optimization Online


Semidefinite programming vs LP relaxations for polynomial programming

Jean B. Lasserre (lasserre***at***laas.fr)

Abstract: 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 and recent SDP (semi definite programming) relaxations introduced by the author. The comparison is analyzed in the light of recent results in real algebraic geometry on various representations of polynomials, positive on a compact semi algebraic set.

Keywords: global optimization; SDP and LP relaxations; real algebraic geometry;

Category 1: Global Optimization (Theory )

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 3: Linear, Cone and Semidefinite Programming (Linear Programming )

Citation: Math. Oper. Res. 27 (2002), pp. 347--360 http://pubsonline.informs.org/main/index.php?user=48814


Entry Submitted: 12/07/2001
Entry Accepted: 12/07/2001
Entry Last Modified: 07/15/2002

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society