Complexity Aspects of SDP Relaxations of Polynomial Optimization Problems

January 17, 2007
  • Polynomial solutions
  • 35C11
We discuss complexity aspects of Lasserre's sequence of SDP relaxations of a given polynomial optimization problem. As a special example where a lot is known, we consider the MAXCUT problem. The following topics should be covered: - the moment problem and convergence to unique minimizers, - speed of convergence to the optimal value, - Scheiderers result on stability and the moment problem, - the approximability result of Goemans and Williamson for MAXCUT, and - the inapproximability result of Khot, Kindler, Mossel and O'Donnell for MAXCUT.