Back to Search Start Over

Exponential convergence of sum-of-squares hierarchies for trigonometric polynomials

Authors :
Bach, Francis
Rudi, Alessandro
Source :
SIAM Journal on Optimization, In press
Publication Year :
2022

Abstract

We consider the unconstrained optimization of multivariate trigonometric polynomials by the sum-of-squares hierarchy of lower bounds. We first show a convergence rate of $O(1/s^2)$ for the relaxation with degree $s$ without any assumption on the trigonometric polynomial to minimize. Second, when the polynomial has a finite number of global minimizers with invertible Hessians at these minimizers, we show an exponential convergence rate with explicit constants. Our results also apply to minimizing regular multivariate polynomials on the hypercube.

Details

Database :
arXiv
Journal :
SIAM Journal on Optimization, In press
Publication Type :
Report
Accession number :
edsarx.2211.04889
Document Type :
Working Paper