Proposed title and abstract as of Nov. 2019, subject to change.

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.
This is particularly true for the Max-Cut problem, MC, where a
polynomial-time approximation algorithm with ratio $\alpha \approx
0.878$ is given by a method of Goemans and Williamson using
SDP. Moreover, algorithms based on SDP
and other tools have been very effective and problems with
dimension in the thousands have been solved to optimality.

In contrast, the quadratic assignment problem, QAP, is an NP-hard
problem where dimensions bigger than $30$ are still considered hard.
This is similarly true for many graph partitioning, GP, problems.
SDP and in particular, the  doubly nonnegative, DNN, relaxation have
been successful in providing strong bounds.

We look at semidefinite relaxations for these hard problems and some
features that they have in common. We present a successful approach for all
of them. The problems we look at are the: second lifting for MC, and the
DNN relaxations for both the QAP and the GP.
We show that the Slater constraint qualification, strict feasibility,
fails for all these problems. Rather than resulting in theoretical and
numerical difficulties we show how to use facial reduction, FR, to
regularize while reducing the dimension of the problem. 

Finally, the large size of the relaxations makes it difficult to use in
interior-point type methods. We see that FR fits perfectly with an
alternating directions method of multipliers, ADMM. We show 
empirically that solving these relaxations generically solves the
original hard combinatorial problems.