% file is s17.tex
{\bf $\pm 1$ QUADRATIC PROGRAMMING}
\begin{itemize}
\item
\[
\begin{array}{c}
~~~(P)~~~\mu^*:=\max ~ q(x):=x^tQx+c^tx,\\
        x \in F := \{-1,1\}^n,
\end{array}
\]
$Q$ $n \times n$ symmetric matrix, $c \in \Re^n$.
\item
Relaxed Problem - $K \supset F$
\[
\begin{array}{c}
(RP)~~~f(u) = \max_{x \in K} q_u(x):=\\
     x^t(Q - \diag(u))x + u^te +c^tx,
\end{array}
\]
\item
Solve Tractable Problem 
\[ B:= \min_{u \in L} f(u) \]
\item
Upper Bound 
\[\mu^* \leq B \]
\end{itemize}