Convergence Rates for Polynomial Optimization on Set Products

Abstract. We consider polynomial optimization problems on Cartesian products of basic compact semialgebraic sets. The solution of such problems can be approximated as closely as desired by hierarchies of semidefinite programming relaxations, based on classical sums of squares certificates due to Putinar and Schmüdgen. When the feasible set is the bisphere, i.e., the Cartesian product of two unit spheres, we show that the hierarchies based on the Schmüdgen/Putinar-type certificates converge to the global minimum of the objective polynomial at a rate in [Formula: see text], where [Formula: see text] is the relaxation order. Our proof is based on the polynomial kernel method. We extend this result to arbitrary sphere products and give a general recipe to obtain convergence rates for polynomial optimization over products of distinct sets. Eventually, we rely on our results for the bisphere to analyze the speed of convergence of a semidefinite programming hierarchy approximating the order 2 quantum Wasserstein distance.