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

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

Published electronically:
October 4, 2001

MathSciNet review:
1862561

Full-text PDF

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.**C. BERG.*The multidimensional moment problem and semi-groups*, in: Moment in Mathematics (1987), pp. 110-124, ed. H.J. Landau, Amer. Math. Soc. MR**89k:44013****2.**R.E. CURTO AND L. A. FIALKOW.*The truncated complex**-moment problem*, Trans. Amer. Math. Soc.**352**(2000), pp. 2825-2855. MR**2000j:47027****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.**M. KOJIMA AND L. TUNSCEL, *Cones of matrices and successive convex relaxations of non convex sets*, SIAM J. Optim.**10**(2000), 750-778. MR**2001i:90062****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,*Cones of matrices and set-functions and 0-1 optimization*, SIAM J. Optim.**1**(1991), 166-190. MR**92c:52016****10.**M. PUTINAR,*Positive polynomials on compact semi-algebraic sets*, Ind. Univ. Math. J.**42**(1993), pp. 969-984. MR**95h:47014****11.**K. SCHMÜDGEN,*The**-moment problem for compact semi-algebraic sets*, Math. Ann.**289**(1991), pp. 203-206. MR**92b:44011****12.**B. SIMON,*The classical moment problem as a self-adjoint finite difference operator*, Adv. Math.**137**(1998), 82-203. MR**2001e:47020****13.**J. F. STURM,*Theory and algorithms of semidefinite programming*, in*High Performance Optimization methods*, H. Frenk, K. Roos and S. Zhang eds., Kluwer Academic Publishers, Dordrecht, 2000, pp. 3-20. MR**2001e:90001****14.**L. VANDENBERGHE AND S. BOYD,*Semidefinite programming*, SIAM Review**38**(1996), pp. 49-95. MR**96m:90005**

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