Sum-of-Squares Programming for Nonlinear Safety Verification

90 concepts80 papers1 proposal

Ensuring that a robot, a power grid, or a chemical plant stays within safe operating bounds is a fundamental challenge in engineering. For simple linear systems, we have robust tools to guarantee safety. However, most real-world systems are nonlinear, governed by complex polynomial dynamics where traditional verification methods often fail or become computationally impossible.

Sum-of-Squares (SOS) programming has emerged as a powerful bridge between abstract algebraic geometry and practical control engineering. It allows researchers to transform the difficult task of proving a system's safety into a structured optimization problem that can be solved efficiently by modern computers.

The Core Intuition: From Trajectories to Certificates

To prove a system is safe, you could try to simulate every possible path it might take—an impossible task. A more elegant approach is to find a safety certificate: a mathematical function that acts as a boundary. If you can find a function $B(x)$ that is positive in "unsafe" regions and negative in "safe" regions, and you can prove the system's dynamics never allow $B(x)$ to increase toward zero, you have a formal proof of safety.

The problem is that checking if a general polynomial is always non-negative is NP-hard. As noted in Converse results on existence of sum of squares Lyapunov functions, SOS programming relaxes this hard problem. Instead of asking "is this function positive?", we ask "can this function be written as a sum of squared polynomials?" If a function is a sum of squares (e.g., $f(x) = g_1(x)^2 + g_2(x)^2$), it is obviously non-negative. This algebraic check can be converted into a Semidefinite Program (SDP), a type of convex optimization that solvers can handle reliably.

Synthesizing Safety Boundaries

Researchers use this mechanism to automatically "search" for safety certificates. Xu et al. demonstrate this by synthesizing polynomial barrier functions for semi-autonomous vehicles, ensuring that features like Lane Keeping and Adaptive Cruise Control don't conflict.

This approach is particularly effective for:

  • Complex Geometries: Amice et al. use SOS to compute large, certified collision-free regions for high-dimensional robot arms by converting trigonometric kinematics into polynomials.
  • Distributed Systems: Ahmadi et al. extend these certificates to "barrier functionals" to verify systems governed by partial differential equations, such as fluid flows.
  • Reachability: Korda et al. show how to compute the "Maximum Controlled Invariant set"—the largest possible safe zone—by optimizing polynomial coefficients directly.

Handling Uncertainty and Data

Real systems are rarely perfectly modeled. A significant branch of recent research applies SOS to systems with noise or unknown dynamics. Lavaei et al. introduce Augmented Control Barrier Certificates to provide formal safety guarantees for stochastic systems, bypassing the "curse of dimensionality" that plagues grid-based methods.

When the underlying physics are completely unknown, Nejati et al. show that SOS can be used for data-driven synthesis. By using a single trajectory of data, they formulate safety conditions as bilinear matrix inequalities, allowing for the creation of safety controllers without ever identifying the system model. Similarly, Lefringhausen et al. combine Bayesian inference with SOS to generate certificates that are robust across multiple candidate models of a system.

Scaling to Real-Time Applications

While powerful, standard SOS programming via Semidefinite Programming can be computationally expensive for very large systems. To address this, Ahmadi et al. introduced SDSOS (Scaled Diagonally Dominant Sum of Squares). By relaxing the requirements further into Second Order Cone Programs (SOCPs), they enable real-time safety verification for UAVs and large-scale controllers that were previously untreatable.

Other researchers have focused on reducing complexity through the "theorem of alternatives." Zheng et al. demonstrate that this mathematical mapping can significantly shrink the size of the resulting semidefinite program, making high-dimensional polynomial constraints much easier to process.

Beyond Physical Safety

The utility of SOS extends into software and logic. Feng et al. use polynomial templates and optimization to find loop invariants for probabilistic programs, proving that code will behave as expected even with random inputs. Furthermore, Ramasubramanian et al. combine SOS with game theory to ensure systems satisfy complex Linear Temporal Logic (LTL) requirements even when facing an intelligent adversary.

By turning the qualitative question of "is it safe?" into the quantitative search for a sum-of-squares decomposition, this field provides a rigorous mathematical foundation for the next generation of autonomous and resilient systems.

Key Foundational Work

A Framework for Worst-Case and Stochastic Safety Verification Using Barrier Certificates (2007) — contributed 2 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

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

Latest version (a living page):

@misc{lacuna_sum_of_squares_optimization_0651d3dd,
  title = {sum-of-squares optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sum-of-squares-optimization/rdr_0651d3ddc70c46c1b71225c980a6a2ba},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 2, frozen text):

@misc{lacuna_sum_of_squares_optimization_0651d3dd_v2,
  title = {sum-of-squares optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sum-of-squares-optimization/rdr_0651d3ddc70c46c1b71225c980a6a2ba/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake