Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



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

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 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 $K$-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 $K$-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

Similar Articles

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

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

American Mathematical Society