Semidefinite Approximations for Global Unconstrained Polynomial Optimization

Dorina Jibetean (D.Jibeteancwi.nl)
Monique Laurent (M.Laurentcwi.nl)

Abstract: We consider here the problem of minimizing a polynomial function on $\oR^n$. The problem is known to be hard even for degree $4$. Therefore approximation algorithms are of interest. Lasserre \cite{lasserre:2001} and Parrilo \cite{Pa02a} have proposed approximating the minimum of the original problem using a hierarchy of lower bounds obtained via semidefinite programming relaxations. We propose here a method for computing a converging sequence of upper bounds using semidefinite programming based on perturbing the original polynomial. The method is applied to several examples.

Keywords: polynomial optimization, semidefinite programming

Category 1: Global Optimization (Theory )

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

Category 3: Nonlinear Optimization (Unconstrained Optimization )

Citation: To appear in SIAM Journal on Optimization

Download: [Postscript][PDF]

Entry Submitted: 03/25/2004
Entry Accepted: 03/30/2004
Entry Last Modified: 05/24/2005

Modify/Update this entry