Polynomials nonnegative on a grid and discrete optimization
Author:
Jean B. Lasserre
Journal:
Trans. Amer. Math. Soc. 354 (2002), 631649
MSC (2000):
Primary 13P99, 30C10; Secondary 90C10, 90C22
Published electronically:
October 4, 2001
MathSciNet review:
1862561
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: We characterize the realvalued 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
(89k:44013)
 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
(2000j:47027), http://dx.doi.org/10.1090/S0002994700024727
 3.
T. JACOBI, A representation theorem for certain partially ordered commutative rings, Mathematische Zeitschrift, 237 (2001), pp. 259273. 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), 223235. 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
(2001i:90062), http://dx.doi.org/10.1137/S1052623498336450
 7.
J.B. LASSERRE, Global optimization with polynomials and the problem of moments, SIAM J. Optim. 11 (2001), 796817.
 8.
J.B. LASSERRE, Optimality conditions and LMI relaxations for 01 programs, LAASCNRS 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
(92c:52016)
 10.
Mihai
Putinar, Positive polynomials on compact semialgebraic sets,
Indiana Univ. Math. J. 42 (1993), no. 3,
969–984. MR 1254128
(95h:47014), http://dx.doi.org/10.1512/iumj.1993.42.42045
 11.
Konrad
Schmüdgen, The 𝐾moment problem for compact
semialgebraic sets, Math. Ann. 289 (1991),
no. 2, 203–206. MR 1092173
(92b:44011), http://dx.doi.org/10.1007/BF01446568
 12.
Barry
Simon, The classical moment problem as a selfadjoint finite
difference operator, Adv. Math. 137 (1998),
no. 1, 82–203. MR 1627806
(2001e:47020), http://dx.doi.org/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
(2001e:90001)
 14.
Lieven
Vandenberghe and Stephen
Boyd, Semidefinite programming, SIAM Rev. 38
(1996), no. 1, 49–95. MR 1379041
(96m:90005), http://dx.doi.org/10.1137/1038003
 1.
 C. BERG. The multidimensional moment problem and semigroups, in: Moment in Mathematics (1987), pp. 110124, 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. 28252855. MR 2000j:47027
 3.
 T. JACOBI, A representation theorem for certain partially ordered commutative rings, Mathematische Zeitschrift, 237 (2001), pp. 259273. 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), 223235. 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), 750778. MR 2001i:90062
 7.
 J.B. LASSERRE, Global optimization with polynomials and the problem of moments, SIAM J. Optim. 11 (2001), 796817.
 8.
 J.B. LASSERRE, Optimality conditions and LMI relaxations for 01 programs, LAASCNRS Technical report #00099, submitted.
 9.
 L. LOVÁSZ AND A. SCHRIJVER, Cones of matrices and setfunctions and 01 optimization, SIAM J. Optim. 1 (1991), 166190. MR 92c:52016
 10.
 M. PUTINAR, Positive polynomials on compact semialgebraic sets, Ind. Univ. Math. J. 42 (1993), pp. 969984. MR 95h:47014
 11.
 K. SCHMÜDGEN, The moment problem for compact semialgebraic sets, Math. Ann. 289 (1991), pp. 203206. MR 92b:44011
 12.
 B. SIMON, The classical moment problem as a selfadjoint finite difference operator, Adv. Math. 137 (1998), 82203. 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. 320. MR 2001e:90001
 14.
 L. VANDENBERGHE AND S. BOYD, Semidefinite programming, SIAM Review 38 (1996), pp. 4995. 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:
LAASCNRS, 7 Avenue du Colonel Roche, 31077 Toulouse Cédex, France
Email:
lasserre@laas.fr
DOI:
http://dx.doi.org/10.1090/S0002994701028987
PII:
S 00029947(01)028987
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
