Sum of Squares Programming for Nonlinear System Verification

This direction is merged into another direction: semidefinite programming scalability (curse of dimensionality in polynomial optimization). Its last version stays readable and citable here.

Version 1 of 126 papers29 conceptsfrozen 2026-10-04

Proving that a dynamical system is stable or safe is a fundamental challenge in engineering. For simple linear systems, we have straightforward tools like eigenvalues. But for nonlinear systems—those governing everything from autonomous drones to power grids—proving stability usually requires finding a Lyapunov function: a mathematical "energy" function that always decreases as the system evolves.

The problem is that finding these functions is notoriously difficult. Historically, it required manual trial and error or restrictive assumptions. Sum of Squares (SOS) programming changes this by transforming the search for these certificates into a tractable convex optimization problem.

The Core Challenge: Global Non-negativity

To prove a system is stable, we often need to guarantee that a specific polynomial $V(x)$ (our candidate Lyapunov function) is non-negative for all possible states $x$. As Antonis Papachristodoulou and James Anderson explain in On validation and invalidation of biological models, verifying the non-negativity of a general polynomial is an NP-hard problem. We cannot simply check every point, and the algebraic structure of high-dimensional polynomials is too complex for standard solvers.

The SOS Relaxation

The "aha!" moment of this research direction is a clever relaxation: while checking if a polynomial is non-negative is hard, checking if it can be written as a Sum of Squares of other polynomials is much easier.

If $V(x) = \sum f_i(x)^2$, then $V(x)$ is obviously non-negative for all $x$. As Amir Ali Ahmadi and Pablo Parrilo demonstrate in Sum of squares certificates for stability of planar, homogeneous, and switched systems, this requirement is a "relaxation" because every SOS polynomial is non-negative, though not every non-negative polynomial is necessarily an SOS.

The breakthrough is that the search for an SOS decomposition can be cast as a Semidefinite Program (SDP). In an SDP, we optimize over symmetric matrices that are "positive semidefinite" (all eigenvalues $\ge 0$). This is a convex problem, meaning we can solve it efficiently and reliably using standard numerical tools.

From Stability to Safety

This framework extends far beyond simple stability. Researchers have applied SOS programming to several critical verification tasks:

Scaling to Real-World Complexity

A common critique of formal methods is that they don't scale. However, recent advancements in software and theory have made SOS practical for complex systems. Antonis Papachristodoulou and his team developed SOSTOOLS, a toolbox that allows researchers to solve nonlinear stability problems with dozens of variables in seconds.

The reach of SOS has even extended into modern machine learning and complex physics. Amin Abyaneh and Hsiu-Chin Lin showed in Learning Lyapunov-Stable Polynomial Dynamical Systems Through Imitation that robots can learn motion policies that are guaranteed to be stable by embedding SOS constraints directly into the learning process. Similarly, Aditya Gahlawat and Matthew M. Peet have applied these techniques to Partial Differential Equations (PDEs), proving stability for systems with infinite-dimensional states.

By bridging the gap between abstract algebraic geometry and practical control engineering, SOS programming provides a rigorous, algorithmic way to trust the nonlinear systems that underpin our modern world.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_sum_of_squares_programming_for_nonlinear_9d512f69,
  title = {Sum of Squares Programming for Nonlinear System Verification},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sum-of-squares-programming-for-nonlinear-system-verification/rdr_9d512f69abc44b2eaa9cff8e5730242a},
  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_programming_for_nonlinear_9d512f69_v1,
  title = {Sum of Squares Programming for Nonlinear System Verification},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sum-of-squares-programming-for-nonlinear-system-verification/rdr_9d512f69abc44b2eaa9cff8e5730242a/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}