TITLE:
Hard Combinatorial Problems, Doubly Nonnegative Relaxations, Facial
Reduction, and Alternating Direction Method of Multipliers

Abstract:

Semi-definite programming, SDP, relaxations have proven to be extremely successful both in theory and practice for many hard combinatorial problems.
The relaxations can be strengthened using cuts, e.g., nonnegativity constraints.

We consider the numerical and theoretical difficulties for these relaxations.