## Polynomials nonnegative on a grid and discrete optimization

HTML articles powered by AMS MathViewer

- by Jean B. Lasserre
- Trans. Amer. Math. Soc.
**354**(2002), 631-649 - DOI: https://doi.org/10.1090/S0002-9947-01-02898-7
- Published electronically: October 4, 2001
- PDF | Request permission

## Abstract:

We characterize the real-valued polynomials on $\mathbb R^n$ that are nonnegative (not necessarily strictly positive) on a grid $\mathbb K$ of points of $\mathbb R^n$, in terms of a weighted sum of squares whose degree is bounded and known in advance. We also show that the mimimization of an arbitrary polynomial on $\mathbb K$ (a discrete optimization problem) reduces to a convex continuous optimization problem of fixed size. The case of concave polynomials is also investigated. The proof is based on a recent result of Curto and Fialkow on the $\mathbb K$-moment problem.## References

- Christian Berg,
*The multidimensional moment problem and semigroups*, Moments in mathematics (San Antonio, Tex., 1987) Proc. Sympos. Appl. Math., vol. 37, Amer. Math. Soc., Providence, RI, 1987, pp. 110–124. MR**921086**, DOI 10.1090/psapm/037/921086 - Raúl E. Curto and Lawrence A. Fialkow,
*The truncated complex $K$-moment problem*, Trans. Amer. Math. Soc.**352**(2000), no. 6, 2825–2855. MR**1661305**, DOI 10.1090/S0002-9947-00-02472-7 - T. Jacobi,
*A representation theorem for certain partially ordered commutative rings*, Mathematische Zeitschrift,**237**(2001), pp. 259–273. - T. Jacobi and A. Prestel,
*On special representations of strictly positive polynomials*, Technical report, Konstanz University, Konstanz, Germany, January 2000. - T. Jacobi and A. Prestel,
*Distinguished representations of strictly positive polynomials*, J. Reine Angew. Math.**532**(2001), 223–235. - Masakazu Kojima and Levent Tunçel,
*Cones of matrices and successive convex relaxations of nonconvex sets*, SIAM J. Optim.**10**(2000), no. 3, 750–778. MR**1774772**, DOI 10.1137/S1052623498336450 - J.B. Lasserre,
*Global optimization with polynomials and the problem of moments*, SIAM J. Optim.**11**(2001), 796–817. - J.B. Lasserre,
*Optimality conditions and LMI relaxations for 0-1 programs*, LAAS-CNRS Technical report #00099, submitted. - L. Lovász and A. Schrijver,
*Matrix cones, projection representations, and stable set polyhedra*, Polyhedral combinatorics (Morristown, NJ, 1989) DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 1, Amer. Math. Soc., Providence, RI, 1990, pp. 1–17. MR**1105111**, DOI 10.1090/dimacs/001/01 - Mihai Putinar,
*Positive polynomials on compact semi-algebraic sets*, Indiana Univ. Math. J.**42**(1993), no. 3, 969–984. MR**1254128**, DOI 10.1512/iumj.1993.42.42045 - Konrad Schmüdgen,
*The $K$-moment problem for compact semi-algebraic sets*, Math. Ann.**289**(1991), no. 2, 203–206. MR**1092173**, DOI 10.1007/BF01446568 - Barry Simon,
*The classical moment problem as a self-adjoint finite difference operator*, Adv. Math.**137**(1998), no. 1, 82–203. MR**1627806**, DOI 10.1006/aima.1998.1728 - Jos F. Sturm,
*Theory and algorithms of semidefinite programming*, High performance optimization, Appl. Optim., vol. 33, Kluwer Acad. Publ., Dordrecht, 2000, pp. 1–194. MR**1750470** - Lieven Vandenberghe and Stephen Boyd,
*Semidefinite programming*, SIAM Rev.**38**(1996), no. 1, 49–95. MR**1379041**, DOI 10.1137/1038003

## Bibliographic Information

**Jean B. Lasserre**- Affiliation: LAAS-CNRS, 7 Avenue du Colonel Roche, 31077 Toulouse Cédex, France
- MR Author ID: 110545
- Email: lasserre@laas.fr
- Received by editor(s): November 11, 2000
- Published electronically: October 4, 2001
- © Copyright 2001 American Mathematical Society
- Journal: Trans. Amer. Math. Soc.
**354**(2002), 631-649 - MSC (2000): Primary 13P99, 30C10; Secondary 90C10, 90C22
- DOI: https://doi.org/10.1090/S0002-9947-01-02898-7
- MathSciNet review: 1862561