%======================= main.tex ===========================================
\documentstyle{slides}
\newtheorem{exam}{Example}
\newtheorem{prop}{Proposition}
\newtheorem{lem}{Lemma}
\newtheorem{thm}{Theorem}
\newtheorem{cor}{Corollary}
\newcommand{\Diag}{{\rm Diag\,}}
\newcommand{\diag}{{\rm diag\,}}
\newcommand{\tr}{{\rm trace\,}}
\newcommand{\trace}{{\rm trace\,}}
\newcommand{\rank}{{\rm rank\,}}
\newcommand{\p}{{\cal P}}
\newcommand{\kvec}{{\rm vec\,}}
\newcommand{\trian}{{\rm trian\,}}
\newcommand{\Trian}{{\rm Trian\,}}
\newcommand{\BoDiag}{{\rm B^0Diag\,}}
\newcommand{\OoDiag}{{\rm O^0Diag\,}}
\newcommand{\arrow}{{\rm arrow\,}}
\newcommand{\Arrow}{{\rm Arrow\,}}
\newcommand{\bodiag}{{\rm b^0diag\,}}
\newcommand{\oodiag}{{\rm o^0diag\,}}
\newcommand{\ck}{{\cal C}_k}
\newcommand{\dk}{{\cal D}_k}
\newcommand{\uu}{{\cal U}}
\newcommand{\uk}{{\cal U}_k}
\newcommand{\vk}{{\cal V}_k}
\newcommand{\wk}{{\cal W}_k}
\newcommand{\wm}{{\cal W}_m}
\newcommand{\w}{{\cal W}}
\newcommand{\wks}{{\cal W}^s_k}
\newcommand{\wms}{{\cal W}^s_m}
\newcommand{\zk}{{\cal Z}_k}
\newcommand{\zks}{{\cal Z}^s_k}
\newcommand{\z}{{\cal Z}}
\newcommand{\n}{{\cal N}}
\newcommand{\ra}{{\cal R}}
\newcommand{\q}{{\cal Q}}
\newcommand{\s}{{\cal S}_n}
\newcommand{\m}{{\cal M}_{n}}
\newcommand{\req}[1]{(\ref{#1})}
\newcommand{\adj}{{\rm adj\,}}
\newcommand{\relint}{{\rm relint\,}}
\pagestyle{plain}
\begin{document}
\blackandwhite{example}
%======================= example.tex
%  the file example.tex must exist - it is empty though
%======================= 
%======================= 
\begin{slide}{}
\begin{center}
{\bf SEMIDEFINITE PROGRAMMING and DISCRETE OPTIMIZATION: A SURVEY}
\end{center}
 
(Linear Programming for the 90's and 00's)

~~\\
Henry Wolkowicz \\
University of Waterloo\\
\rule{155mm}{.1mm}


\end{slide}
\begin{slide}{}
collaborators:

\[
\left.
\begin{array}{l}
\mbox{Abdo Alfakih, Qing Zhao,}\\
 \mbox{and Serge Kruk }
\end{array}
\right\}
 \mbox{Waterloo}\\
\]

 Franz Rendl (Graz)\\
 Panos Pardalos (Florida) 
\end{slide}
\begin{slide}{}
\begin{center}
Discrete Optimization
\end{center}

$\bullet$
Problems where the variables are restricted to discrete values.


$\bullet$
MANY diverse applications: e.g. production planning and
control, scheduling, location-allocation, and portfolio analysis.

$\bullet$
Can prove to be very hard to solve to optimality (NP-hard).

$\bullet$
Currently, most popular techniques use linear programming
relaxations, i.e. LP models are easy to formulate and very efficient
to solve (simplex or interior-point methods).


\end{slide}
\begin{slide}{}
\begin{center}
THEME (Motivation):
\end{center}
\begin{description}
\item
LINEAR:
\begin{description}
\item[$\bullet$]
Linear relaxations have been the major tool used for discrete
optimization problems; this is due to simplicity of the relaxation and
the success in solving the relaxation. Thus, a tractable (nice)
subproblem is used.
\item[$\bullet$]
Various linear relaxations have all been proved equal to the Lagrangian
dual (Lagrangian relaxation) of a linear model (e.g. Adams and Dearing,
1994)
\end{description}
\end{description}
\end{slide}
\begin{slide}{}
\begin{center}
THEME cont...:
\end{center}
\begin{description}
\item
QUADRATIC:
\begin{description}
\item[$\bullet$]
Quadratic models are better than linear models but are too hard to
solve.
\item[$\bullet$]
SDP provides an efficient solution technique for the Lagrangian
relaxation of quadratic models.
\item[$\bullet$]
Many quadratic relaxations have been proved equivalent to the Lagrangian
relaxation, i.e. to the SDP relaxation. From this and the linear case,
we conjecture that we cannot find a {\em better} tractable problem than
the Lagrangian relaxation, i.e. the SDP relaxation for the quadratic
model.
\end{description}
\end{description}

\end{slide}


\begin{slide}{}
quadratic models: e.g.
\[ x_i \in  \{0,1\}  ~ \mbox{iff} ~ x_i^2-x_i=0
\]

How does SDP arise from quadratic models?

From the Lagrangian relaxation.

We get a hidden constraint from the fact that a quadratic
$q(x)=x^tQx+b^tx$ is bounded below only if the Hessian $Q \succeq 0.$
(Otherwise move in the direction of an 'negative' eigenvector.)

\end{slide}
\begin{slide}{}
\begin{center}
Max-Cut Problem
\end{center}
$G=(V,E)$ is an undirected graph with edge set $V$ and weights
$w_{ij}$ on the edges $(v_i,v_j) \in E.$

We want to find the index set $\cal I$ to maximize the weight of the
edges with one end point with index in $\cal I$ and the other in the
complement.
\[
 \begin{array}{c}
    \max ~ \frac 12 \sum_{i<j} w_{ij}(1-x_ix_j),~~~x \in  \{ \pm 1 \}^n.
\end{array}
\]
Equate $x_i=1$ with $i \in \cal I$ and -1 otherwise.  \\

\end{slide}
\begin{slide}{}
Let
\[ q(x) := x^tQx, \]
where $Q$ is the appropriate $n \times n$ symmetric matrix.

An equivalent problem is  the homogeneous
{\em $(\pm 1)$-quadratic programming problem}
\[
\mu^*:=\max ~ q(x),~~~x \in \{ \pm 1 \}^n.
\]

The relaxation $-1 \leq x_i \leq 1$ may not help, i.e. problems with
definiteness.

\end{slide}
\begin{slide}{}
Replace $x \in \{ \pm 1 \}^n$ with constraints $x_i^2=1.$

This equivalent problem is just as hard to solve.
However, we can use Lagrangian relaxation to get an upper bound.
\begin{eqnarray*}
\mu^* 
&=& \max_{x} \min_{\lambda} x^tQx + \sum_i \lambda_i (1-x^2_i)
\\
&\leq& \min_{\lambda} \max_{x} x^tQx + \sum_i \lambda_i (1-x^2_i)
\\
       & =& \min_{\lambda} \max_{x} x^t\left(Q-\Diag (\lambda) \right)x
           + \lambda^te.
\end{eqnarray*}
a tractable convex minimization problem
(Lagrangian dual is always a nice tractable problem.)

\end{slide}
\begin{slide}{}
\begin{eqnarray*}
\mu^* & \leq & \min_{\lambda} \max_{x} x^t\left(Q-\Diag (\lambda) \right)x
           + \lambda^te.
\end{eqnarray*}
{\em hidden semidefinite constraint}
\[ Q - \Diag (\lambda) \preceq 0  ~\mbox{(negative semidefinite)}\]

\[
\begin{array}{cc}
\min & \left<\lambda ,e\right>=\lambda^t e \\
\mbox{subject to} & \Diag (\lambda) \succeq Q,
\end{array}
\]

just as for  LP 

(note:
adjoint operator $\Diag^*(Y)=\diag(Y),$ the diagonal vector of the matrix $Y,$
and the semidefinite cone is self polar)

dual program:
\[
\begin{array}{cc}
\max & \left<Q ,X\right>=\tr QX \\
\mbox{subject to} & \diag(X) = e\\
      & X \succeq 0.
\end{array}
\]
\end{slide}
\begin{slide}{}
SDP relaxation of MC:
\[
\begin{array}{cc}
\max & \tr QX \\
\mbox{subject to} & \diag(X) = e\\
      & X \succeq 0.
\end{array}
\]
note: $x_i^2=1$ is equivalent to
\[  \diag(xx^t) = e  \]
and $x^tQx= \tr Qxx^t.$ 

Relax the rank-1 condition on $X$ to get the SDP relaxation.
\end{slide}
\begin{slide}{}

In general:\\
consider the quadratic functions:
\[q_i(y)=\frac 12 y^tQ_iy+y^tb_i + c_i,~y\in \Re^n \]

and the quadratic constrained quadratic program:
\[ {\bf (QQP)}
\begin{array}{ccc}
    q^*=  & \min &q_0(y) \\
 &  \mbox{s.t.} & q_i(y)=0\\
     &&  i=1,\ldots m
    \end{array}
\]


\end{slide}
\begin{slide}{}
Lagrangian (multipliers $x_i$):\\
\[ 
\begin{array}{rcl}
  L(y,x) &=& 
  q_0(y)+
  \sum_{i=1}^m x_i(q_i(y))   \\
  && \frac 12 y^t (Q_0 -\sum_{i=1}^m x_iQ_i)y  ~\mbox{quadratic}\\
 &&   +y^t(b_0 -\sum_{i=1}^m x_ib_i)~\mbox{linear}\\
   &&+ (c_0 -\sum_{i=1}^m x_ic_i)~\mbox{constant}
\end{array}
\]

\[q^*=\min_y \max_x L(y,x) \geq d^* = \max_x \min_y L(y,x).
\]
homogenize linear term
\[ y_0y^t(b_0 -\sum_{i=1}^m x_ib_i), ~~ y_0^2=1.  \]
\end{slide}
\begin{slide}{}
\[
\begin{array}{cccc}
  d^*=\\
  =\max_x \min_y &L(y,x)\\
  = \max_x \min\limits_{y_0^2=1}& \frac 12 y^t (Q_0 -\sum_{i=1}^m x_iQ_i)y 
                            ~~~(+ty_0^2) \\
 &   +y_0y^t(b_0 -\sum_{i=1}^m x_ib_i)\\
 &+ (c_0 -\sum_{i=1}^m x_ic_i)
                            ~~~(-t)
\end{array}
\]

The hidden semidefinite constraint yields the semidefinite program, 
i.e. we get\\
 $A: \Re^{m+1} \rightarrow {\cal S}_{n+1}$
\[ 
B=\left( \begin{array}{cc}
      0 & b_0^t \\ b_0 &Q_0
   \end{array}  \right),
A \left( \begin{array}{c}
      t \\ x
   \end{array}  \right)
   = \left[ \begin{array}{cc}
        -t &  \sum_{i=1}^m x_ib_i^t \\
      \sum_{i=1}^m x_ib_i  & \sum_{i=1}^m x_i Q_i
        \end{array}   \right]
\]

\[
B-A \left( \begin{array}{c}
      t \\ x
   \end{array}  \right)
 \succeq 0.
\]
\end{slide}
\begin{slide}{}
The dual program is equivalent to the SDP (with $c_0=0$)
\[ {\bf (D)}
\begin{array}{ccc}
    d^*=  & \mbox{sup} & -t -\sum_{i=1}^m x_ic_i \\
 &  \mbox{s.t.} & A\left( \begin{array}{c}
      t \\ x
   \end{array}  \right)
 \preceq B\\
  && x \in \Re^m, t \in \Re
    \end{array}
\]
and  the dual of the dual
\[ {\bf (DD)}
\begin{array}{ccc}
    d^*=& \inf &\tr BU \\
 &  \mbox{s.t.} & A^*U = \left( \begin{array}{c}
      -1 \\ -c
   \end{array}  \right) \\
  && U \succeq 0.
    \end{array}
\]
\end{slide}


\begin{slide}{}
\begin{center}
Semidefinite Programming\\
 looks just like\\
Linear Programming
\end{center}
\[ {\bf (P)}
\begin{array}{cccc}
    p^*=  & \mbox{sup} &c^tx \\
 &  \mbox{s.t.} & Ax \preceq b&(b-Ax \in \p)\\
  && x \in \Re^m
    \end{array}
\]
$\preceq$ denotes the L{\"{o}}wner partial order
\[ A : \Re^m \rightarrow {\cal S}_n, 
\]
where ${\cal S}_n$ is the set of
$n \times n ~\mbox{symmetric matrices}$

$\p$,
~~ the cone of positive semidefinite matrices
\begin{center}
replaces
\end{center}
$\Re^n_+,$ ~~the nonnegative orthant

\end{slide}
\begin{slide}{}
Equivalently:

\[ {\bf (P)}
\begin{array}{cccc}
    p^*=  & \mbox{sup} &\sum_j c_j x_j \\
 &  \mbox{s.t.} & b- \sum_j x_j A_j \succeq 0\\
  && x \in \Re^m
    \end{array}
\]

where

$b=b^t, A_j=A_j^t$ are symmetric matrices

\end{slide}
\begin{slide}{}
\[ {\bf (P)}
\begin{array}{cccc}
    p^*=  & \mbox{sup} &c^tx \\
 &  \mbox{s.t.} & Ax \preceq b&(b-Ax \in \p)\\
  && x \in \Re^m
    \end{array}
\]
The Lagrangian for this problem is:
\[ L(x,U) := c^tx + \left<U,b-Ax \right>
\]
where
\[U=U^t ~\mbox{Lagrange multiplier}\]
\[  \left<U,b-Ax \right> = \tr U(b-Ax) \]

We can rewrite the Lagrangian as
\[ L(x,U) = \left< U,b\right> +x^t(c-A^*U)
\]
($A^*$~adjoint of $A$ - like transpose)


\end{slide}
\[ 
\begin{array}{cccc}
\left<U,Ax \right> &=& \tr U \sum_j x_j A_j \\
                   &=& \tr  \sum_j x_j UA_j \\
                   &=& x^t (\tr  UA_j) \\
                   &=& x^t A^* U\\
     &=& \left<x,A^*U \right> \\
\end{array}
\]


\begin{slide}{}
\begin{center}
{\bf DUALITY}
\end{center}
The Lagrangian $L$ is a payoff function 
 from player $U$ to player $X$\\ 
\[ L(x,U) := c^tx + \left<U,b-Ax \right>
\]

The primal and dual programs are derived
 from the optimal (worst case) strategy for each player


\end{slide}
\begin{slide}{}
\[ L(x,U) := c^tx + \left<U,b-Ax \right>
\]
Player $X$ wants to maximize the payoff over all possible strategies of
player $U$
\[p^* = \max_x\min_{U \succeq 0}L(x,U) 
\]

hidden constraint $b-Ax \succeq 0$
yields the primal

\[ {\bf (P)}
\begin{array}{ccc}
    p^*=  & \mbox{sup} &c^tx \\
 &  \mbox{s.t.} & Ax \preceq b\\
  && x \in \Re^m
    \end{array}
\]
\end{slide}
\begin{slide}{}
\[ L(x,U) = \left< U,b\right> +x^t(c-A^*U)
\]
Player $U$ wants to minimize the payoff over all possible strategies of
player $X$
\[d^* =\min_{U \succeq 0} \max_x L(x,U) 
\]

hidden constraint $c-A^*U=0$ yields the dual

\[ {\bf (D)}
\begin{array}{ccc}
    d^*=& \inf &\tr bU \\
 &  \mbox{s.t.} & A^*U = c \\
  && U \succeq 0.
    \end{array}
\]
\end{slide}
\begin{slide}{}
Characterization of optimality for the\\
   dual pair $x,U$
 \[ 
\begin{array}{cc} 
    Ax \preceq b & \mbox{primal feasibility}\\
~\\
    A^*U = c  & \mbox{dual feasibility}\\
~\\
    U \circ (Ax -b) = 0e & \mbox{complementary slackness}
\end{array}
\]
\[
    U \circ (Ax -b) = \mu e ~~~~~ \mbox{perturbed}
\]

Forms the basis for:\\ ~~\\
primal simplex method\\
dual simplex method\\
interior point methods
\end{slide}
\begin{slide}{}
\underline{Example}

If the primal is
\[ {\bf (P)}
\begin{array}{ccc}
    p^*=  & \mbox{sup} &x_2 \\
 &  \mbox{s. t.} & 
\left[ \begin{array}{ccc}
       x_2 & 0 & 0\\
       0 & x_1 & x_2\\
       0 & x_2 & 0
       \end{array}  \right]
\preceq 
   \left[ \begin{array}{ccc}    
       1 & 0 & 0\\
       0 & 0 & 0\\
       0 & 0 & 0
       \end{array}  \right] 
    \end{array}
\]
i.e.
\[c = (0,1)^t, ~Ax = x_1 
      \left[ \begin{array}{ccc}
       0 & 0 & 0\\
       0 & 1 & 0\\
       0 & 0 & 0
       \end{array}  \right]
   + x_2
 \left[ \begin{array}{ccc}
       1 & 0 & 0\\
       0 & 0 & 1 \\
       0 & 1  & 0
       \end{array}  \right]
\]
then the dual is
\[ {\bf (D)}
\begin{array}{cccccc}
    d^*=& \inf &\tr U_{11}\\
 &  \mbox{s. t.} & U_{22}&=&0  \\
 &   & U_{11}+2U_{23}&=&1  \\
  && U \succeq 0.
    \end{array}
\]
Then $p^*=0 < d^*=1.$ DUALITY GAP!!!
\end{slide}
\begin{slide}{}

{\bf Why use SEMIDEFINITE PROGRAMMING?}

Quadratic approximations are better than linear approximations. 

{\bf Quadratic approximations are too hard to solve!}

But, we
can solve relaxations of
quadratic approximations efficiently using semidefinite programming.
\end{slide}
\begin{slide}{}
\begin{center}
APPLICATIONS
\end{center}
Finding bounds and good feasible solutions
for hard discrete optimization problems such as:
\begin{enumerate}
\item
max-cut;
\item
graph partitioning;
\item
quadratic assignment problem;
\item
set partitioning
\item
Maximum Satisfiability Problem
\item
Feedback Vertex Set Problem
\item
max-clique.
\end{enumerate}
\end{slide}
\begin{slide}{}
Unconstrained and constrained optimization techniques, e.g.
\begin{enumerate}
\item
quasi-Newton updates that preserve positive definiteness.
\item
Trust region algorithms for large scale minimization.
\item
Extended SQP techniques for constrained minimization.
\end{enumerate}
\end{slide}
\begin{slide}{}
Others:
\begin{enumerate}
\item
Partial Hermitian matrix completion problems.
\item
Min-max eigenvalue problems, matrix norm minimization, eigenvalue
localization.
\item
logarithmic Chebychev approximation, structural optimization, pattern
separation by ellipsoids, statistics (educational testing problem),
control and systems theory
\end{enumerate}
\end{slide}
\begin{slide}{}
{\bf QUADRATIC ASSIGNMENT PROBLEM}

{\bf QAP} 

\[
\begin{array}{ccc}
\mu^*:= &\min\limits_{X \in \Pi} & \tr AXBX^t - 2CX^t \\
\end{array}
\]
~\\
~\\
$A, B$ and $C$ are real $n\times n$ matrices\\
$\Pi$ is the set of permutation matrices.

~~\\
~~\\
~~\\
Rewrite as
\[
(QAP_E)~~
\begin{array}{ccl}
\mu^*:=
&\min & \tr AXBX^t - 2CX^t \\
&\mbox{~s.t.~} & XX^t = I, \left( X^tX = I\right) \\
         && \left(Xe = X^te = e \right)\\
        && X_{ij}^2 - X_{ij} = 0,~~ \forall i,j.
\end{array}
\]

ignore $Xe = X^te = e$ for now
\end{slide}
\begin{slide}{}
Find the semidefinite relaxation by taking the dual of the Lagrangian
dual.

-----------------------------------------------

We first add the (0,1)-constraints to the objective function using
Lagrange multipliers $W_{ij}$
\[
\begin{array}{ccc}
\mu_{\cal O} &=& \min\limits_{XX^t=X^tX = I} \max\limits_W
\tr AXBX^t - 2CX^t \\
       &&+ \sum_{ij} W_{ij}(X_{ij}^2 - X_{ij}).
\end{array}
\]
~~\\
~~\\
We now homogenize the objective function by multiplying by a constrained
scalar $x_0$
\[
\begin{array}{cc}
\mu_{\cal O} \geq \mu_R = \\
\max\limits_W  \min\limits_{\stackrel{XX^t=X^tX=I}{x_0^2 =1}}&
\tr \left[ AXBX^t + \right.\\ 
  &  \left.W(X \circ X)^t
    -x_0(2C+ W)X^t \right].
\end{array}
\]

\end{slide}
\begin{slide}{}
Introducing a Lagrange multiplier $w_0$ for the constraint on $x_0$ and
Lagrange multipliers $S_b$ for $XX^t=I$ and $S_o$ for $X^tX=I$ we
get
\[
\begin{array}{ll}
\mu_{\cal O} \geq \mu_R := \\
   \max\limits_W  \min\limits_{X,~x_0} &
\tr \left[ AXBX^t +  W(X \circ X)^t + w_0 x_0^2 \right. \\
         & \left. + S_b XX^t + S_o X^tX
\right] \\ 
& - \tr x_0(2C+ W)X^t\\
 &  - w_0 - \tr S_b - \tr S_o.
\end{array}
\]

We have grouped the quadratic, linear, and constant terms together.
We now define $x:= \kvec X$, $y^t:=(x_0,x^t)$ and $w^t:= (w_0,\kvec W^t)$ and 
get
\[
\begin{array}{ll}
\mu_R = \\
\max\limits_W \min\limits_{y} & y^t \left[ L_Q+Arrow(w)+\BoDiag(S_b)+
                 \right. \\
& \left. \OoDiag(S_o)  \right] y \\
& - w_0 - \tr S_b - \tr S_o
\end{array}
\]
\end{slide}
\begin{slide}{}
We used the $(n^2+1) \times (n^2+1)$ matrix
\[
L_Q := \left[ \begin{array}{cc}
0 & - \kvec (C)^t \\
-\kvec (C) & B \otimes A
\end{array} \right],
\]
and the (interesting) linear operators
\[
\Arrow (w) := \left[ \begin{array}{cc}
w_0 & - \frac 12 w_{1:n^2}^t \\
-\frac 12 w_{1:n^2} & \Diag \left(w_{1:n^2}\right)
\end{array} \right],
\]
\[
\BoDiag (S) := \left[
\begin{array}{cc}
0 & 0 \\
0 & I \otimes S_b
\end{array}
\right]
\]
and
\[
\OoDiag (S) := \left[
\begin{array}{cc}
0 & 0 \\
0 & S_o \otimes I
\end{array}
\right].
\]

\end{slide}
\begin{slide}{}
The hidden semidefinite constraint yields the equivalent SDP:
\[
(D_{\cal O})~~
\begin{array}{llc}
\max & - w_0 - \tr S_b - \tr S_o \\
\mbox{~s.t.~}& L_Q +\Arrow(w) + \\
        & \BoDiag(S_b) + \OoDiag(S_o) \succeq 0,
    \end{array}
\]
The dual of this dual yields the semidefinite relaxation.

$Y \succeq 0$ is $(n^2+1) \times ( n^2+1)$\\
     the dual matrix variable

\[
(SDP_{\cal O})~~
\begin{array}{cllcll}
\min &\tr L_QY \\
\mbox{~s.t.~}
  & \bodiag(Y) = I && \oodiag(Y) = I \\
  & \arrow(Y) = e_{0} && Y \succeq 0
\end{array}
\]
\end{slide}
\begin{slide}{}
adjoint operators are:
\[\arrow (Y) := \diag (Y) - (0, (Y_{0,1:n^2})^t. \]

$$ \bodiag(Y) := \sum\limits_{k=1}^n Y_{(k-1)n+1:kn,(k-1)n+1:kn} $$

$$ [\oodiag(Y)]_{ij} := \tr Y_{(i-1)n+1:in,(j-1)n+1:jn}  $$

\end{slide}
\begin{slide}{}
\begin{center}
{\bf Direct Approach to SDP Relaxation}
\end{center}

Let\\
 $X \in \Pi_n$ be a permutation matrix\\
$x=\kvec(X),~ c=\kvec(C).$
\begin{eqnarray*}
  q(X) &=& \tr AXBX^t - 2CX^t \\
       &=& x^t (B \otimes A) x -2c^tx \\
       &=& \trace xx^t (B \otimes A)  -2c^tx \\
       &=& \trace L_Q Y_X,
\end{eqnarray*}
where $L_Q$ is as above and
\[
Y_X := \left[
\begin{array}{cc}
1& x^t \\
x & xx^t
\end{array}
\right].
\]
\end{slide}
\begin{slide}{}
For a permutation matrix X:
\[  \diag(X_{:i}X_{:j}^T)=X_{:i} \circ X_{:j} = 0, ~ \mbox{if}~ i \neq j,
\]
and
\[ X_{i:} \circ X_{j:} = 0, ~ \mbox{if}~ i \neq j,
\]
i.e. the diagonal of the off-diagonal blocks are identically zero and
the off-diagonal of the diagonal blocks are identically zero. These are
exactly the zeros of the barycenter $\hat{Y}.$

\end{slide}
\begin{slide}{}
For
\[J \subset \{(i,j):1\le i,j \le n^{2}+1\}\]
\[ \label{eq:gangster}
({\mathcal G}_{J}(Y))_{ij}:=\left\{\begin{array}{ll}
                      Y_{ij} & \mbox{if}~ (i,j) \in J\\
                      0     & \mbox{otherwise.}
                    \end{array}
                    \right.
\]
the operator 
${\mathcal G}_{J}:  {\mathcal S}_{n^2+1} \rightarrow {\mathcal S}_{n^2+1}$ is
called the {\em Gangster} operator (shoots holes in the matrix).
\end{slide}
\begin{slide}{}
 We can now get
a very simple projected relaxation.

\[
(QAP_{R2})~~~~
\begin{array}{lll}
\mu_{R2} := & \min & \tr (\hat{V}^TL_Q\hat{V})R   \\
 & \mbox{~s.t.}
 & {\mathcal G}_{\bar{J}}(\hat{V}R\hat{V}^T) = 0  \\
 &&  R \succeq 0.  
\end{array}
\]

The dual problem is
\[
\begin{array}{lll}
\mu_{R2} := & \max & -Y_{00} \\
& \mbox{~s.t.}
&\hat{V}^{T}(L_{Q}+{\mathcal G}^{*}_{\bar{J}}(Y))\hat{V} \succeq 0.
\end{array}
\]
\end{slide}
\begin{slide}{}
Problems from QABLIB

The first column
indicates the problem instance looked at and its size. 

nugxx refers
to the Nugent example of size xx.

The columns give the optimal solution, the Gilmore-Lawler bound
GLB, the projection
or elimination bound ELI,
 EVB3 iterated elimination,
and GAN semidefinite bound with gangster operator.

\end{slide}
\begin{slide}{}

\begin{center}
\begin{tabular}{|l|rrrrr|} \hline
   & OPT  &  GLB &  ELI &   EVB3 &  GAN\\
\hline
\hline
  nug05 &   50 &   50 &   47 &   50 &  50    \\
  nug06 &   86 &   84 &   69 &   70 &  86    \\
  nug07 &  148 &  137 &  125 &  130 &  144   \\
  nug08 &  214 &  186 &  167 &  174 &  204   \\
  nug12 &  578 &  493 &  472 &  498 &  534   \\
  nug15 & 1150 &  963 &  973 & 1002 &  1075  \\
  nug20 & 2570 & 2057 & 2196 & 2286 &  2385  \\
  nug30 & 6124 & 4539 & 5266 & 5450 &  5648  \\
\hline\hline
 car10ga& 4954 & 3586 & 4079 & 4541 &  4853 \\
 car10gb& 8082 & 6139 & 7211 & 7617 &  7960 \\
 car10gc& 8649 & 7030 & 7837 & 8233 &  8561 \\
 car10gd& 8843 & 6840 & 8006 & 8364 &  8666 \\
 car10ge& 9571 & 7627 & 8672 & 8987 &  9349 \\
\hline
\end{tabular}
\end{center}
Numerical Results for lower bounds

GAN refers to the ''gangster'' operator with the SDP bound


\end{slide}
\begin{slide}{}
\begin{center}
{\bf Adding Generic Inequality Constraints}
\end{center}

From the relaxation for the (0,1)-constraints of the original problem:
$$
y_{ij} \geq 0 \mbox{~~since~~} x_i x_j \geq 0.
$$
We also get so called triangle inequalities 
\[
y_{ij}+y_{ik}+y_{jk}-\left( y_{ii}+y_{jj}+y_{kk}\right)+1 \geq 0
\]
and
\[
y_{ij}-y_{ik}-y_{jk}+y_{kk} \geq 0
\]

\end{slide}
\begin{slide}{}
Therefore the following is a strengthened semidefinite relaxation of QAP
\[
(SDP)~~
\begin{array}{llll}
  \min & \tr L_Q Y &&\\
  \mbox{~s.t.~}
       & \bodiag(Y)   = I  &&  \oodiag(Y)  = I \\
       & T_0 Y T_0^t  = E  &&  T_0 Y_{\cdot,0}  = e \\
       & \arrow(Y) = e_{0} &&  \trian(Y) \geq -g \\
       &  Y \succeq 0 & \\
\end{array}
\]
~~\\
{\bf BUT}

Slater's condition always fails!!!

How do we start a primal-dual {\bf INTERIOR} point method???
\end{slide}
\begin{slide}{}
\begin{center}
{\bf Graph Equi-Partitioning}\\
(special case of QAP)
\end{center}
$k$ and $m$  given integers\\
 $G$ an edgeweighted undirected graph on $n :=km$ nodes, 
given by its adjacency matrix $A$.\\
($a_{ij}$ weight of edge $i  \leftrightarrow j$)

a $k$-partition of $V(G)$ is a partitioning of $V(G)$ into $k$ subsets
$(S_1, \ldots, S_k)$ of equal cardinality.

the columns of $Y \in \Re^{n \times k}$ are the characteristic vectors
for the sets $S_k$
$${\cal F}_k := \lbrace Y: Yu_k = u_n, 
   ~Y^tu_n= mu_k, y_{ij} \in \lbrace 0,1
\rbrace \rbrace$$

$L := \diag(Au_n) - A$ ~~{\em Laplacian matrix associated to $G$}.

\end{slide}
\begin{slide}{}
weight of the edges of $G$, cut by some $k$-partition $Y  \in {\cal F}_k$,
$$\frac{1}{2} \tr Y^tLY$$

THE PROBLEM:

$$(k - GP)
\begin{array}{ccc}
 \min & \frac{1}{2} \tr Y^tLY &(=\tr LYY^t)\\
    \mbox{subject to} & Y \in {\cal F}_k
\end{array}
$$

\end{slide}
\begin{slide}{}

$${\cal T}_k  := \lbrace X: X = YY^t   
       \mbox{~for some~}  Y \in {\cal F}_k \rbrace$$

$${\cal E}_m  :=\lbrace X: X=X^t, \diag(X)=u_n, Xu_n = mu_n \rbrace$$

note $X \in {\cal T}_k$ implies that the only
eigenvalues of $X$ are 0 and $m$\\
 Therefore $mI -X \succeq 0$


THE SDP RELAXATION:
$$
\min \lbrace \frac{1}{2} \tr LX : X \in {\cal E}_m,~X \succeq 0,~
mI- X \succeq 0 \rbrace.$$

We can add further constraints, e.g. $X \geq 0$ and other 'polyhedral
constraints'
\end{slide}
\begin{slide}{}
Numerics (Thanks to Stefan Karisch)
\begin{center}
\begin{tabular}{ | r | r | r | r | } \hline
$n$  & $|E|$ & cut & ${\cal E}_m \cap {\cal P}$ \\ \hline
36 & 305   & 119 & 112  \\
60 & 903   & 367 & 355  \\
84 & 1762  & 747 & 717  \\
108 & 2897 & 1252 & 1206 \\
132 & 4325 & 1901 & 1833 \\
\hline
\end{tabular}
\end{center}
Partitioning random graphs into 2 components of equal size.
The first two columns describe the size of the graphs, column 3 contains
the best equipartition found, column 4  contains the lower bound.

\end{slide}
\begin{slide}{}
\begin{center}
\begin{tabular}{ | r | r | r | r | r |} \hline
$n$  &  cut & ${\cal E}_m \cap {\cal P}$ &
${\cal E}_m \cap {\cal P}\cap{\cal N}$ & sign constr. \\ \hline
36 &   160 & 149.1 & 154.3 & 120 \\
60 &   506 & 472.6 & 484.1 & 223 \\
84 &   1014 & 955.1 & 972.8 & 349 \\
108 &  1693 & 1607.7 & 1630.8 & 469 \\
132 &  2563 & 2443.7 & 2469.3 & 554 \\
\hline
\end{tabular}
\end{center}
Partitioning random graphs into $k=3$ components of equal size.
The first  column identifies the graph, column 2 contains
the best 3-partition found, columns 3 and 4 contain lower bounds from
semidefinite relaxations, the last column indicates the number of
nonnegativity constraints $x_{ij} \geq 0$ used, to insure $X \geq 0.$

\end{slide}
\begin{slide}{}
\begin{center}
\begin{tabular}{ | r | r | r | r | r |} \hline
$n$  &  cut & ${\cal E}_m \cap {\cal P}$ &
${\cal E}_m \cap {\cal P}\cap{\cal N}$ & sign constr. \\ \hline
36 &   186 & 167.6 & 179.7 & 211 \\
60 &   585 & 531.7 & 556.1 & 405 \\
84 &   1165 & 1074.6 & 1112.7 & 596 \\
108 &  1935 & 1808.7 & 1860.9 & 859 \\
132 &  2915 & 2749.2 & 2810.4 & 993 \\
\hline
\end{tabular}
\end{center}
Partitioning random graphs into $k=4$ components of equal size.
The first  column identifies the graph, column 2 contains
the best 4-partition found, columns 3 and 4 contain lower bounds from
semidefinite relaxations, the last column indicates the number of
nonnegativity constraints $x_{ij} \geq 0$ used, to insure $X \geq 0.$
\end{slide}

\begin{slide}{}
URLs:\\
Workshop on
Semidefinite Programming and Interior-Point Approaches for
Combinatorial Optimization Problems\\

http://orion.uwaterloo.ca/\\
  \~{ }hwolkowi/fields.d/readme.html

other URLs:\\
http://www.zib.de/helmberg/semidef.html \\

 


\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\end{document}

