Polynomials nonnegative on a grid and discrete optimization

Author:
Jean B. Lasserre

Journal:
Trans. Amer. Math. Soc. **354** (2002), 631-649

MSC (2000):
Primary 13P99, 30C10; Secondary 90C10, 90C22

Published electronically:
October 4, 2001

MathSciNet review:
1862561

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We characterize the real-valued polynomials on that are nonnegative (not necessarily strictly positive) on a grid of points of , 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 (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 -moment problem.

**1.**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**, 10.1090/psapm/037/921086**2.**Raúl E. Curto and Lawrence A. Fialkow,*The truncated complex 𝐾-moment problem*, Trans. Amer. Math. Soc.**352**(2000), no. 6, 2825–2855. MR**1661305**, 10.1090/S0002-9947-00-02472-7**3.**T. JACOBI,*A representation theorem for certain partially ordered commutative rings*, Mathematische Zeitschrift,**237**(2001), pp. 259-273. CMP**2001:14****4.**T. JACOBI AND A. PRESTEL,*On special representations of strictly positive polynomials*, Technical report, Konstanz University, Konstanz, Germany, January 2000.**5.**T. JACOBI AND A. PRESTEL,*Distinguished representations of strictly positive polynomials*, J. Reine Angew. Math.**532**(2001), 223-235. CMP**2001:09****6.**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**, 10.1137/S1052623498336450**7.**J.B. LASSERRE,*Global optimization with polynomials and the problem of moments*, SIAM J. Optim.**11**(2001), 796-817.**8.**J.B. LASSERRE,*Optimality conditions and LMI relaxations for 0-1 programs*, LAAS-CNRS Technical report #00099, submitted.**9.**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****10.**Mihai Putinar,*Positive polynomials on compact semi-algebraic sets*, Indiana Univ. Math. J.**42**(1993), no. 3, 969–984. MR**1254128**, 10.1512/iumj.1993.42.42045**11.**Konrad Schmüdgen,*The 𝐾-moment problem for compact semi-algebraic sets*, Math. Ann.**289**(1991), no. 2, 203–206. MR**1092173**, 10.1007/BF01446568**12.**Barry Simon,*The classical moment problem as a self-adjoint finite difference operator*, Adv. Math.**137**(1998), no. 1, 82–203. MR**1627806**, 10.1006/aima.1998.1728**13.**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****14.**Lieven Vandenberghe and Stephen Boyd,*Semidefinite programming*, SIAM Rev.**38**(1996), no. 1, 49–95. MR**1379041**, 10.1137/1038003

Retrieve articles in *Transactions of the American Mathematical Society*
with MSC (2000):
13P99,
30C10,
90C10,
90C22

Retrieve articles in all journals with MSC (2000): 13P99, 30C10, 90C10, 90C22

Additional Information

**Jean B. Lasserre**

Affiliation:
LAAS-CNRS, 7 Avenue du Colonel Roche, 31077 Toulouse Cédex, France

Email:
lasserre@laas.fr

DOI:
https://doi.org/10.1090/S0002-9947-01-02898-7

Keywords:
Algebraic geometry; positive polynomials; $\K$-moment problem; semidefinite programming

Received by editor(s):
November 11, 2000

Published electronically:
October 4, 2001

Article copyright:
© Copyright 2001
American Mathematical Society