Scaling Sum of Squares Optimization

411 concepts317 papers1 proposal

Polynomial optimization provides a rigorous mathematical framework for solving complex non-convex problems across robotics, control theory, and machine learning. By using the Sum-of-Squares (SOS) hierarchy, researchers can transform notoriously difficult global optimization problems into convex Semidefinite Programs (SDPs). This approach allows us to find certifiable global optima, map out safe regions of attraction for nonlinear systems, and verify the safety of cyber-physical architectures.

However, this mathematical elegance hides a severe computational trap: the curse of dimensionality. As systems grow in size or require higher-fidelity approximations, the underlying optimization problems hit a "memory wall," rendering standard SOS techniques intractable. Understanding why this scaling bottleneck occurs—and how modern research circumvents it—is essential to deploying these formal verification tools in the real world.


The Core Mechanism: From Nonnegativity to Matrices

To understand why SOS optimization struggles to scale, we must first look at what it is trying to achieve. At its core, SOS optimization answers a fundamental question: Is a given polynomial $p(x)$ non-negative for all possible values of $x$?

Directly verifying global nonnegativity is an NP-hard problem. The SOS framework bypasses this by searching for a sufficient condition: if a polynomial can be written as a sum of squared polynomials, it must be non-negative.

$$p(x) = \sum_i q_i(x)^2$$

Algebraically, finding these constituent polynomials $q_i(x)$ is equivalent to finding a positive semidefinite matrix $Q$ (denoted as $Q \succeq 0$) that satisfies:

$$p(x) = z(x)^T Q z(x)$$

where $z(x)$ is a vector containing the basis of all monomials up to degree $d$. This formulation turns an intractable non-negativity check into a standard semidefinite program that can be solved using interior-point methods.


The Monomial Explosion: Why SOS Fails to Scale

The scalability bottleneck stems directly from the size of the monomial vector $z(x)$. If we are dealing with a system of $n$ variables and want to check a polynomial of degree $2d$, the number of elements in $z(x)$ is given by the combinatorial formula:

$$\binom{n + d}{d}$$

Because the decision matrix $Q$ must index every pair of these monomials, its dimensions scale quadratically with this choice. As highlighted by Mohamadreza Ahmadi et al. 2017 and Luyao Niu et al. 2022, this combinatorial explosion severely restricts the application of SOS to high-dimensional systems.

Consider how this plays out across two axes:

1. The State-Space Bottleneck ($n$)

In applications like robotics or power grids, $n$ represents the number of state variables (e.g., joint positions, velocities, or voltages). As He Yin et al. 2020 and Stéphane Drobot et al. 2024 note, even moderately sized models can easily overwhelm standard hardware. For instance, a 12-degree-of-freedom robot manipulator analyzed by Alexandre Amice et al. 2022 requires massive offline processing times because the state space is simply too large for dense matrix representations.

2. The Degree Explosion Trap ($d$)

Even if the number of state variables $n$ is small, the degree $d$ required to certify a property can independently break the solver. As Amir Ali Ahmadi et al. 2017 demonstrate, a system might possess a simple underlying structure, but proving its stability might require a high-degree Lyapunov certificate. This "degree explosion" forces the optimization variables to expand exponentially, hitting what Chaojie Li 2024 terms the "memory wall"—where the problem size exceeds the RAM capacity of standard computing infrastructure.


Pathways to Scalability

To bring the guarantees of polynomial optimization to high-dimensional real-world systems, researchers have developed techniques to bypass the dense matrix requirements of traditional SDPs. These methods generally fall into two categories: exploiting structural sparsity and relaxing the underlying mathematical cones.

                  [Polynomial Optimization Problem]
                                 |
         +-----------------------+-----------------------+
         |                                               |
 [Exploit Sparsity]                             [Alternative Cones]
         |                                               |
         ├─ Term Sparsity (TSSOS)                        ├─ SDSOS (SOCP Relaxation)
         └─ Correlative Sparsity                         └─ SONC (Circuit Polynomials)

Exploiting Sparsity

Real-world polynomials rarely feature every possible interaction between every variable; they are often sparse. Researchers exploit this by breaking a single massive semidefinite constraint into a collection of smaller, coupled constraints.

  • Term Sparsity: Jie Wang et al. 2021 introduced the TSSOS framework, which analyzes the specific monomial terms present in the input polynomial. By constructing chordal extensions of the underlying adjacency graphs, they eliminate unnecessary zero-entries in the large $Q$ matrix, drastically reducing computational overhead.
  • Correlative Sparsity: When variables only interact within specific subsets (a property formalized via the Running Intersection Property), the problem can be decomposed. Ngoc Hoang Anh et al. 2023 leveraged this to develop a sparse version of Reznick's Positivstellensatz, proving that large-scale global optimization can be solved in smaller, modular blocks without sacrificing global optimality guarantees.

Alternative Cones: SDSOS and SONC

Instead of trying to solve the massive SDP more efficiently, another approach changes the optimization problem itself by replacing the semidefinite cone with more tractable alternatives.

  • SDSOS (Scaled Diagonally Dominant Sum of Squares): Amir Ali Ahmadi et al. 2015 proposed restricting the search to a subset of positive semidefinite matrices: those that are diagonally dominant. This restriction allows the problem to be framed as a Second-Order Cone Program (SOCP). While SOCPs provide slightly more conservative bounds than full SDPs, they can be solved orders of magnitude faster, enabling real-time control synthesis for complex systems like quadrotors.
  • SONC (Sums of Nonnegative Circuit Polynomials): Adam Kurpisz 2018 explored the use of circuit polynomials as an alternative certificate over the boolean hypercube. SONC certificates bypass the monomial basis entirely by focusing on the support of the polynomial, allowing for short, low-degree certificates where traditional SOS would require a high-degree representation.

By shifting from dense, monolithic global certificates to sparse decompositions and alternative algebraic cones, modern optimization frameworks continue to push the boundaries of how large a certifiably safe system can be.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

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

Latest version (a living page):

@misc{lacuna_semidefinite_programming_scalability_cur_304e0d31,
  title = {semidefinite programming scalability (curse of dimensionality in polynomial optimization)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/semidefinite-programming-scalability-curse-of-dimensionality-in-polynomial/rdr_304e0d31470546009fe96b017e520eeb},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_semidefinite_programming_scalability_cur_304e0d31_v2,
  title = {semidefinite programming scalability (curse of dimensionality in polynomial optimization)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/semidefinite-programming-scalability-curse-of-dimensionality-in-polynomial/rdr_304e0d31470546009fe96b017e520eeb/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake