A New Look at Nonnegativity on Closed Sets and Polynomial Optimization

Jean B. LasserreSIAM J. Optim 2011 · DOI

Abstract: We first show that a continuous function is nonnegative on a closed set if and only if (countably many) moment matrices of some signed measure with $d\nu = f d\mu$ are all positive semidefinite (if $K$ is compact, $\mu$ is an arbitrary finite Borel measure with $supp(\mu) = K$). In particular, we 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 (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.

Introduction

In the field of global optimization, determining the global minimum $f^*$ of a polynomial $f$ on a set $K$ is a fundamental challenge. For the past two decades, the "Lasserre Hierarchy" has been a cornerstone of this field, primarily known for providing a sequence of semidefinite programming (SDP) relaxations that yield increasingly tight lower bounds on $f^*$. However, these methods often leave a gap: while they tell us what the minimum cannot be below, they do not inherently provide a guaranteed upper bound unless a feasible point is explicitly found that matches the lower bound.

Standard approaches for obtaining upper bounds typically rely on local search heuristics, such as gradient descent, which lack global convergence guarantees and can easily become trapped in local optima. This paper introduces a novel theoretical framework that characterizes nonnegativity on closed sets through measure theory, resulting in a convergent hierarchy of upper bounds that are both computationally efficient and theoretically robust.

A Measure-Theoretic Characterization of Nonnegativity

The central innovation of this work is the shift from purely algebraic certificates of nonnegativity (like Sum of Squares) to a measure-theoretic perspective. Lasserre demonstrates that a continuous function $f$ is nonnegative on a closed set $K$ if and only if the integral of $f$ against any "squared" polynomial is nonnegative with respect to a reference measure $\mu$ supported on $K$.

Specifically, the paper proves that $f \ge 0$ on $K$ if and only if the moment matrices associated with the signed measure $d\nu = f d\mu$ are all positive semidefinite. This provides a "no-lifting" certificate; unlike standard SOS methods that require adding a large number of auxiliary variables to project high-dimensional spectrahedra, this method defines the approximation directly within the space of the polynomial's coefficients.

The Hierarchy of Upper Bounds

By considering polynomials of increasing degree $2d$, Lasserre constructs a sequence of values $\lambda_d$. Each $\lambda_d$ represents the largest value such that the moment matrix of the measure $(f - \lambda) d\mu$ remains positive semidefinite.

Computational Efficiency via Generalized Eigenvalues

A significant practical advantage of this approach is its computational simplicity. Lasserre shows that finding $\lambda_d$ does not require a general-purpose, heavy-duty SDP solver. Instead, the problem reduces to a generalized eigenvalue problem for a pair of real symmetric matrices. This "one-variable" optimization is significantly faster and more numerically stable than general SDPs, making it a highly attractive alternative for large-scale problems.

Reference Measures

To implement this hierarchy, one must be able to compute the moments of a reference measure $\mu$ whose support is exactly the set $K$. The paper provides explicit, tractable choices for $\mu$ on several common geometries:

  • Entire Space ($\mathbb{R}^n$): Gaussian measures.
  • Positive Orthant: Exponential measures.
  • Compact Sets: Uniform measures on boxes, simplices, or balls.
  • Discrete Sets: Counting measures on the vertices of a hypercube.

Numerical Benchmarks and Results

The method was evaluated against several classic challenges in polynomial optimization:

  1. The Motzkin Polynomial: This is a famous example of a polynomial that is nonnegative but cannot be represented as a sum of squares. The proposed hierarchy successfully handles such cases where traditional SOS methods might struggle without complex modifications.
  2. MAXCUT Problems: By treating discrete optimization on graphs as polynomial optimization over hypercube vertices, the method provides a new avenue for bounding combinatorial problems.
  3. Non-attained Minima: The hierarchy is shown to converge even in cases where the global minimum exists but is not achieved at any finite point (e.g., $x^2 + (1-xy)^2$ on the positive orthant), a scenario that often defeats local search algorithms.

Key Insights and Conclusion

This work completes the "sandwich" of polynomial optimization. By providing a convergent hierarchy of upper bounds to complement the existing lower-bound hierarchies, researchers can now trap the true global minimum within a provably shrinking interval. The "no-lifting" property and the reduction to generalized eigenvalue problems represent a significant step forward in making principled global optimization computationally accessible.

However, some limitations remain. The method currently requires the moments of the reference measure to be known, which limits its immediate application to "simple" sets. Furthermore, while initial convergence is often rapid, the "long tail" behavior—where convergence slows down as the bound approaches the true minimum—and numerical conditioning at very high degrees remain areas for future investigation. Despite these challenges, the framework offers a powerful new tool for characterizing nonnegativity and solving global optimization problems.

Summary updated

BibTeX
@article{lasserre2011new,
  author = {Jean B. Lasserre},
  title = {{A New Look at Nonnegativity on Closed Sets and Polynomial Optimization}},
  journal = {SIAM J. Optim.},
  year = {2011},
  doi = {10.1137/100806990},
}
Figure