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:
- Reachability Analysis: He Yin, Peter Seiler, and colleagues use SOS to compute "safety bubbles" or reachable sets for uncertain systems (Reachability Analysis Using Dissipation Inequalities For Nonlinear Dynamical Systems).
- Inverse Optimal Control: Edouard Pauwels, Jean B. Lasserre, and Didier Henrion use SOS to recover the underlying cost functions that govern observed behavior (Linear Conic Optimization for Inverse Optimal Control).
- Quantum Systems: Denys I. Bondar and Jakub Marecek apply these hierarchies to identify the dynamics of open quantum systems from data (Recovering models of open quantum systems from data via polynomial optimization).
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:
- 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).
- 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).
- 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.