The Moment Sum of Squares Hierarchy for Global Optimization

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2354 papers436 conceptsfrozen 2026-10-04

Most optimization problems are easy to solve if they are convex, but notoriously difficult if they are not. When we deal with polynomials—functions that appear everywhere from robotics to power grids—we often face "landscapes" filled with local minima that trap standard algorithms.

The Moment-Sum-of-Squares (Moment-SOS) hierarchy, often referred to as the Lasserre hierarchy, provides a systematic way to solve these non-convex problems. It works by "lifting" a difficult problem in a few variables into a sequence of easier, convex problems in a higher-dimensional space. As Adam N. Letchford, Jean B. Lasserre, and Pablo Parrilo highlight in The 2013 Newton Institute Programme on polynomial optimization, this framework bridges the gap between pure algebraic geometry and practical computational engineering.

The Core Intuition: Proving Positivity

To find the global minimum of a polynomial $f(x)$, we are essentially looking for the largest constant $\gamma$ such that $f(x) - \gamma \geq 0$ for all $x$. Proving that a polynomial is always non-negative is the fundamental challenge.

The "Sum of Squares" (SOS) insight is simple: if we can write a polynomial as a sum of squared polynomials, such as $f(x) = g_1(x)^2 + g_2(x)^2$, then $f(x)$ is obviously non-negative for any real $x$. While not every non-negative polynomial is a sum of squares, many are. Crucially, checking if a polynomial has an SOS representation is a convex problem that can be solved efficiently using Semidefinite Programming (SDP).

As Jean B. Lasserre demonstrates in Best $\ell_1$-approximation of nonnegative polynomials by sums of squares, we can use SDP to find the "closest" SOS polynomial to any given non-negative one, effectively turning a "hard" algebraic problem into an "easy" numerical one.

The Hierarchy: Trading Complexity for Accuracy

The "hierarchy" part of the name refers to the degree of the polynomials we use in our SOS proof.

  1. At the lowest level, we look for a simple SOS proof using low-degree polynomials. This gives us a quick but potentially loose lower bound on the minimum.
  2. As we increase the degree (the "relaxation order"), the SDP becomes larger and more complex, but the bound becomes tighter.
  3. Under broad conditions, this sequence of bounds is guaranteed to converge to the true global optimum.

Jesús A. De Loera and Peter N. Malkin explain in Computation with Polynomial Equations and Inequalities Arising in Combinatorial Optimization that this hierarchy allows us to analyze systems involving inequalities by seeking these SOS representations, systematically tightening the convex relaxations as the degree increases.

Dual Perspectives: Moments and Measures

The framework has a beautiful duality. While the SOS side looks at functions and proofs of positivity, the Moment side looks at the data itself.

Instead of optimizing over points $x$, we optimize over "pseudo-distributions" or "moments" (like mean and variance) of a potential solution. Didier Henrion describes this in Chapter 10: Conic Linear Optimization for Nonlinear Optimal Control as "lifting" the problem into the space of measures. By representing a measure through a finite sequence of its moments, we can transform non-convex trajectories into linear programs over those moments.

This dual view is what makes the hierarchy so versatile. For example:

Solving the Unsolvable

The true power of this research direction lies in its ability to provide provable guarantees for problems that were previously considered "black boxes."

In the energy sector, the Alternating Current Optimal Power Flow (ACOPF) problem is essential for running the grid but is highly non-convex due to the physics of electricity. Bissan Ghaddar, Jakub Marecek, and Martin Mevissen showed in Optimal Power Flow as a Polynomial Optimization Problem that by treating this as a polynomial problem and applying the hierarchy, they could achieve provable global optimality for medium-sized grids and high-quality bounds for massive ones.

Whether it is finding saddle points in games (Jiawang Nie and Zi Yang in The Saddle Point Problem of Polynomials) or identifying the dynamics of quantum systems (Denys I. Bondar et al. in Recovering models of open quantum systems from data via polynomial optimization), the Moment-SOS hierarchy provides a unified mathematical language to turn the "hard" geometry of polynomials into the "solvable" algebra of semidefinite matrices.

Papers in this version

Showing 60 of 354 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 254 papers
  2. Version 1 · 2026-10-04 · 354 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_semidefinite_programming_relaxation_ca9be9b9,
  title = {semidefinite programming relaxation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/semidefinite-programming-relaxation/rdr_ca9be9b9af29430b8a8d17584a828539},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_the_moment_sum_of_squares_hierarchy_for__ca9be9b9_v1,
  title = {The Moment Sum of Squares Hierarchy for Global Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/the-moment-sum-of-squares-hierarchy-for-global-optimization/rdr_ca9be9b9af29430b8a8d17584a828539/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}