%======================= 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 APPLICATIONS OF SEMIDEFINITE PROGRAMMING}
\end{center}
 
(Linear Programming for the 90's and 00's)

~~\\
~~\\
~~\\
~~\\
~~\\
~~\\
Henry Wolkowicz \\
University of Waterloo

\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, ~n \times n ~\mbox{symmetric matrices}
\]

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

\end{slide}
\begin{slide}{}
payoff function player $X$ to player $Y$
\[ L(x,U) := \left< U,b\right> +x^t(c-A^*U)
\]
The dual is obtained from the optimal strategy of the competing player
\[p^* = \max_x\min_{U \succeq 0}L(x,U) \leq d^*
        =\min_{U \succeq 0} \max_x L(x,U) 
\]
The 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}
\]
for 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}{}
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}
\]
then the dual is
\[ {\bf (D)}
\begin{array}{ccc}
    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.$
\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}
\begin{enumerate}
\item
Finding bounds and good feasible solutions
for hard combinatorial problems such as:
\begin{enumerate}
\item
max-cut;
\item
graph partitioning;
\item
quadratic assignment problem;
\item
max-clique.
\end{enumerate}
\item
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}
\item
Partial Hermitian matrix completion problems.
\item
Min-max eigenvalue problems, matrix norm minimization, eigenvalue
localization.
\end{enumerate}
\end{slide}
\begin{slide}{}
\begin{center}
Max-Cut Problem
\end{center}
\[
 \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.  \\
Let
\[ q(x) := x^tQx, \]
where $Q$ is an $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.
\]
Replace $x \in \{ \pm 1 \}^n$ constraints $x_i^2=1.$

Note that for
\[ X=xx^t,  \]
\[ X \succeq 0,~ \diag (X) = e, ~q(x)=\tr XQ.  \] 
Relax the rank-1 condition on $X$ to get SDP.
\end{slide}
\begin{slide}{}
How does SDP arise from quadratic approximations?

Let 
\[q_i(y)=\frac 12 y^tQ_iy+y^tb_i + c_i,~y\in \Re^n \]
\[ {\bf (QQP)}
\begin{array}{ccc}
    q^*=  & \min &q_0(y) \\
 &  \mbox{s.t.} & q_i(y)=0\\
     &&  i=1,\ldots m
    \end{array}
\]
Lagrangian:\\
\[ 
\begin{array}{ccc}
  L(y,x) &=& \frac 12 y^t (Q_0 -\sum_{i=1}^m x_iQ_i)y  \\
 &&   +y^t(b_0 -\sum_{i=1}^m x_ib_i)\\
   &&+ (c_0 -\sum_{i=1}^m x_ic_i)
\end{array}
\]

\[q^*=\min_y \max_x L(y,x) \geq d^* = \max_x \min_y L(y,x).
\]
homogenize
\[ 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}
\]
As in linear programming, the dual of the dual is obtained from the optimal
strategy of the competing player:
\[ {\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}{}
{\bf The Trust Region Subproblem:}

Let
\[ q(x):= x^tAx - 2a^tx,
\]
\begin{eqnarray*}
(TRS)~~~~~ \mu^* := &\min& q(x)\\
&\mbox{s.t.}&
x^tx = s^2~~(\leq s^2).
\end{eqnarray*}

where

$A=A^t$, not necessarily semidefinite\\
$a \in \Re^n$, $s>0.$
~~\\
(application: quadratic model for unconstrained minimization)
\end{slide}
\begin{slide}{}
{\bf Homogenization of TRS}
\begin{eqnarray*}
\mu^* &=& \min\limits_{||x||=s,~y_0^2=1}  x^tAx - 2y_0a^tx \\
&=& \max\limits_t \min\limits_{||x||=s}  x^tAx - 2y_0a^tx +ty_0^2-t \\
&=& \max\limits_t \min\limits_{||x||=s,~y_0^2=1}  x^tAx - 2y_0a^tx
+ty_0^2-t \\
&=& \max\limits_t \min\limits_{||x||^2+y_0^2=s^2+1}  x^tAx - 2y_0a^tx
+ty_0^2-t
\end{eqnarray*}

\[ =  \max\limits_t (s^2+1)\lambda_1(D(t)) -t\]

$$D(t) = \left(
\begin{array}{cc}
t & -a^t \\
-a & A
\end{array}
\right).
$$
\end{slide}
\begin{slide}{}
%%This is slide 14
{\bf unconstrained dual problem to TRS}

$$D(t) = \left(
\begin{array}{cc}
t & -a^t \\
-a & A
\end{array}
\right)
$$

$y=\left( \begin{array}{c} y_0\\ x \end{array} \right)$ 
normalized eigenvector for $\lambda_{\min} D(t)$
\[
k(t) =  (s^2+1)\lambda_{\min}(D(t)) -t,
\]

\[  \mbox{***   }~~~ \max_t k(t)
\]

Note
\[  k^\prime(t) = (s^2+1)y_0^2 -1=0  \]
is feasibility for $x$
\end{slide}
\begin{slide}{}
%%This is slide 15
{\bf SDP Primal-Dual Pair}
\[
\max_t k(t) =  (s^2+1)\lambda_{\min}(D(t)) -t,
\]


add the variable $\lambda$
\[
\begin{array}{cc}
\max & (s^2+1)\lambda - t \\
\mbox{s.t.} & D(t) \succeq \lambda I
\end{array}
(DSDP)
\]

Lagrangian dual of this dual is:
\[
\begin{array}{cc}
\min & \tr D(0)X \\
\mbox{s.t.} & \tr X = s^2+1 \\
      &  X_{11} = 1\\
      & X \succeq 0
\end{array}(PSDP)
\]
\end{slide}
\begin{slide}{}
%%This is slide 16
primal-dual interior point method:

approx. solve perturbed optimality conditions
using Newton's method:
\[
\begin{array}{c}
  \tr X = s^2+1 \\
        X_{11} = 1\\
  D(t) - \lambda I - Z = 0\\
  \mu Z^{-1} - X = 0  \\
       X \succ 0, Z \succ 0
\end{array}
\]


\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 permutaion 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 equivalend 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}{}
\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}{}

