Computing Invariant Reachable Sets through Sum-of-Squares Programming
Abstract
Funnels, time-varying invariant sets around nominal trajectories, certify that a closed-loop system tracks its plan, and can be composed into verified motion plans. Their computation by sum-of-squares (SOS) programming is well established in formulation but not in practice: the result depends on implementation choices such as the initial guess, Lyapunov function normalization, and termination rule, which the literature documents only briefly. This paper presents a self-contained treatment of SOS-based funnel computation, implemented in the open-source package computeSOSFunnels. We propose a minimum-volume formulation with inlet and outlet constraints under which funnels with coinciding nominal endpoints compose by construction. Numerical experiments on a unicycle, with timing studies on a cart-pole and a 12-state quadrotor, characterize the pipeline: infeasible initial guesses are partly decidable before solving, the certificate shows no violations among 39,000 boundary samples per funnel under the true dynamics, and constructing the semidefinite program, not solving it, dominates computation time.
Related
- Practical Semialgebraic Optimization via Sparse Sample-Based Sum-of-Squares Programming
- Integer linear programming based methods for computing the maximum chordal subgraph of an arbitrary graph
- Computing Equilibria in Integer Programming Games with Shared Constraints
- Unitary-Invariant Decomposition of Reducible Total Least Squares Core Problems
- Low-Thrust Trajectory Optimization with Quantum Computing and Sequential Convex Programming
BibTeX
@misc{jaffar2026computing,
title = {{Computing Invariant Reachable Sets through Sum-of-Squares Programming}},
author = {Mohamed Khalid M Jaffar},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.04325},
eprint = {2611.04325},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.04325},
}
RIS
TY - UNPB
TI - Computing Invariant Reachable Sets through Sum-of-Squares Programming
AU - Mohamed Khalid M Jaffar
PY - 2026
DA - 2026/11/03
PB - arXiv
DO - 10.48550/arxiv.2611.04325
UR - https://arxiv.org/abs/2611.04325
AB - Funnels, time-varying invariant sets around nominal trajectories, certify that a closed-loop system tracks its plan, and can be composed into verified motion plans. Their computation by sum-of-squares (SOS) programming is well established in formulation but not in practice: the result depends on implementation choices such as the initial guess, Lyapunov function normalization, and termination rule, which the literature documents only briefly. This paper presents a self-contained treatment of SOS-based funnel computation, implemented in the open-source package computeSOSFunnels. We propose a minimum-volume formulation with inlet and outlet constraints under which funnels with coinciding nominal endpoints compose by construction. Numerical experiments on a unicycle, with timing studies on a cart-pole and a 12-state quadrotor, characterize the pipeline: infeasible initial guesses are partly decidable before solving, the certificate shows no violations among 39,000 boundary samples per funnel under the true dynamics, and constructing the semidefinite program, not solving it, dominates computation time.
ER -