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.
- 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.
- As we increase the degree (the "relaxation order"), the SDP becomes larger and more complex, but the bound becomes tighter.
- 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:
- In Control Theory: Milan Korda and colleagues use it in Controller design and region of attraction estimation for nonlinear dynamical systems to "sandwich" the safe operating zones of a robot between guaranteed inner and outer bounds.
- In Statistics: David Steurer and Pravesh K. Kothari apply it in Outlier-robust moment-estimation via sum-of-squares to estimate the properties of a dataset even when an adversary has corrupted the data.
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.