Polynomials nonnegative on a grid and discrete optimization

Authors
Citation
Jb. Lasserre, Polynomials nonnegative on a grid and discrete optimization, T AM MATH S, 354(2), 2001, pp. 631-649
Citations number
14
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Mathematics
Journal title
TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY
ISSN journal
0002-9947 → ACNP
Volume
354
Issue
2
Year of publication
2001
Pages
631 - 649
Database
ISI
SICI code
0002-9947(2001)354:2<631:PNOAGA>2.0.ZU;2-M
Abstract
We characterize the real-valued polynomials on R-n that are nonnegative (no t necessarily strictly positive) on a grid K of points of R-n, in terms of a weighted sum of squares whose degree is bounded and known in advance. We also show that the minimization of an arbitrary polynomial on K (a discrete optimization problem) reduces to a convex continuous optimization problem of fixed size. The case of concave polynomials is also investigated. The pr oof is based on a recent result of Curto and Fialkow on the K-moment proble m.