Complexity Aspects of SDP Relaxations of Polynomial Optimization Problems
Presenter
January 17, 2007
Keywords:
- Polynomial solutions
MSC:
- 35C11
Abstract
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.