Polynomial Optimization for Formal Safety Verification

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

Version 1 of 274 papers84 conceptsfrozen 2026-10-04

In the design of autonomous systems—from UAVs to power converters—the most critical question is: "Can we guarantee this system will never enter an unsafe state?" Traditionally, answering this required either exhaustive simulation (which can never prove safety) or state-space discretization (which suffers from the "curse of dimensionality").

A powerful alternative has emerged that treats safety verification not as a search through trajectories, but as a convex optimization problem. By using Sum-of-Squares (SOS) programming, researchers can automatically synthesize mathematical "certificates" that prove a system is safe without ever needing to solve its underlying differential equations.

The Intuition: Safety as a Landscape

Imagine a robot moving through a state space. Some regions are "safe" (the road) and others are "unsafe" (a ditch). To prove the robot is safe, we don't need to track every possible path it might take. Instead, we can look for a Barrier Certificate.

A Barrier Certificate is a scalar function $B(x)$ that acts like a topographical map. We want to find a function where:

  1. $B(x) \leq 0$ for all initial starting positions.
  2. $B(x) > 0$ for all unsafe regions.
  3. The value of $B(x)$ never increases along the system's trajectories.

If such a function exists, it acts as an impenetrable fence. Since the robot starts in a region where $B \leq 0$ and the value of $B$ can only go down or stay the same, it can never reach the unsafe region where $B > 0$. Han Wang and Antonis Papachristodoulou demonstrate in Safety Verification and Controller Synthesis for Systems with Input Constraints that these certificates can be significantly less conservative than traditional methods, allowing for larger safe operating regions.

The Mechanism: Sum-of-Squares Programming

The challenge is finding this function $B(x)$. For a general nonlinear system, checking if a function is globally non-negative is an NP-hard problem. This is where Sum-of-Squares (SOS) optimization provides a breakthrough.

If a polynomial can be written as a sum of squared polynomials (e.g., $p(x) = f_1(x)^2 + f_2(x)^2$), it is obviously non-negative. While not every non-negative polynomial is a sum of squares, the set of SOS polynomials is much easier to work with. Crucially, checking if a polynomial is SOS can be cast as a Semidefinite Program (SDP), a type of convex optimization that can be solved efficiently.

Amir Ali Ahmadi and Anirudha Majumdar in Some Applications of Polynomial Optimization in Operations Research and Real-Time Decision Making show that by relaxing complex polynomial constraints into SOS or even simpler SDSOS (Scaled Diagonally Dominant Sum of Squares) forms, we can generate safety certificates for UAVs in real-time.

Scaling to Complex Systems

This framework is remarkably flexible, extending far beyond simple robot motion:

From Verification to Synthesis

The ultimate goal is not just to verify safety, but to design controllers that ensure it. By treating the controller coefficients as variables in the SOS program, we can jointly search for a control law and its safety proof.

Milan Korda and Didier Henrion pioneered a "primal-dual" approach in Convex Computation of the Maximum Controlled Invariant Set For Polynomial Control Systems. Instead of guessing a Lyapunov function, they use "occupation measures" to characterize the largest possible safe set, transforming the search for a controller into a linear program over measures, which is then solved via the SOS hierarchy.

This shift—from manual "guess-and-check" of safety functions to automated synthesis via convex optimization—represents a fundamental change in how we build reliable autonomous systems. As Jared Miller and Mario Sznaier suggest in Quantifying the Safety of Trajectories using Peak-Minimizing Control, this hierarchy allows us to calculate increasingly tight bounds on safety, providing a rigorous numerical path toward absolute certainty in machine behavior.

Papers in this version

Showing 60 of 74 papers.

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

@misc{lacuna_polynomial_optimization_for_formal_safet_0651d3dd_v1,
  title = {Polynomial Optimization for Formal Safety Verification},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/polynomial-optimization-for-formal-safety-verification/rdr_0651d3ddc70c46c1b71225c980a6a2ba/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}