# A hierarchy of spectral relaxations for polynomial optimization

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Jul 2020.

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

- [An Inexact Projected Gradient Method with Rounding and Lifting by Nonlinear Programming for Solving Rank-One Semidefinite Relaxation of Polynomial Optimization](https://mlsanity.com/paper/2105.14033/) (2021)
- [Stability Analysis of Recurrent Neural Networks by IQC with Copositive Mutipliers](https://mlsanity.com/paper/2202.04592/) (2022)
- [Sparse Polynomial Optimization: Theory and Practice](https://mlsanity.com/paper/2208.11158/) (2022)
- [Tractable hierarchies of convex relaxations for polynomial optimization on the nonnegative orthant](https://mlsanity.com/paper/2209.06175/) (2022)

## Abstract (arXiv)

We show that (i) any constrained polynomial optimization problem (POP) has an equivalent formulation on a variety contained in an Euclidean sphere and (ii) the resulting semidefinite relaxations in the moment-SOS hierarchy have the constant trace property (CTP) for the involved matrices. We then exploit the CTP to avoid solving the semidefinite relaxations via interior-point methods and rather use ad-hoc spectral methods that minimize the largest eigenvalue of a matrix pencil. Convergence to the optimal value of the semidefinite relaxation is guaranteed. As a result we obtain a hierarchy of nonsmooth "spectral relaxations" of the initial POP. Efficiency and robustness of this spectral hierarchy is tested against several equality constrained POPs on a sphere as well as on a sample of randomly generated quadratically constrained quadratic problems (QCQPs).