%======================= example.tex
% slide 1
\begin{slide}{}
\begin{center}
{\bf A RECIPE FOR BEST SEMIDEFINITE RELAXATION
FOR (0,1)-QUADRATIC PROGRAMMING}

Henry Wolkowicz \\
Department of Combinatorics and Optimization \\
University of Waterloo\\
(anonymous ftp at orion.uwaterloo.ca)
\end{center}

~\\
~\\
~\\
~\\
work with:\\
 Svata Poljak (University Passau)\\
 Franz Rendl (University of Graz)

\end{slide}
% slide 2
\begin{slide}{}
\begin{center}
  {\bf OUTLINE}
\end{center}
\begin{itemize}
\item
Hidden semidefinite constraints in quadratic programming
\item
Best relaxations for (0,1)-quadratic programming (with linear
constraints)
\item 
Applications:
\begin{itemize}
\item
Quadratic Assignment Problem
\item
Graph Partitioning Problem 
\item
Max-clique Problem
\end{itemize}
\end{itemize}
\end{slide}
%slide 3
\begin{slide}{}
{\bf (-1,+1)-quadratic programming problem}

\[
(P)~~~\mu^*:=\max ~ q(x),~~~x \in F \cap S,
\]

where:\\
 $F = \{-1,1\}^n, ~S \subset \Re^n,$ and $F \cap S \neq \emptyset$

quadratic objective function
\[ q(x) := x^tQx-2c^tx, \]

$Q$ $n \times n$ symmetric matrix,  $c \in \Re^n$

\end{slide}
%slide 4
\begin{slide}{}
\begin{center}
{\bf EXAMPLES}
\end{center}

 {\em Quadratic Assignment Problem}\\
(in the trace formulation)
\[
(QAP)~~~ \begin{array}{c}
    \max_{X\in\Pi} ~ q(X):=\tr(AXB - 2C)X^t
  \end{array}
\]
~~\\
~~\\
~~\\
{\em Max-Cut Problem}
\[
(MC)~~~  \begin{array}{c}
    \max ~ \frac 12 \sum_{i<j} w_{ij}(1-x_ix_j),~~~x \in F
\end{array}
\]

\end{slide}
%slide 5
\begin{slide}{}
HIDDEN SEMIDEFINITE CONSTRAINTS

Trust Region Subproblem (TRS)
\begin{eqnarray*} 
\mu^*&=&\min\limits_x q(x) ~\mbox{s.t.}~ x^tx = s^2 ~(\leq s^2)\\
     &=&\min\limits_x \max\limits_\lambda L(x,\lambda) \\
    & \geq & \max\limits_\lambda \min\limits_x L(x,\lambda)\\
    & =& \max\limits_{Q-\lambda \succeq 0} \min\limits_x L(x,\lambda)\\
    & =& \max\limits_{Q-\lambda \succeq 0} h(\lambda)\\
   &=&  \mu^*
\end{eqnarray*}
where
\[ x_\lambda = (Q-\lambda I)^\dagger c \]
\[ h(\lambda) = L(x_,\lambda) = -c^t(Q-\lambda I)^\dagger c +\lambda
s^2\]
---------------\\
:nonconvex objective but min-max = max-min\\
:hidden convexity provides the hidden convex dual program
\end{slide}
%slide 6
\begin{slide}{}
RELAXATIONS OF (-1,1)-QUADRATIC PROGRAMMING

use perturbations 
\[q_u(x) :=  q(x) + x^t \Diag (u) x - u^te\]

Relaxation 0:

\[f_0 (u) := \max_x q_u(x)
\]
\begin{eqnarray*}
\mu^* \leq B_0 &:=& \min_{u^te=0}  f_0(u)=\min_u  f_0(u)\\
   &=& \min_{Q+\Diag(u) \preceq 0}  f_0(u)
\end{eqnarray*}
This bound equals the Lagrangian dual of the original (0,1)-quadratic
program in the following form - $u_i$ are Lagrange multipliers
\[ \min q(x) \mbox{~s.t.}~x_i^2=1,~\forall i
\]
\end{slide}
%slide 7
\begin{slide}{}
Relaxation 1 -  sphere of radius $\sqrt{n}$
\[ f_1(u):= \max_{|| x ||^2 =n} ~ q_u(x)
\]
\[
 \mu^* \leq B_1 :=\min_{u^te=0} f_1(u)=\min_u f_1(u)
\]
\begin{eqnarray*}
B_1 &=& \min_u \max_{x^tx=n} q_u(x)\\
 & = & \min_{u,\lambda} \max_x q_u(x) + \lambda(x^tx-n) \\
 & = & \min_{v^te=0} \max_x q_v(x),~ \mbox{with~} v=u+\lambda e \\
 & = & B_0