{\bf THEOREM}\\
Let $x=vec(X)$ and $F_S$ be the feasible set of (SDP).
Define the centroid point
\[
\hat{Y} := \frac 1{n!} \sum\limits_{X \in \Pi_n}
 \left[
\begin{array}{cc}
1& x^t \\
x & xx^t
\end{array}
\right].
\]
Then:\\

1.~~
$\hat{Y}$ has a 1 in the (1,1) position and $n$ diagonal $n \times n$
blocks with diagonal elements $1/n.$ The first row and column equal
the diagonal.  The rest of the matrix is made up
of  $n \times n$ blocks with all elements equal to $1/(n(n-1))$  except
for the diagonal elements which are 0:
\end{slide}
\begin{slide}{}
\[
{\small
\begin{array}{ll}
\hat{Y} =\\
{   %\tiny
=\left[
\begin{array}{c|c}
1 & \frac 1n e^t \\ \hline\\
\frac 1n e & \begin{array}{cccc}
             \diag(\frac 1n e) &  (\frac 1{n(n-1)}) (E-I)
       &\cdots &(\frac 1{n(n-1)}) (E-I) \\
                      \cdots  &\cdots  &\cdots  & \cdots  \\
                      \cdots  &\cdots  &\cdots  & \cdots  \\
                      \cdots  &\cdots  &\cdots  & \cdots  \\
                    (\frac 1{n(n-1)}) (E-I) &\cdots
   &(\frac 1{n(n-1)}) (E-I) & \diag(\frac 1n e)
             \end{array}
\end{array}
\right] } \\
~\\
=\left[
\begin{array}{c|c}
1 & \frac 1n e^t \\
\hline\\
\frac 1n e &
E \otimes \left( \frac 1{n(n-1)} (E-I)\right)
       - I \otimes \left( \frac 1{n(n-1)} E - \frac
            1{n-1} I\right)
\end{array}
\right]
\end{array}  }
\]
2.~~
\[
\rank(\hat{Y}) = (n-1)^2 +1
\]
3.~~
\[
\diag \hat{Y} =
 \left(
\begin{array}{c}
1 \\
\frac 1n e
\end{array}
\right)
\]
4.~~
\[
\trace(\hat{Y}) = 1 +n
\]
\end{slide}
\begin{slide}{}
5.~~\\
The $n^2+1$ eigenvalues of $\hat{Y}$ are given in the vector
\[
(2,\frac 1{n-1} e_{(n-1)^2},0 e_{2n-1})
\]
6.~~
\[
{\cal N} (\hat{Y}) = \left\{
\left( \begin{array}{c}   -\frac 1n e^tu\\ u
          \end{array}  \right)
          : u \in {\cal R} (T^t) \right\},
\]
where $T$ is the assignment constraint matrix.

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

We can use the matrix $T$ to project onto the minimal face.

We get a simplified SDP with a positive definite feasible point.

Status: Solved $n=10$ to optimality.
\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}{}
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}
\end{document}