A hierarchy of spectral relaxations for polynomial optimization

Understand

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.