Global Polynomial Optimization via the Moment-SOS Hierarchy

This direction is merged into another direction: semidefinite programming scalability (curse of dimensionality in polynomial optimization). Its last version stays readable and citable here.

Version 1 of 115 papers16 conceptsfrozen 2026-10-04

Finding the global minimum of a non-convex function is generally NP-hard. While local search methods like gradient descent are efficient, they often get trapped in local optima, providing no guarantee that the result is the best possible solution. However, for problems where the objective and constraints are polynomials, a powerful mathematical framework known as the Moment-SOS hierarchy allows us to solve these "impossible" problems globally by transforming them into a sequence of convex programs.

The Core Intuition: Lifting to Measures

The fundamental challenge of non-convex optimization is that the "landscape" of the function is jagged. Jean B. Lasserre proposed a radical shift in perspective: instead of searching for a single optimal point $x^*$, we search for a probability measure $\mu$ that is supported on the set of global minimizers.

While the original problem is non-convex in the space of points, it becomes linear (and thus convex) in the space of measures. The catch is that the space of all possible measures is infinite-dimensional. To make this tractable, the Moment-SOS hierarchy "relaxes" the problem by looking only at the first few moments of the measure (e.g., the mean, variance, and higher-order correlations).

As explored in The Moment-SOS hierarchy: Applications and related topics, this creates a sequence of Semidefinite Programs (SDPs)—a well-understood class of convex optimization problems—of increasing size. Each step in the hierarchy provides a better lower bound on the global minimum.

The Dual View: Sum-of-Squares Certificates

Every optimization problem has a "dual" perspective. In this hierarchy, the dual of searching for moments is searching for Sum-of-Squares (SOS) polynomials.

To prove that a polynomial $f(x)$ is always greater than or equal to a value $\gamma$, it is sufficient to show that $f(x) - \gamma$ can be written as a sum of squared polynomials. If such a representation exists, it serves as a "certificate" of global non-negativity. Jean B. Lasserre demonstrated in S.o.s. approximation of polynomials nonnegative on a real algebraic set that these SOS certificates are universal: as the degree of the polynomials in the sum increases, we can approximate the non-negativity of any polynomial on a semi-algebraic set with arbitrary precision.

The "Miracle" of Finite Convergence

Theoretically, one might expect to need an infinite number of relaxation steps to reach the exact global optimum. However, a recurring theme in this research is finite convergence.

In practice, the hierarchy often "collapses" to the exact global solution in just a few steps. Jean B. Lasserre showed in Convexity in semi-algebraic geometry and polynomial optimization that for strictly convex problems, this convergence is guaranteed to be finite. Even more surprisingly, Jiawang Nie and colleagues have shown that for "generic" (almost all) polynomial problems, the hierarchy reaches the exact solution or proves non-existence in finite steps, as seen in their work on saddle point problems and variational inequalities.

Scaling and Applications

While the hierarchy is mathematically elegant, the size of the SDPs grows combinatorially with the number of variables and the degree of the polynomials. To address this, researchers like Jean B. Lasserre and Kim-Chuan Toh developed Sparse-BSOS, which exploits structured sparsity in the problem to handle thousands of variables.

This framework has moved beyond pure theory into complex engineering and data science domains:

Tools like GloptiPoly 3, developed by Didier Henrion and Jean B. Lasserre, have made these techniques accessible, allowing users to solve non-convex problems by simply defining the polynomials and letting the hierarchy handle the global certification.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_global_polynomial_optimization_via_the_m_77b9afb5,
  title = {Global Polynomial Optimization via the Moment-SOS Hierarchy},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/global-polynomial-optimization-via-the-moment-sos-hierarchy/rdr_77b9afb56b02430cb159a0de83845c52},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_global_polynomial_optimization_via_the_m_77b9afb5_v1,
  title = {Global Polynomial Optimization via the Moment-SOS Hierarchy},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/global-polynomial-optimization-via-the-moment-sos-hierarchy/rdr_77b9afb56b02430cb159a0de83845c52/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}