Sum-of-Squares Optimization for Nonlinear System Verification

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

Version 1 of 2518 papers608 conceptsfrozen 2026-10-04

Ensuring that a nonlinear system—like a drone, a robot arm, or a power grid—will always remain safe is a notoriously difficult problem. Traditional methods often rely on discretizing the state space into a grid, but this approach collapses under the "curse of dimensionality" as the number of variables grows.

A powerful alternative has emerged: treating safety and stability as a search for certificates. Instead of checking every possible point in space, researchers use Sum-of-Squares (SOS) optimization to find a single mathematical function that proves the entire system's good behavior.

The Search for Certificates

At the heart of this research is the idea of a "certificate." If you want to prove that a system will never enter a "danger zone," you don't need to simulate every possible path. You only need to find a Barrier Certificate. As Tichakorn Wongpiromsarn, Andrew G. Lamperski, and Andrew Lamperski demonstrate in Automata Theory Meets Barrier Certificates, a barrier certificate is a function that is positive in the danger zone and negative in the safe zone, with dynamics that prevent the system from ever crossing the zero-level set.

Similarly, to prove stability, researchers search for Lyapunov functions—functions that act like "energy" and always decrease as the system evolves. Ian R. Manchester and Jean-Jacques E. Slotine extended this to Control Contraction Metrics (CCMs), which certify that any two trajectories of a nonlinear system will converge toward each other, ensuring robust tracking (Control Contraction Metrics and Universal Stabilizability).

From Polynomials to Semidefinite Programs

The challenge is: how do you find these functions? If the system's dynamics are described by polynomials, we can search for a certificate that is also a polynomial.

A polynomial $p(x)$ is guaranteed to be non-negative if it can be written as a Sum of Squares: $p(x) = \sum f_i(x)^2$. This insight allows us to transform a difficult "for all $x$" constraint into a Semidefinite Program (SDP), a type of convex optimization that can be solved efficiently.

This "Moment/SOS hierarchy" is the engine behind a wide range of applications:

The Scalability Bottleneck

Despite its elegance, SOS optimization faces a significant hurdle: as the number of state variables or the degree of the polynomial increases, the size of the resulting SDP grows combinatorially.

Papers across the field repeatedly highlight this "computational overhead." For example, Milan Korda and Colin Jones note that standard SOS methods often struggle with systems exceeding six to eight states (Controller design and region of attraction estimation for nonlinear dynamical systems).

Breaking the Curse: Sparsity and SDSOS

To move beyond low-dimensional systems, researchers are developing "relaxed" or "structured" versions of SOS:

  1. SDSOS (Scaled Diagonally Dominant Sum of Squares): Amir Ali Ahmadi and Anirudha Majumdar introduced SDSOS to replace expensive SDPs with much faster Second-Order Cone Programs (SOCPs). This allows for real-time safety certificates on complex systems like quadrotors (Some Applications of Polynomial Optimization in Operations Research and Real-Time Decision Making).
  2. Exploiting Sparsity: Many real-world systems are "sparse"—not every variable interacts with every other variable. Ngoc Hoang Anh Mai and Victor Magron have developed sparse versions of polynomial positivity theorems (like Reznick's Positivstellensatz), breaking large problems into smaller, manageable pieces (A Sparse Version of Reznick's Positivstellensatz).
  3. Specialized Toolboxes: To make these methods accessible, tools like SOStab (Stéphane Drobot et al.) automate the generation of stability certificates for specific domains like power systems (SOStab: a Matlab Toolbox for Transient Stability Analysis).

By shifting from point-by-point checking to the global search for polynomial certificates, this research direction provides a rigorous mathematical foundation for the safety of the complex, nonlinear systems that increasingly define our world.

Papers in this version

Showing 60 of 518 papers.

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 1, frozen text):

@misc{lacuna_sum_of_squares_optimization_for_nonlinea_304e0d31_v1,
  title = {Sum-of-Squares Optimization for Nonlinear System Verification},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sum-of-squares-optimization-for-nonlinear-system-verification/rdr_304e0d31470546009fe96b017e520eeb/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}