%======================= main.tex ===========================================
\documentstyle[psfig]{slides}
\include{latexsym}
\include{amsfonts}
%\input psfig
\newtheorem{exam}{Example}
\newtheorem{prop}{Proposition}
\newtheorem{lem}{Lemma}
\newtheorem{thm}{Theorem}
\newtheorem{cor}{Corollary}
%\newtheorem{figure}{Figure}
\newcommand{\Diag}{{\rm Diag\,}}
%\newcommand{\Reals}{{\mathbb R}}
\newcommand{\diag}{{\rm diag\,}}
\newcommand{\tr}{{\rm trace\,}}
\newcommand{\trace}{{\rm trace\,}}
\newcommand{\rank}{{\rm rank\,}}
\newcommand{\p}{{\mathcal 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}{{\mathcal C}_k}
\newcommand{\dk}{{\mathcal D}_k}
\newcommand{\uu}{{\mathcal U}}
\newcommand{\uk}{{\mathcal U}_k}
\newcommand{\vk}{{\mathcal V}_k}
\newcommand{\wk}{{\mathcal W}_k}
\newcommand{\wm}{{\mathcal W}_m}
\newcommand{\w}{{\mathcal W}}
\newcommand{\wks}{{\mathcal W}^s_k}
\newcommand{\wms}{{\mathcal W}^s_m}
\newcommand{\zk}{{\mathcal Z}_k}
\newcommand{\zks}{{\mathcal Z}^s_k}
\newcommand{\z}{{\mathcal Z}}
\newcommand{\n}{{\mathcal N}}
\newcommand{\ra}{{\mathcal R}}
\newcommand{\q}{{\mathcal Q}}
\newcommand{\s}{{\mathcal S}_n}
\newcommand{\m}{{\mathcal 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\\
\rule{155mm}{.1mm}
~~\\
~~\\
~~\\
~~\\
(with Franz Rendl and Qing Zhao)

\end{slide}

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

Wednesday May 15- Friday May 17, 1996 

The Fields Institute\\
University of Toronto campus\\

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



\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 {\mathcal S}_n, 
\]
where ${\mathcal 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}
\begin{enumerate}
\item
Finding bounds and good feasible solutions
for hard combinatorial problems such as:
\begin{enumerate}
\item
{\large \bf 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.
\item
logarithmic Chebychev approximation, structural optimization, pattern
separation by ellipsoids, statistics (educational testing problem),
{\large \bf control and systems theory}
\end{enumerate}
\end{slide}
\begin{slide}{}
How does SDP arise from quadratic approximations?

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}{}

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 (multipliers $x_i$):\\
\[ 
\begin{array}{ccc}
  L(y,x) &=& \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 {\mathcal 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}{}
\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 $\mathcal I$ to maximize the weight of the
edges with one end point with index in $\mathcal 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 \mathcal 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.
\]

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

Note that if $X=xx^t$, then
\[  x^tQx = \tr x^tQx = \tr QX.  \]

We get the equivalent problem
\[
\begin{array}{ccc}
      \mbox{sup} &q(x)=\tr XQ \\
   \mbox{s.t.} &  \diag (X) = e\\
  & X=X^t \succeq 0\\
  &  X ~\mbox{is rank one}
    \end{array}
\]

Relax the rank-1 condition on $X$ to get the SDP relaxation.
\end{slide}
\begin{slide}{}
Goemans-Williamson:\\
-Randamized approximation algorithm (polynomial time)
that delivers solutions at least 
\[
\rho=.87856~~\mbox{(performance guarantee)}
\]
times the optimal value. \\
-It depends on a means of randomly rounding a solution from the
semidefinite relaxation.


\end{slide}
\begin{slide}{}
\begin{center}
\begin{tabular}{|r|r|r|}
\hline
\multicolumn{1}{|c}{size} $n$ &
\multicolumn{1}{|c}{iterations}&
\multicolumn{1}{|c|}{hh:mm:ss}\\
\hline
100 & 14 &      48\\
150 & 12 &    2:30\\
200 & 12 &    6:30\\
250 & 13 &   14:24\\
300 & 14 &   30:24\\
400 & 14 & 1:24:36\\
500 & 14 & 2:13.18\\ \hline
\end{tabular}
\end{center}
SDP relaxation for max-cut, computed on
a 486, 66 Mhz PC
\end{slide}
\begin{slide}{}
Max--Cut with triangle inequalities
\begin{center}
\begin{tabular}{|r|r|r@{ (}c@{) }|r|r|}\hline
\multicolumn{6}{|l|}{random graphs, edge-weights $\in\{-10,\ldots,10\}$}\\ \hline
\multicolumn{1}{|c}{size} $n$ &
\multicolumn{1}{|c}{cut}&
\multicolumn{1}{|c@{ (}}{upper bnd}&
\%&
\multicolumn{1}{|c}{hh:mm:ss}&
\multicolumn{1}{|c|}{iters}\\ \hline\hline
 30 &  330 &  330.0001 &0.0&       54 &  59 \\
 40 &  619 &  619.0000 &0.0&     2:02 &  60 \\
 50 &  708 &  708.0001 &0.0&  1:04:22 & 166 \\
 70 & 1215 & 1248.7142 &2.8&  4:42:21 & 220 \\
100 & 2440 & 2540.2528 &4.1& 37:56:05 & 266 \\ \hline\hline
\hline
\hline
\multicolumn{6}{|l|}{ random unweighted graphs, edge probability $0.5$}\\ \hline
\multicolumn{1}{|c}{size} $n$ &
\multicolumn{1}{|c}{cut}&
\multicolumn{1}{|c@{ (}}{upper bnd}&
\%&
\multicolumn{1}{|c}{hh:mm:ss}&
\multicolumn{1}{|c|}{iters}\\ \hline\hline
 30 &  143 &  143.0000 &0.0&       56 &  62 \\
 40 &  245 &  245.6864 &0.3&    59:19 & 247 \\
 50 &  374 &  375.3689 &0.4&  1:54:18 & 250 \\
 70 &  723 &  726.0399 &0.4&  5:57:22 & 257 \\ \hline
\end{tabular}
\end{center}
         number of nodes in the graph is $n$\\
 {\em cut} best cut found\\
 {\em upper bnd\ } value of the relaxation\\
 \% percentage of gap; relaxation-best cut\\
          computation times on a DEC-station
         5000/240.

 Note that the number of iterations is
         almost independent of $n$ if the gap is not closed.
\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}{}
SUN SPARC station 1 using MATLAB with a
fortran interface for the Lanczos algorithm.

Average results for several dimensions

The hard case examples had
multiplicity of the smallest eigenvalue ranging from 1 to 6. 

A multiple
of the identity was added when a positive definite matrix was needed.

The work is the amount of work times one Lanczos step.


\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
\hline
dim  &  prbs  &  dens  &  it  & cpu sec & work &   \\
\hline
1540-1565  & 30  &  .01  &  4.44  &  54.18  &  1.73 &    \\
\hline
1540-1558  & 30  &  .013  &  4.11  &  56.13 &  1.75 &pd \\
\hline
1500-1565  & 2  &  .01  &  4.29  &  57.04 &  4.85  & hc\\
\hline
1800-1865  & 12  &  .05  &  4.24  &  28.16&  4.25  & hc\\
\hline
\hline
\end{tabular}

pd - positive definite Hessian, hc - hard case

\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_{\mathcal 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_{\mathcal 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_{\mathcal 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_{\mathcal 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_{\mathcal 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}{}
After adding the assignment linear equality constraints,
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 \\
       & \arrow(Y) = e_{0} &&  \tr (DY) = 0 \\
       &  Y \succeq 0 & \\
\end{array}
\]
~~\\
{\bf BUT $D \succeq 0$}

Slater's condition always fails!!! 

The dual optimal set is unbounded.

How do we start a primal-dual feasible {\bf INTERIOR} point method???

How do we stop a primal-dual infeasible {\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 barycenter
\[
\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}{}
\[
{\tiny
\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.~~
\[
{\mathcal N} (\hat{Y}) =
           {\mathcal R} (\hat{T}^t) \mbox{~and~}
{\mathcal R} (\hat{Y}) =
           {\mathcal R} (\hat{V})
\]
so that
\[
{\mathcal N} (\hat{T}) =
           {\mathcal R} (\hat{V})~),
\]
where
\[ \hat{T}=\left[ \begin{array}{c|c}
       (- \frac 1n Te) & T  \end{array} \right] 
  ~~\left( =
         \left[ \begin{array}{c|c}
       - e & T  \end{array} \right] \right)
\]
is a $2n \times (n^2+1)$ matrix, 
\end{slide}
\begin{slide}{}
the assignment constraint matrix $T$ is 
\[
 T := \left[  \begin{array}{ccccc}
 e^t &0&\cdots &\cdots &0 \\
 0&e^t &0&\cdots &0 \\
 \cdots & \cdots &\cdots &\cdots &\cdots \\
 0 & \cdots &\cdots &0 &e^t \\
 I&I&\cdots&\cdots&I
\end{array}  \right],
\]
$\hat{V}$ is the block, bidiagonal $(n^2+1) \times
((n-1)^2+1)$ matrix
\[
\begin{array}{rcl}
\hat{V}&=&
\left[ \begin{array}{c|c}
1 & 0 \\
\hline
\kvec (I)/n &
\begin{array}{ccccc}
V & 0& \ldots &\ldots &0\\
-V & V&0 &\ldots &0\\
0 &-V &V&\ldots&0 \\
\ldots & \ldots &\ldots& \ldots& \ldots\\
\ldots & \ldots &0& -V& V\\
0  & \ldots&\ldots & 0 &-V \\
\end{array}
\end{array} \right],
\end{array}
\]
$V$ is the $n \times (n-1)$ matrix
\[
V =
\left( \begin {array} {cccc}
  \beta     &  \beta     & \ldots &  \beta \\
 1+\alpha    &  \alpha     & \ldots &  \alpha \\
  \alpha     &  1+\alpha   & \ldots &  \alpha \\
 \vdots &        & \ddots & \vdots \\
  \alpha     &  \alpha     & \ldots & 1+\alpha \\
\end  {array} \right),
\]
and $\alpha= -1/(n + \sqrt{n}),~\beta= -1/\sqrt{n}$ (so that $V^te=0$).

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


We can use the matrix $\hat{V}$ to project onto the minimal face.
\[   Y \in \hat{V} {\mathcal S}_d \hat{V}, ~~ d= t(n-1)^2+1)
\]

Sparsity can be maintained with this projection.

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

Status: Solved relaxation $n \leq 30$ to optimality.
\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{eqnarray*}
 Y &=&
  \left(
  \begin{array}{c}
   1 \\ \kvec X
   \end{array}   \right)
( 1~~\kvec X^t)  \\
   &=&
\left[
\begin{array}{cc}
   \left(
  \begin{array}{c}
   1 \\
   X_{:1}\\
   X_{:2}\\
   \vdots \\
   X_{:n}\\
   \end{array}   \right)
   (1 ~~
   X_{:1}^t~~
   X_{:2}^t~~
   \vdots ~~
   X_{:n}^t)
\end{array}  \right],\\
\end{eqnarray*}
which contains the $n^2$ blocks
\[
  (X_{:i}X_{:j}^t).
\]
1) diagonal of off-diagonal blocks are 0
\[  \diag(X_{:i}X_{:j}^t)=X_{:i} \circ X_{:j} = 0, ~ \mbox{if}~ i \neq
j,
\]
2) off-diagonal of diagonal blocks are 0
\[ X_{i:} \circ X_{j:} = 0, ~ \mbox{if}~ i \neq j,
\]


\end{slide}
\begin{slide}{}
\begin{center}
{\bf \large GANGSTER OPERATOR}
\end{center}
\psfig{figure=mobster.PS,height=3in,width=3.9in}

\[
\left[ \begin{array}{cccccccc}
  & 0 & & & 0 \\
0 & 0 &0& & 0 \\
  & 0 & & & 0 \\
  &   & & & 0 \\
0 & 0 &0&0&   \\
\end{array} \right],
\]
\[
{\mathcal G}(Y) = 0.
\]


\end{slide}
\begin{slide}{}
We can eliminate the redundant
constraints and obtained a full rank constraint.

simple projected SDP relaxation
\[
\begin{array}{ll}
\min & \tr (\hat{V}^tL_Q\hat{V})X  \\
\mbox{~s.t.}
 & (\hat{V}X\hat{V}^t)_{00}  = 1 \\
 & {\mathcal PG}_{\hat{J}}(\hat{V}X\hat{V}^t) = 0  \\
 &  X \succeq 0,
\end{array}
\]
where the operator
\[ {\mathcal PG}_{\hat{J}}: {\mathcal S}_{t((n-1)^2+1)} \rightarrow
\Re^{n^3-2n^2}
\]

\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}{}
Numerics (Thanks to Qing Zhao)

\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}{}
\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$
$${\mathcal 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 {\mathcal 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 {\mathcal F}_k
\end{array}
$$

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

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

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

note $X \in {\mathcal 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 {\mathcal 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 & ${\mathcal E}_m \cap {\mathcal 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 & ${\mathcal E}_m \cap {\mathcal P}$ &
${\mathcal E}_m \cap {\mathcal P}\cap{\mathcal 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 & ${\mathcal E}_m \cap {\mathcal P}$ &
${\mathcal E}_m \cap {\mathcal P}\cap{\mathcal 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}

