# Sum-of-squares optimization without semidefinite programming

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Dec 2017.

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

- [Tractable hierarchies of convex relaxations for polynomial optimization on the nonnegative orthant](https://mlsanity.com/paper/2209.06175/) (2022)
- [A practical, fast method for solving sum-of-squares problems for very large polynomials](https://mlsanity.com/paper/2410.19844/) (2024)

## Abstract (arXiv)

We propose a homogeneous primal-dual interior-point method to solve sum-of-squares optimization problems by combining non-symmetric conic optimization techniques and polynomial interpolation. The approach optimizes directly over the sum-of-squares cone and its dual, circumventing the semidefinite programming (SDP) reformulation which requires a large number of auxiliary variables. As a result, it has substantially lower theoretical time and space complexity than the conventional SDP-based approach. Although our approach avoids the semidefinite programming reformulation, an optimal solution to the semidefinite program can be recovered with little additional effort. Computational results confirm that for problems involving high-degree polynomials, the proposed method is several orders of magnitude faster than semidefinite programming.