×

A new look at nonnegativity on closed sets and polynomial optimization. (English) Zbl 1242.90176

In this paper the authors show first that a continuous function \(f\) is nonnegative on a closed set \(\mathbf K\subseteq \mathbb R^{n}\) if and only if (countably many) moment matrices of some signed measure d\(\nu = fd\mu \) with supp \(\mu = \mathbf K\) are all positive semidefinite (if \(\mathbf K\) is compact, \(\mu \) is an arbitrary finite Borel measure with supp \(\mu = \mathbf K\)). In particular, the authors obtain a convergent explicit hierarchy of semidefinite (outer) approximations with no lifting of the cone of nonnegative polynomials of degree at most d. When used in polynomial optimization on certain simple closed sets \(\mathbf K\) (e.g., the whole space \(\mathbb R^{n}\), the positive orthant, a box, a simplex, or the vertices of the hypercube), it provides a nonincreasing sequence of upper bounds which converges to the global minimum by solving a hierarchy of semidefinite programs with only one variable (in fact, a generalized eigenvalue problem). In the compact case, this convergent sequence of upper bounds complements the convergent sequence of lower bounds obtained by solving a hierarchy of semidefinite relaxations as in, e.g., [J. B. Lasserre, SIAM J. Optim. 11, No. 3, 796–817 (2001; Zbl 1010.90061)].

MSC:

90C26 Nonconvex programming, global optimization
28C15 Set functions and measures on topological spaces (regularity of measures, etc.)

Citations:

Zbl 1010.90061

Software:

GloptiPoly
PDFBibTeX XMLCite
Full Text: DOI arXiv