Practical Semialgebraic Optimization via Sparse Sample-Based Sum-of-Squares Programming
Abstract
As the importance of semialgebraic optimization grows in engineering, so does the need for scalable sum-of-squares (SOS) methods. Their convex relaxations can guide mixed-integer search and often deliver certified global optima outright. Scaling traditional SOS typically requires hand-crafted bases and redundant constraints, whereas sample-based SOS numerically exploits feasible set geometry to reduce bases and build smaller, often tighter relaxations from black-box evaluations. However, discrete variables can require exponentially many samples, and each sampled equation couples all cliques, destroying correlative sparsity. In this work, we avoid enumeration and slack variables by sampling a tractable variety that contains the feasible set, with multipliers only for the omitted constraints. To recover sparsity, we introduce "separator" polynomials that split the sampled equations into local systems coupled only on clique overlaps. This yields a novel, convergent hierarchy of semidefinite programs (SDPs) with block sizes and sample requirements governed by local interactions rather than total problem size. Lastly, we show how to verify sample sufficiency and prune redundant equations numerically before solving. In robust estimation and motion planning, we obtain certifiably small optimality gaps at scales far beyond those reported for traditional sparse SOS. For example, we solve a truncated least-squares 3D registration problem with 1600 candidate correspondences in under 49 seconds using an off-the-shelf SDP solver on a laptop CPU.
Related
- Real radical branch recovery for second order semialgebraic optimization
- Computing Invariant Reachable Sets through Sum-of-Squares Programming
- PDLP: a practical first-order method for large-scale linear programming
- A Bilevel Neurodynamic Approach for Distributed SCAD-Regularized Sparse Least Squares
- Sparse Sum-of-Squares Layers for Certified Learning
BibTeX
@misc{nezvadovitz2026practical,
title = {{Practical Semialgebraic Optimization via Sparse Sample-Based Sum-of-Squares Programming}},
author = {Jason Nezvadovitz and David M. Rosen},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.07108},
eprint = {2611.07108},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.07108},
}
RIS
TY - UNPB
TI - Practical Semialgebraic Optimization via Sparse Sample-Based Sum-of-Squares Programming
AU - Jason Nezvadovitz
AU - David M. Rosen
PY - 2026
DA - 2026/11/04
PB - arXiv
DO - 10.48550/arxiv.2611.07108
UR - https://arxiv.org/abs/2611.07108
AB - As the importance of semialgebraic optimization grows in engineering, so does the need for scalable sum-of-squares (SOS) methods. Their convex relaxations can guide mixed-integer search and often deliver certified global optima outright. Scaling traditional SOS typically requires hand-crafted bases and redundant constraints, whereas sample-based SOS numerically exploits feasible set geometry to reduce bases and build smaller, often tighter relaxations from black-box evaluations. However, discrete variables can require exponentially many samples, and each sampled equation couples all cliques, destroying correlative sparsity. In this work, we avoid enumeration and slack variables by sampling a tractable variety that contains the feasible set, with multipliers only for the omitted constraints. To recover sparsity, we introduce "separator" polynomials that split the sampled equations into local systems coupled only on clique overlaps. This yields a novel, convergent hierarchy of semidefinite programs (SDPs) with block sizes and sample requirements governed by local interactions rather than total problem size. Lastly, we show how to verify sample sufficiency and prune redundant equations numerically before solving. In robust estimation and motion planning, we obtain certifiably small optimality gaps at scales far beyond those reported for traditional sparse SOS. For example, we solve a truncated least-squares 3D registration problem with 1600 candidate correspondences in under 49 seconds using an off-the-shelf SDP solver on a laptop CPU.
ER -