# Simplification Methods for Sum-of-Squares Programs

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Mar 2013.

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

- [Sum-of-Squares Programming for Ma-Trudinger-Wang Regularity of Optimal Transport Maps](https://mlsanity.com/paper/2412.13372/) (2024)

## Abstract (arXiv)

A sum-of-squares is a polynomial that can be expressed as a sum of squares of other polynomials. Determining if a sum-of-squares decomposition exists for a given polynomial is equivalent to a linear matrix inequality feasibility problem. The computation required to solve the feasibility problem depends on the number of monomials used in the decomposition. The Newton polytope is a method to prune unnecessary monomials from the decomposition. This method requires the construction of a convex hull and this can be time consuming for polynomials with many terms. This paper presents a new algorithm for removing monomials based on a simple property of positive semidefinite matrices. It returns a set of monomials that is never larger than the set returned by the Newton polytope method and, for some polynomials, is a strictly smaller set. Moreover, the algorithm takes significantly less computation than the convex hull construction. This algorithm is then extended to a more general simplification method for sum-of-squares programming.