\end{eqnarray*}
\end{slide}
%slide 8
\begin{slide}{}
Relaxation 2 -  Unit Box
\[ f_1(u):= \max\limits_{| x _i|\leq =1} ~ q_u(x)
\]
\[
 \mu^* \leq B_2 :=\min\limits_{Q+\Diag(u) \preceq 0} f_2(u)=\min\limits_u f_2(u)
\]
\begin{eqnarray*}
B_2 &=& \min\limits_{u} \max\limits_{x^2_i \leq 1} q_u(x)\\
    &=& \min\limits_{u} \min\limits_{\lambda \geq 0}
         \max_{x} q_u(x) + \sum_i \lambda_i(1-x_i^2)\\
 & = & B_0 ~~\mbox{after~~} v=u-\lambda
\end{eqnarray*}
again
\end{slide}
%slide 9
\begin{slide}{}
Relaxation $1^c$ -  Homogenization, \\
 -~~~~~~~~~~~~~~~~~-sphere  radius $=\sqrt{n+1}$
\[Q^c:= \left[ \begin{array}{cc}
   0 &  - c^t \\
  - c &Q    \end{array}  \right]
\]
\[ q^c_u(y) :=   y^t( Q^c+\diag(u))y-u^te
\]
\begin{eqnarray*}
f_1^c(u) &:=& \max_{||y||^2=n+1} q^c_u(y)\\
   &=& (n+1) \lambda_{\max} (Q^c + \diag (u) ) - u^te
\end{eqnarray*}
\[
 \mu^* \leq B_1^c := \min_{u^te=0} f_1^c(u) = \min_{u} f_1^c(u)
\]
\begin{eqnarray*}
B_1^c  &=& \min_v \max_{y^ty = n+1} q^c_v (y)= \min_v \max_y q^c_v (y)\\
    &=& \min_{u,u_0} \max_{x,x_0}  u_0(x_0^2-1) + x^t(Q+\Diag(u))x\\
&& ~~~~~~~~~~~~-2x_0c^tx - u^te \\
    &=& \min_{u} \max_{x,x^2_0=1}   x^t(Q+\Diag(u))x -2x_0c^tx - u^te \\
    &=& B_0
\end{eqnarray*}
again

Similarly for $B_2^c$
\end{slide}
%slide 10
\begin{slide}{}
Relaxation $3$ -  semidefinite SDP ($c=0$)
\[ q(x) =   x^t Qx = \tr Qxx^t
\]
with $Y=xx^t$
\[
\begin{array}{ccc}
       B_3 :=&\max &\tr QY \\
 &  \mbox{~subject to~} &\diag(Y) = e \\
        && Y \succeq 0
    \end{array}
\]
The dual is
\[
\begin{array}{ccc}
      B_3 :=& \mbox{minimize~} & y^te \\
 &  \mbox{~subject to~} &Q - \Diag(y) \preceq 0
    \end{array}
\]
-------------\\
\[Q-\Diag(y-\frac{e^ty}n e) \preceq \frac{e^ty}n I\]
with $w=y-\frac{e^ty}n e$ and $z=\frac{e^ty}n$
\[
\begin{array}{ccc}
      B_3 :=& \mbox{minimize~} & nz \\
 &  \mbox{~subject to~} &Q - \Diag(w) \preceq zI \\
    &  &  w^te=0\\
=& B_1^c
    \end{array}
\]
\end{slide}
%slide 11
\begin{slide}{}
All the bounds are equal to the Lagrangian relaxation of the equivalent
quadratically constrained program.

The SDP relaxation is the dual of the Lagrangian dual.

What happens if we allow more general perturbations?
\end{slide}
%slide 12
\begin{slide}{}
More General Perturbations

\[ q_{V,d}(x) := x^t(Q+V)x + (c+d)^tx
\]
\begin{thm}
Suppose that
\[
q_{V,d}(x) \geq q(x),~~~ \forall x \in F.\]
Then
\[
\begin{array}{c}
V=P+U,~\mbox{with~} P \succeq 0,~ U ~ \mbox{is diagonal,}\\
   ~~~~~~\mbox{and}~\tr
U =0.
\end{array}
\]
Moreover, there exists a diagonal matrix $W,$ with $\tr W = 0,$ such
that
\[
\max_x q_{V,d}(x) \geq \max_x q_{W,0}(x).
\]
\hspace*{4.5in}  $\Box$
\end{thm}

Therefore, we need only consider diagonal perturbations, i.e. we have
the best quadratic approximation - by duality we have the best SDP
relaxation.

\end{slide}
%slide 13
\begin{slide}{}
General Case - allow linear constraints

