Optimization of Polynomials on the Unit Sphere

January 16, 2007
  • Maximum principle
  • 30C80
We consider the problem of computing the maximum absolute value of a real multivariate polynomial on the unit sphere. We identify a class of polynomials for which the problem admits a randomized polynomial time approximation algorithm consisting in computing the maximum absolute value of the restriction of the polynomial onto a random subspace of logarithmic dimension and scaling the result. The characteristic feature of polynomials admitting such an algorithm is that they are "focused": the ratio of their maximum absolute value and the L2 norm is large.