Exploiting Correlative Sparsity in Polynomial Optimization

65 concepts51 papers1 proposal

Finding the global minimum of a multivariate polynomial is a notoriously difficult, non-convex problem. The standard modern toolkit for achieving global optimality relies on the Moment-SOS (Sum-of-Squares) hierarchy, pioneered by Lasserre (and synthesized in works like The Moment-SOS hierarchy and The Moment-SOS hierarchy: Applications and related topics). This framework reformulates global polynomial optimization into a sequence of convex Semidefinite Programs (SDPs). As the degree of the relaxation increases, the solution is guaranteed to converge monotonically to the true global optimum.

However, this mathematical elegance comes with a massive computational bottleneck. For a polynomial with $n$ variables relaxed at degree $d$, the size of the corresponding semidefinite matrix scales combinatorially ($O(n^d)$). As a result, dense SOS relaxations quickly become intractable for problems with more than a few dozen variables. As noted by Hohmann et al. and Chuong et al., failing to exploit the underlying structural relationships between variables leads to massive, redundant calculations that cripple scalability.

The solution lies in a powerful structural insight: real-world systems rarely feature dense, all-to-all interactions. By identifying and exploiting correlative sparsity, researchers can bypass this exponential explosion, scaling global optimization to thousands of variables.

The Intuition of Correlative Sparsity

In a physical network, a dynamic control loop, or a geometric vision problem, a given variable typically interacts only with a small subset of other variables.

To build intuition, imagine an optimization problem over four variables ($x_1, x_2, x_3, x_4$) where the objective function is:

$$f(x) = x_1 x_2 + x_2 x_3 + x_3 x_4$$

In this function, $x_1$ never directly multiplies $x_4$. The variables are linked in a chain-like graph rather than a fully connected clique. A dense SOS relaxation ignores this, constructing a monolithic semidefinite matrix that accounts for all possible interactions among all four variables simultaneously.

Correlative sparsity exploitation maps this interaction graph directly onto the optimization framework. Formally, this structural property is often captured by the Running Intersection Property (RIP), which ensures that the graph of variable interactions can be decomposed into a tree of smaller, maximal cliques. As shown by Lasserre et al., even when dealing with non-smooth or complex semi-algebraic functions, lifting them into higher dimensions naturally induces this running intersection property, providing a systematic pathway to break down massive optimization problems.

Decomposing the Algebraic Certificates

The core mechanism of sparse polynomial optimization is translating variable independence into decomposed algebraic certificates of positivity (such as Sum-of-Squares or Positivstellensatz representations).

Instead of demanding a single, massive SOS certificate for the entire polynomial, the framework breaks the certificate down into a sum of smaller SOS polynomials. Each smaller polynomial only contains variables belonging to a specific local clique from the interaction graph.

Dense Hierarchy:  [================== Massive Monolithic SDP Matrix ==================]
                                             vs.
Sparse Hierarchy: [ Small Clique SDP 1 ] -> [ Small Clique SDP 2 ] -> [ Small Clique SDP 3 ]

Anh et al. demonstrated this explicitly by developing a sparse version of Reznick's Positivstellensatz. They proved that by restricting certificates to local variable subsets satisfying the Running Intersection Property, the computational complexity drops from exponential in the total number of variables to polynomial in the size of the largest variable subset.

Similarly, Magron and Rocca et al. leveraged sparse Krivine-Stengle representations to drastically accelerate formal verification and roundoff error bounding. By focusing purely on local polynomial structures, their methods achieve massive speedups over dense representations without losing formal, certified guarantees.

Varieties of Structural Sparsity

Depending on the problem domain, correlative sparsity manifests in several distinct patterns, each yielding specialized optimization shortcuts:

1. Chordal Decomposition and Structured Subsets

When the variable interaction graph is chordal (or can be extended to one via chordal completion), the large semidefinite matrix constraint can be decomposed into a collection of smaller, coupled semidefinite constraints. Miller et al. advanced this by decomposing the problem before applying structured subset approximations, achieving the numerical accuracy of full SDPs in a fraction of the time. Zheng et al. bridged the gap between fast, weaker approximations (like diagonally dominant sum-of-squares, or DSOS) and full SOS by exploiting this exact correlative sparsity pattern in large-scale dynamical systems.

2. Basis and Term Reduction

Instead of focusing on variable groups, one can look at the sparsity of the monomials themselves. Yang et al. and Yang et al. introduced basis reduction techniques for geometric perception. By recognizing that individual measurements only interact with local variables, they pruned the mathematical basis, forcing the optimization problem to scale linearly rather than quadratically with the number of data points. Yang et al. extended this to "term sparsity," constructing compact SDP relaxations for outlier-robust perception.

3. Star-Shaped Sparsity

In many machine learning contexts, individual data points interact with a shared global parameter but remain completely independent of each other. Pehlevan et al. exploited this "star-shaped" sparsity pattern to make high-order moment relaxations computationally feasible for large-margin classifiers in hyperbolic spaces, preventing the exponential scaling typically associated with the Lasserre hierarchy.

Real-World Impact

By breaking the curse of dimensionality, sparse polynomial optimization has unlocked global optimality guarantees for complex engineering and scientific applications:

  • Control and Safety Verification: Cerone et al. applied correlative sparsity to robust set-membership estimation, scaling global optimization to systems with hundreds of variables. Miller et al. leveraged the separable structure of distance metrics to compute provable safety margins and distance bounds to unsafe sets for high-dimensional dynamical systems.
  • Computer Vision: In 3D shape reconstruction and geometric perception, algorithms like Shape⋆ and STRIDE (Yang et al.; Yang et al.) use sparse polynomial optimization to maintain absolute optimality certificates, even when up to 90% of the input data consists of outliers.
  • Machine Learning and Quantum Networks: Marecek et al. utilized sparsity-exploiting hierarchies to train fair forecasting models over long temporal sequences with manageable computational overhead, while Klep et al. exploited the sparsity of "state polynomials" to efficiently bound quantum correlations in complex networks.

Key Foundational Work

GloptiPoly 3: moments, optimization and semidefinite programming (2009) — contributed 1 concept elements to this direction.
Positivity and Optimization for Semi-Algebraic Functions (2010) — contributed 1 concept elements to this direction.
On k-Column Sparse Packing Programs (2010) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_correlative_sparsity_exploitation_5e1cd328,
  title = {correlative sparsity exploitation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/correlative-sparsity-exploitation/rdr_5e1cd3285be745239416a50c77fb5dc3},
  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_correlative_sparsity_exploitation_5e1cd328_v1,
  title = {correlative sparsity exploitation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/correlative-sparsity-exploitation/rdr_5e1cd3285be745239416a50c77fb5dc3/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake