\documentclass{slides}
\pagestyle{plain}
\setlength{\textheight}{5.3in}
\setlength{\textwidth}{5.35in}
\newcommand{\F}{{\cal F}}
\newcommand{\Kprod}{\otimes}
\newcommand{\Diag}{\rm Diag\,}
\newcommand{\Sn}{{\cal S}_n}
\newcommand{\tran}{^T}
\newcommand{\diag}{\rm diag\,}
\newcommand{\tr}{\rm trace\,}
\newcommand{\trace}{\rm trace\,}
\newcommand{\svec}{{\rm svec\,}}
\newcommand{\sMat}{{\rm sMat\,}}
\newcommand{\hMat}{{\rm hMat\,}}
\newcommand{\dsvec}{{\rm dsvec\,}}
\newcommand{\sdiag}{{\rm sdiag\,}}
\newcommand{\vsMat}{{\rm vsMat\,}}
\newcommand{\kvec}{{\rm vec\,}}
\newcommand{\kmat}{{\rm Mat\,}}
\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}
\newcommand{\nc}{\newcommand}
\nc{\Hcal}{{\cal H}}
%\renewcommand{\leftmargin}{-.5in}


\newcommand{\rank}{{\rm rank\,}}
\newcommand{\p}{{\cal P}}
\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\,}}




\def\QED{~\rule[-1pt] {8pt}{8pt}\par\medskip ~~}
\begin{document}
%=======================
%=======================
\begin{slide}{}
\begin{center}
{\bf
Is Lagrangian (SDP) Relaxation Best for Quadratic Optimization?
}
\end{center}


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

~\\
~\\

\end{slide}
\begin{slide}{}
%\large{
\begin{center}
{\bf OUTLINE}
\end{center}
%}
\begin{enumerate}
\item[$\bullet$]
Quadratically constrained quadratic program, QQP.

\item[$\bullet$]
Special case of Max-Cut, MC, problem:\\
equivalent bounds to Lagrangian (SDP) relaxation\\
redundant constraints

\item[$\bullet$]
SDP equivalent to Lagrangian relaxation for QQPs.

\item[$\bullet$]
Theme (or conjecture):
{\em Lagrangian relaxation is best}

\item[$\bullet$]
zero duality gap for nonconvex problems
\end{enumerate}

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


\begin{center}
{\bf QQP}
\end{center}

\[
         q_i(x) : =  x^TQ_ix+2g_i^Tx +\alpha_i, \quad Q_i=Q_i^T
\]
\[
(\mbox{QQP}_x)
   \begin{array}{rcl}
        q^*:= &  \min  & q_0(x)\\
&{\rm subject~to} & q_k(x) \leq 0\\
  && k \in {\cal I} :=\{1, \ldots , m\}\\
&& x \in \Re^n
            \end{array}
\]
Lagrangian of QQP$_x$
\[
          L(x,\lambda):= q_0(x)
 + \sum_{k \in {\cal I} } \lambda_k q_k(x),
\]
$\lambda=(\lambda_k) \geq 0$ are nonnegative Lagrange
multipliers.

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

{\bf Lagrange multipliers - two uses.}

1. Classical: if a CQ holds at optimum
$\bar{x}$, then the KKT necessary conditions for optimality
hold
\begin{eqnarray*}
    \bar{\lambda} \geq 0, \nabla L(\bar{x},\bar{\lambda})=0\\
     \bar{x} \mbox{ feasible }\\
     \bar{\lambda}_k q_k(\bar{x})=0, \forall k \in {\cal I}
\end{eqnarray*}
If the Lagrangian at $\bar{\lambda}$ is also convex
in $x$, then KKT sufficient for optimality.

2. Lagrangian Relaxation (duality):
\[
       q^* \geq d^*:=  \max\limits_{\lambda \geq 0}
          \min_x  q_0(x)  
 + \sum_{k \in {\cal I} } \lambda_k q_k(x).
\]




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

Zero duality gap holds if $q^*=d^*.$ 

Strong duality holds if $q^*=d^*$ and also $d^*$ is attained. 

Moreover, $d^*$ can be efficiently evaluated using SDP.

Questions:\\
$\bullet$Can one do better than the Lagrangian relaxation?\\
$\bullet$When does a zero duality gap hold?\\
$\bullet$What redundant constraints can
be added to close the duality gap?








