Journal
SIAM JOURNAL ON OPTIMIZATION
Volume 16, Issue 2, Pages 490-514Publisher
SIAM PUBLICATIONS
DOI: 10.1137/04060562X
Keywords
semidefinite programming; global optimization; approximation algorithm; positive polynomial; sum of squares of polynomials; moment matrix
Categories
Ask authors/readers for more resources
We consider the problem of minimizing a polynomial function on R-n, known to be hard even for degree 4 polynomials. Therefore approximation algorithms are of interest. Lasserre [SIAM J. Optim., 11 (2001), pp. 796-817] and Parrilo [Math. Program., 96 (2003), pp. 293-320] 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 tight upper bounds based on perturbing the original polynomial and using semidefinite programming. The method is applied to several examples.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available