Abstract
We present a general method for bounding the accuracy of semi-definite programming relaxations for polynomial optimization. As an example, we apply our mehod to obtain accuracy bounds for optimization over the hypersphere and the boolean cube. The method allows the explicit recovery of approximate representing measures for moment matrix relaxations. Our techniques are loosely inspired by methods used in quantum optics.
Joint work with Andrew Doherty and Pablo Parrilo.