# DSOS and SDSOS Optimization: More Tractable Alternatives to Sum of Squares and Semidefinite Optimization

arXiv: https://arxiv.org/abs/1706.02586 · HTML: https://mlsanity.com/paper/1706.02586/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Jun 2017.

## Built on by (most cited first, 19 of 19)

- [Shape-constrained Symbolic Regression -- Improving Extrapolation with Prior Knowledge](https://mlsanity.com/paper/2103.15624/) (2021)
- [Evolving Scientific Discovery by Unifying Data and Background Knowledge with AI Hilbert](https://mlsanity.com/paper/2308.09474/) (2023)
- [Risk-averse autonomous systems: A brief history and recent developments from the perspective of optimal control](https://mlsanity.com/paper/2109.08947/) (2021)
- [A Unified View of SDP-based Neural Network Verification through Completely Positive Programming](https://mlsanity.com/paper/2203.03034/) (2022)
- [Synthesizing Stable Reduced-Order Visuomotor Policies for Nonlinear Systems via Sums-of-Squares Optimization](https://mlsanity.com/paper/2304.12405/) (2023)
- [SoS1: O1 and R1-Like Reasoning LLMs are Sum-of-Square Solvers](https://mlsanity.com/paper/2502.20545/) (2025)
- [A Distributionally Robust Approach to Regret Optimal Control using the Wasserstein Distance](https://mlsanity.com/paper/2304.06783/) (2023)
- [Higher-Order Newton Methods with Polynomial Work per Iteration](https://mlsanity.com/paper/2311.06374/) (2023)
- [Gaussian Control Barrier Functions : A Non-Parametric Paradigm to Safety](https://mlsanity.com/paper/2203.15474/) (2022)
- [Stable and Transferable Hyper-Graph Neural Networks](https://mlsanity.com/paper/2211.06513/) (2022)
- [Robust Stability of Neural Network-controlled Nonlinear Systems with Parametric Variability](https://mlsanity.com/paper/2109.05710/) (2021)
- [From LLM-Generated Conjectures to Lean Formalizations: Automated Polynomial Inequality Proving via Sum-of-Squares Certificates](https://mlsanity.com/paper/2605.15445/) (2026)
- [Data Generation Method for Learning a Low-dimensional Safe Region in Safe Reinforcement Learning](https://mlsanity.com/paper/2109.05077/) (2021)
- [Parabolic Relaxation for Quadratically-constrained Quadratic Programming -- Part I: Definitions & Basic Properties](https://mlsanity.com/paper/2208.03622/) (2022)
- [Parabolic Relaxation for Quadratically-constrained Quadratic Programming -- Part II: Theoretical & Computational Results](https://mlsanity.com/paper/2208.03625/) (2022)
- [Tractable hierarchies of convex relaxations for polynomial optimization on the nonnegative orthant](https://mlsanity.com/paper/2209.06175/) (2022)
- [Training Safe Neural Networks with Global SDP Bounds](https://mlsanity.com/paper/2409.09687/) (2024)
- [A practical, fast method for solving sum-of-squares problems for very large polynomials](https://mlsanity.com/paper/2410.19844/) (2024)
- [Certifiable Factor Graph Optimization](https://mlsanity.com/paper/2603.01267/) (2026)

## Abstract (arXiv)

In recent years, optimization theory has been greatly impacted by the advent of sum of squares (SOS) optimization. The reliance of this technique on large-scale semidefinite programs however, has limited the scale of problems to which it can be applied. In this paper, we introduce DSOS and SDSOS optimization as linear programming and second-order cone programming-based alternatives to sum of squares optimization that allow one to trade off computation time with solution quality. These are optimization problems over certain subsets of sum of squares polynomials (or equivalently subsets of positive semidefinite matrices), which can be of interest in general applications of semidefinite programming where scalability is a limitation. We show that some basic theorems from SOS optimization which rely on results from real algebraic geometry are still valid for DSOS and SDSOS optimization. Furthermore, we show with numerical experiments from diverse application areas---polynomial optimization, statistics and machine learning, derivative pricing, and control theory---that with reasonable tradeoffs in accuracy, we can handle problems at scales that are currently significantly beyond the reach of traditional sum of squares approaches. Finally, we provide a review of recent techniques that bridge the gap between our DSOS/SDSOS approach and the SOS approach at the expense of additional running time. The Supplementary Material of the paper introduces an accompanying MATLAB package for DSOS and SDSOS optimization.