title:  NP-Hard Problems, Doubly Nonnegative Relaxations, Facial Reduction, 
and Splitting Methods

We look at doubly nonnegative relaxations for several 
classes of  hard problems.  We present a successful approach
based on using facial reduction and a splitting of variables.
We show that the Slater constraint qualification, 
strict feasibility, fails for many of these problems. Rather 
than resulting in theoretical and numerical difficulties,
we show how to use facial reduction, FR, to
regularize, reduce the dimension of the problem, and provide
a natural splitting of the variables that allows for efficient first order
methods.  In particular we look at applications to
quadratic assignment type problems, 
including problems related to protein folding.



{Main References and Collaborators}


\begin{itemize}
\item
\cite{BurkImWolk:20}
F.~{\crr Burkowski}, J.~{\crr Im}, and H.~Wolkowicz, \emph{A Peaceman-Rachford splitting
  method for the protein side-chain positioning problem}, 2020.

\item
\cite{ForbesVrisWolk:11}
F.~Burkowski, Y-L. {\crr Cheung}, and H.~Wolkowicz, \emph{Efficient use of
  semidefinite programming for selection of rotamers in protein conformations},
  INFORMS J. Comput. \textbf{26} (2014), no.~4, 748--766. 
\item
\cite{GHILW:20}
N.~{\crr Graham}, H.~{\crr Hu}, J.~Im, X.~{\crr Li}, and H.~Wolkowicz, \emph{A restricted dual
  {P}eaceman-{R}achford splitting method for {QAP}}, Tech. report, 
   Waterloo, Ontario, 2020.

\item
\cite{LiPongWolk:19}
X.~Li, T.K. {\crr Pong}, H.~{\crr Sun}, and H.~Wolkowicz, \emph{A strictly contractive
  {P}eaceman-{R}achford splitting method for the doubly nonnegative relaxation
  of the minimum cut problem}, Comput. Optim. Appl. \textbf{78} (2021), no.~3,
  853--891. MR{4221619}
\end{itemize}