\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}{}
\[
{\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.~~
\[
{\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}{}

\begin{center}
{\bf Tractable Relaxations of Max-Cut}
\end{center}
\[
(MCQ)~~~  \begin{array}{c}
   \mu^*:= \max\limits_{x \in \F} q_0(x) \quad ( : = x^TQx -2 c^Tx).
\end{array}
\]
where $\F=\left\{\pm 1\right\}^n$\\
--------------------------------

perturbing diagonal of $Q$ on $\F:$
\[
\begin{array}{rcl}
q_u(x)& : = &x^T(Q+\Diag(u))x -2 c^Tx - u^Te\\
      &~=&q_0(x),~~\forall x \in \F.
\end{array}
\]

\end{slide}
\begin{slide}{}
{\bf Bound 0:}
the trivial bound from allowing the diagonal perturbations:
\[
  \mu^* \leq f_0 (u) := \max_x q_u(x).
\]
The function $f_0$ can take on the value $+\infty.$ 
Let 
\[S:=\left\{u:u^Te=0, Q+\Diag(u)\preceq 0\right\}.
\]
Then:
\[
\begin{array}{|c|}
\hline\\
  \mu^* \leq B_0 := \min_u  f_0(u) \\
    \left(= \min\limits_{u^Te=0}  f_0(u),
       \mbox{ if } S \neq \emptyset   \right).\\
\hline
\end{array}
\]
Using the hidden semidefinite constraint:
\[
  \mu^* \leq B_0 = \min_{Q+\Diag(u) \preceq 0}  f_0(u).
\]

\end{slide}
\begin{slide}{}
{\bf Bound 1:}
relax the feasible set to
the sphere of radius $\sqrt{n}$ (tractable trust region subproblem, TRS):
\[
\mu^* \leq f_1(u):= \max_{|| x ||^2 =n} ~ q_u(x)
\]
and
\[
\begin{array}{|c|}
\hline\\
  \mu^* \leq B_1 :=\min_u f_1(u).\\
~~\\
\hline
\end{array}
\]


The inner maximization problem is called a
trust region subproblem and is tractable.
This bound provides the central tool in the proofs of equivalence.

\end{slide}
\begin{slide}{}
{\bf Bound 2:} box constraint:
\[
\mu^* \leq f_2(u):= \max_{| x_i | \leq 1} ~ q_u(x).
\]
add the semidefinite constraint to make bound
tractable.
\[
  \mu^* \leq \min_{u} f_2(u)
\]
and
\[
\begin{array}{|c|}
\hline\\
  \mu^* \leq B_2 :=\min_{Q+\Diag(u) \preceq 0} f_2(u).\\
~~\\
\hline
\end{array}
\]


\end{slide}
\begin{slide}{}
{\bf Bound $B_1^c$:} lift to eigenvalue bound:

\[
 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
\]
\[
  \mu^* \leq f_1^c(u) := \max_{||y||^2=n+1} q^c_u(y)
\]
where
\[
   \max_{||y||^2=n+1} q^c_u(y)
   = (n+1) \lambda_{\max} (Q^c + \diag (u) ) - u^Te
\]
\[
\begin{array}{|c|}
\hline\\
  \mu^* \leq B_1^c :=  \min_{u} f_1^c(u).\\
~~\\
\hline
\end{array}
\]

Similarly, we get equivalent bounds $B_0^c$
and homogenized bounds for the other models.


\end{slide}
\begin{slide}{}
{\bf Bound $B_3$:} SDP bound:

After homogenization ( $c=0$), use
\[ x^TQx = \tr x^TQx = \tr Qxx^T\]
and, for $x \in \F,$ $y_{ij} = x_ix_j$ defines a
symmetric, rank one, positive semidefinite matrix $Y$ with diagonal elements 1.
Relax the rank one condition.
\[
\begin{array}{|ccc|}
\hline
&&\\
       B_3 :=&\max &\tr QY \\
 &  \mbox{~subject to~} &\diag(Y) = e \\
        && Y \succeq 0.\\
\hline
    \end{array}
\]



\end{slide}
\begin{slide}{}
Summary: ref. PW:
(without restrictions e.g. $u^Te=0$)


\[
\begin{array}{|rcl|}
\hline
&&~\\
 B_0 &=&\min\limits_u \max\limits_x q_u(x)\\
 B_1 &=&\min\limits_u \max\limits_{x^Tx=n} q_u(x)\\
 B_2 &=&\min\limits_u \max\limits_{-1 \leq x_i \leq 1} q_u(x)\\
 B_3 &=&\max \{\tr Q^cY : \diag(Y) = e,~ Y \succeq 0. \}\\
 B_1^c &=&\min\limits_u \max\limits_{y^Ty=n+1} q^c_u(y)\\
&&~\\
\hline
\end{array}
\]


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

Now replace $\pm 1$ constraints with $x_i^2=1, \forall i.$
\[
\begin{array}{ccc}
       (P_E)&\max & q_0(x)=x^TQx-2c^Tx \\
 &  \mbox{~subject to~} &
        x_i^2 = 1,~~i=1, \cdots, n.  \\
    \end{array}
\]
$B_L$ denotes Lagrangian relaxation bound.

Following our theme:
\begin{center}
\fbox{
{\bf Theorem } $B_L$ equals all above bounds.
}
\end{center}

 ref PRW.\\
(The proofs come from exploiting strong Lagrangian duality of TRS)


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

{\bf A Strengthened SDP Bound for MC}


(second lifting - motivated by the strong duality results to follow)

lifting procedure
\[ X=xx^T\]
implies
\[X^2=xx^Txx^T=nX.\]
equivalent quadratic matrix model for CQ

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

\begin{eqnarray*}
\mu^*:=&\max& \tr QX\\
&\mbox{s.t.}&\diag(X)=e\\
&&X^2-nX=0\\
&&X \succeq 0.
\end{eqnarray*}
Note: $X^2=nX,~\trace X = n$ implies $X$ is rank one.
But, we cannot solve this nonconvex problem in general, i.e. we have to
look at the Lagrangian relaxation.



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

notation:\\
~$\bullet$ $S \in \Sn,$\\
~$\bullet$ $s=\svec(S) \in \Re^{t(n)}$ 
vector formed (columnwise) from $S$
ignoring strictly lower triang.\\
~$\bullet$ $S=\sMat(s)$ inverse of $\svec$\\
~$\bullet$ $\hMat (v)$ 
is adjoint of $\svec$,
off-diagonal terms are multiplied by a half\\
~$\bullet$ $\dsvec (S)$ is
adjoint of $\sMat$, operator 
like $\svec$ but off diagonal elements are
multiplied by 2\\
~$\bullet$ $\sdiag(s):= \diag( \sMat(s))$\\
~$\bullet$ $\vsMat(s)=\kvec(\sMat(s))$
\[\vsMat^*(s)=\dsvec \left( \left(\kmat(v)+\kmat(v)^T\right)/2 \right).
\]


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

As above - use equivalent program
\[
 {\rm MC_O} \begin{array}{ccc}
    \mu^*=
    &\max & \frac 12 \tr QX \\
  &\mbox{s.t.<}& \diag(X) = e\\
     &&X^2-nX=0\\
     &&X \succeq 0,
\end{array}
\]
replace linear constraint with $ ||\diag(X) - e||^2=0$ and
homogenize the problem.
use $X=\sMat(x)$
\[
 {\rm MC_O} \begin{array}{cll}
     \mu^*=
    &\max & \frac 12 \tr \left(Q\, \sMat(x)\right)y_0 \\
  &\mbox{s.t.}& \sdiag(x)^T \sdiag(x) \\
          && ~~~- 2 e^T \sdiag(x)y_0 + n=0\\
     &&\sMat(x)^2-n\, \sMat(x)y_0=0\\
     &&\sMat(x)y_0 \succeq 0\\
     &&1-y_0^2=0.
\end{array}
\]


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

Lagrangian dual
\[
 \begin{array}{lcc}
     \mu^*\leq \mu^*_3:=
    \min\limits_{T \succeq 0,w,S}
\max\limits_{y_0^2=1}  \frac 12 \tr \left(Q\sMat(x)\right)y_0 \\
  ~~~~~~~~~~~~~~+w\left( \sdiag(x)^T \sdiag(x)\right. \\
  ~~~~~~~~~~~~~~~~~~~~~ \left. -2 e^T \sdiag(x)y_0 + n\right)\\
     ~~~~~~~~~~~~~~~~ +\tr S\left((\sMat(x))^2-n\, \sMat(x)y_0\right)\\
     ~~~~~~~~~~~~~~~~~~~~-\tr T(\sMat(x)y_0).
\end{array}
\]

Note:  $\sMat(x) \succeq 0$ necessarily;
$\sdiag(x)=e$ necessarily holds. Therefore,
relaxation is strengthened.
Move $y_0$ into Lagrangian
without increasing the duality gap, since a TRS
i.e. add $ t(1-y_0^2)$ into Lagrangian.
Then apply the hidden semidefinite constraint theme. 


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

The constant part (no Lagrange multipliers) of the Hessian is:
\beq \label{eq:hessian1}
 H_c:=\pmatrix{
  0 & \frac 12 \dsvec(Q)^T\cr
 \frac 12 \dsvec(Q)  & 0\cr
}.
\eeq
The nonconstant part of the Hessian is made up of a linear
combination of matrices, i.e. it is a linear operator on the
Lagrange multipliers. 
Note that 
\begin{eqnarray*}
\tr S (\sMat(x))^2 &=& \tr S\, \sMat(x)\, I\, \sMat(x)^T\\
     &=& \left(\kvec( \sMat(x))\right)^T\left( I \Kprod S \right)
                             \left(\kvec( \sMat(x))\right)\\
     &=& x^T \vsMat^* \left( I \Kprod S \right)
                             \vsMat(x).
\end{eqnarray*}
For notational convenience,
we use the {\em negative} of the Hessian and split it up into four
linear operators:
\beq \label{eq:hessian2}
   \begin{array}{ccc}
 \Hcal(w,S,T,t):= \Hcal_1(w) + \Hcal_2(S) + \Hcal_3(T) +
             \Hcal_4(t) \\
  :=w\pmatrix{
  0 & 2\, \svec(I)^T\cr
  2\, \svec(I) & -2\Diag(\svec(I)) }
  \\
  +\pmatrix{
  0 & 2n\, \dsvec(S)^T\cr
   2n\, \dsvec(S)
        & -2\vsMat^*(I \Kprod S) \vsMat }\\
  +\pmatrix{
  0 & 2\, \dsvec(T)^T\cr
   2\, \dsvec(T) 
        & 0 }\\
  +t\pmatrix{
  2 & 0\cr
   0 & 0 }.\\
\end{array}
\eeq

We then get the (equivalent to the Lagrangian dual) semidefinite program 
\beq \label{eq:MCDSDP}
 {\rm MCDSDP} \begin{array}{ccc}
     \mu^*_{MCSDP3} =
    &\min & nw +\tr 0S + \tr 0T +t\\
  &\mbox{s.t.}& \Hcal(w,S,T,t) \succeq H_c\\
     && T \succeq 0, S=S^T\\
\end{array}
\eeq

The dual  of this SDP  is the strengthened SDP relaxation of MC:
\beq \label{eq:MCPSDP}
 {\rm MCPSDP} \begin{array}{ccc}
     \mu^*_{MCSDP3} =
    &\max & \trace H_cY\\
  &\mbox{s.t.}& \Hcal_1^*(Y) = n\\
  &                 & \Hcal_2^*(Y) = 0\\
  &                 & \Hcal_3^*(Y) \preceq 0\\
  &                 & \Hcal_4^*(Y) = 1\\
     && Y \succeq 0.
\end{array}
\eeq


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

{\bf Convex Quadratic Program}
\begin{eqnarray*}
\mu^*:=&\min& q_0(x)\\
&\mbox{s.t.}& q_k(x) \leq 0,\quad k=1, \ldots m,
\end{eqnarray*}
where all $q_i(x)$ are convex quadratic functions.
The dual is
\[ 
\mbox{DCQP}\qquad
\nu^*:= \max\limits_{\lambda \geq 0}\ \min\limits_x\ q_0(x)
           + \sum_{k=1}^m \lambda_k q_k(x).
\]

$\bullet$(KKT) conditions are sufficient for global optimality

$\bullet$if the primal value of CQP is bounded then it is
attained and there is no duality gap, (e.g. Peterson and Ecker
or  Terlaky).

$\bullet$ the dual may not be attained



\end{slide}
\begin{slide}{}
{\bf Nonconvex Cases}

{\bf 1. Rayleigh Quotient}

$A=A\tran \in \Sn$
\[
 \lambda_{\min} = \min \{x\tran Ax : x\tran  x = 1\}.
\]
tractable (nonconvex) problem

no (Lagrangian) duality gap for this nonconvex problem
\[
\begin{array}{rcl}
 \mu^*&:=& \max\limits_{\lambda}\ \min\limits_x\ 
      x\tran Ax -\lambda (x\tran  x - 1)\\
 &=& \max\limits_{A - \lambda I \succeq 0}\ \min\limits_x\ 
               x\tran (A -\lambda I)x  + \lambda\\
 &=& \max\limits_{A - \lambda I \succeq 0}\ \lambda\\
 &=& \lambda_{\min}
\end{array}
\]


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

{\bf 2. Trust Region Subproblem}
\begin{eqnarray*}
 &\mu^*:=\min& q_0(x)\\
&\mbox{s.t.}& x\tran x - \delta^2\leq 0 \mbox{ (or } =0). \\
\end{eqnarray*}
for ``$\le$," the Lagrangian dual is:
\[ 
\mbox{DTRS}\qquad
 \nu^*:=\max\limits_{\lambda \geq 0}\ \min\limits_x\ q_0(x) + \lambda 
(x\tran x - \delta^2).
\]
strong duality holds and equivalent to (ref Stern-Wolk.) the
(concave) nonlinear semidefinite program 
\begin{eqnarray*}
\mbox{DTRS}\qquad
&\nu^*:=\max& g_0\tran  (Q+\lambda I)^{\dagger} g_0 - \lambda \delta^2\\
&\mbox{s.t.}& Q+\lambda I \succeq 0\\
&&\lambda \geq  0.
\end{eqnarray*}

theme: tractable problem (ref More-Sorensen) but strong duality holds.



\end{slide}
\begin{slide}{}
{\bf 3. Two Trust Region Subproblem}
TTRS consists in minimizing a
(possibly nonconvex) quadratic function subject to a norm and a
least squares constraint.

ref in SQP methods by CDT.

TTRS can have a nonzero duality gap, ref PY and Y.

if objective not convex,
then the primal may not be attained, ref LZ.

TRS can have at most one local and nonglobal optimum, ref M.

Still an open problem whether TTRS is an NP-hard or a polynomial time
problem.


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

Note: a quadratic constraint can be written as
\[  y^tPy \leq \delta  \]
after the homogenization. This is lifted to
\[  \trace PY \leq \delta. \]
Second lifting:
\[   YPY \preceq \delta Y. \]
This strictly strengthens the SDP relaxation.


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


{\bf Orthogonally Constrained Programs with Zero Duality Gaps}

\[ \{X: X X\tran =I\} \]
Stiefel manifold ref EAS

$A$ and $B$ $n\times n$ symmetric matrices
\begin{equation}
\begin{array}{rcl}
{\rm QQP_O}\qquad  \mu^O:=&\min& \tr AXBX\tran\\
&{\rm s.t.}& XX\tran=I.
\end{array}
\end{equation}

Tractable problem using
classical Hoffman-Wielandt inequality.


But, Lagrangian dual has a duality gap, ref ZKRW.

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


The constraints $XX\tran=I$ and
$X\tran X=I$ are equivalent. Add redundant constraints.
\begin{eqnarray*}
{\rm QQP_{OO}}\qquad  \mu^O:=&\min& \tr AXBX\tran\\
&{\rm s.t.}& XX\tran=I,\ X\tran X=I.
\end{eqnarray*}
dual problem is
\begin{eqnarray*}
{\rm DQQP_{OO}}\\
\mu^O \geq \mu^D:=&\max& \tr S+\tr T\\
&\mbox{s.t.}&
(I\Kprod S)+(T\Kprod I)\preceq (B\Kprod A)\\
&& S=S\tran,\ T=T\tran.
\end{eqnarray*}

{\bf Theorem}
Strong duality holds for $\rm QQP_{OO}$ and $\rm DQQP_{OO},$ 
i.e.  $\mu^D=\mu^O$ and both primal and dual are attained.
\QED

Theme again holds.

\end{slide}
\begin{slide}{}
Other applications:

Weighted Sums of Eigenvalues;

Graph Partitioning Problem;

TRS like constraints $\{X: XX\tran \preceq I\}$
(extension of Hoffman-Wielandt inequality)




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

Concluding Remarks:

In each case of a tractable bound for a nonconvex problem, the structure
allows for redundant constraints to be added to close the Lagrangian
duality gap.

What is the correct question about ``best''? Can we close or reduce the
duality gap in general? (ref KT)
\end{slide}
\begin{slide}{}
\end{slide}
\begin{slide}{}
\end{slide}

\end{document}