Equivalent quadratic program
\[
\begin{array}{ccc}
\mu^*=
&\max & q(x)=x^tQx-2c^tx\\
 &  \mbox{~subject to~} &||Ax-b||^2=0\\
        && x_{i}^2 = 1,~~ \forall i.
    \end{array}
\]
{\bf RECIPE for SDP relaxation}
\begin{enumerate}
\item
Replace (P) by the equivalent quadratic program
\item
Take Lagrangian dual - get  min-max of Lagrangian
\item
Homogenize Lagrangian
\item
Use hidden semidefinite constraint to get SDP
\item
Take Lagrangian dual of SDP to get desired SDP
\end{enumerate}
\end{slide}
%slide 14
\begin{slide}{}
The Lagrangian relaxation of the equivalent quadratic program yields the
best possible quadratic bound.
\begin{thm}
Suppose that the set $S$ is described by linear equalities as above.
Suppose that the general perturbed
quadratic function $q_{V,d}$ is defined as above and
\[
q_{V,d,\lambda} : = q_{V,d} - \lambda ||Ax -b||^2.
\]
If
\[
q_{V,d}(x) \geq q(x),~~~ \forall x \in F
     \cap S,
\]
then there exists $\lambda,W$ such that
\[
\begin{array}{c}
q_{V,d} \equiv q_{W,b,\lambda},\\
W=P+U,~\mbox{with~} P \succeq 0,\\
 U ~ \mbox{is diagonal,},~\tr U =0,\\
\mbox{and} ~ b=d - 2 \lambda A^t b.
\end{array}
\]
Moreover, there exists a diagonal $Z$ with $\tr Z =  0$ such that
\[
\max_x q_{V,d}(x) \geq \max_x q_{Z,0,\lambda}(x).\]
\hspace*{4.5in}  $\Box$
\end{thm}
\end{slide}
%slide 15
\begin{slide}{}
QUADRATIC ASSIGNMENT PROBLEM
\[
\begin{array}{cc}
\max &q(X) =\tr (AXB - 2C)X^t \\
  \mbox{~subject to~} &XX^t = I \\
        & X_{ij}^2 - X_{ij} = 0,~~ \forall i,j.
    \end{array}
\]
Apply the recipe:
\[
L_Q := \left[
\begin{array}{cc}
0 & - \kvec (C)^t \\
-\kvec (C) & B \otimes A
\end{array}
\right],
\]
\[
\BoDiag (\Lambda) := \left[
\begin{array}{cc}
0 & 0 \\
0 & I \otimes \Lambda
\end{array}
\right].
\]
and $\bodiag = \BoDiag^*$ adjoint operator\\
---------------\\
Then SPD relaxation is:
\[
\begin{array}{ccc}
       \max &\tr L_QY \\
   \mbox{~subject to~}
         & \diag(Y) = (1,Y_{0,1:n^2})^t \\
         & \bodiag(Y) = I \\
        & Y \succeq 0.
    \end{array}
\]
\end{slide}
%slide 16
\begin{slide}{}
GRAPH PARTITIONING
\[
\begin{array}{cc}
 w(E_{uncut})=\max& \frac{1}{2} \tr X^{t}AX\\
\mbox{subject to} &Xe_k = e_n\\
&X^te_n = m\\
&X_{ij} \in \{0,1\},~\forall ij,
\end{array}
\]
\[
\begin{array}{cc}
 \max& \frac{1}{2} \tr X^{t}AX\\
\mbox{subject to} &||Xe_k-e_n||^2 + ||X^te_n-m||^2 =0\\
&X_{ij}^2-X_{ij} = 0,~\forall ij.
\end{array}
\]
\[
L_A := \left[
\begin{array}{cc}
0 & 0 \\
0 & \frac 12 I \otimes A
\end{array}
\right],
\]
\[  v = \kvec e_n m^t,\]
\[
L_\alpha := \left[
\begin{array}{cc}
0 & -(e+v)^t \\
-(e+v) & (e_ke_k^tI \otimes I +I \otimes  e_ne_n^t)
\end{array}
\right].
\]
The SDP is:
\[
\begin{array}{ccc}
       \max &\tr L_AY \\
   \mbox{~subject to~}
         & \diag(Y) = (1,Y_{0,1:n})^t \\
         & \trace Y L_\alpha = 0\\
        & Y \succeq 0.
    \end{array}
\]
\end{slide}
%slide 17
\begin{slide}{}
MAX-CLIQUE and STABLE SET

$\omega(G)$ size of largest clique in graph G

$x$ is indicator vector for largest clique
\[
\begin{array}{ccl}
\omega(G)=&\max& x^tx\\
&   \mbox{~subject to~}& x_ix_j=0, ~ \mbox{if~} ij \notin E,~i \neq j\\
&  & x_i^2-x_i =0, ~ \forall i.
    \end{array}
\]
\[
L_A := \left[
\begin{array}{cc}
0 & 0 \\
0 & I
\end{array}
\right],
\]
----------------\\
SDP relaxation is
\[
\begin{array}{ccc}
       \max &\tr L_AY \\
   \mbox{~subject to~}
         & \diag(Y) = (1,Y_{0,1:n})^t \\
         & Y_{ij}=0,~\forall ij \notin E\\
        & Y \succeq 0.
    \end{array}
\]
\end{slide}
%slide 3
%\begin{slide}{}
%\end{slide}
%slide 3
%\begin{slide}{}
%\end{slide}
