\documentclass[landscape]{seminar}
\usepackage{amssymb}
\usepackage{psfig}
\pagestyle{empty}

\newcommand{\trace}{{\rm trace\,}}
\newcommand{\rank}{{\rm rank\,}}
\newcommand{\spanl}{{\rm span\,}}
\newcommand{\tr}{{\rm trace\,}}
\newcommand{\dom}{{\rm dom\,}}
\newcommand{\diag}{{\rm diag\,}}
\newcommand{\Diag}{{\rm Diag\,}}
\newcommand{\Mat}{{\rm Mat\,}}
\newcommand{\kvec}{{\rm vec\,}}
\newcommand{\svec}{{\rm svec\,}}
\newcommand{\dsvec}{{\rm dsvec\,}}
\newcommand{\Hmat}{{\rm Hmat\,}}
\newcommand{\vSmat}{{\rm vSmat\,}}
\newcommand{\Smat}{{\rm Smat\,}}
\newcommand{\sMat}{{\rm sMat\,}}
\newcommand{\hMat}{{\rm hMat\,}}
\newcommand{\vsMat}{{\rm vsMat\,}}
\newcommand{\kmat}{{\rm Mat\,}}
\newcommand{\sdiag}{{\rm sdiag\,}}
\newcommand{\Kprod}{\otimes}
\newcommand{\relint}{\rm relint\,}
\newcommand{\Sn}{{\mathcal S^n\,}}
\newtheorem{defi}{Definition}
\newtheorem{example}{Example}
\newtheorem{prop}{Proposition}
\newtheorem{lem}{Lemma}
\newtheorem{thm}{Theorem}
\newtheorem{cor}{Corollary}
\newtheorem{rem}{Remark}
%\newtheorem{table}{table}
\newtheorem{remark}{Remark}
\newtheorem{conj}{Conjecture}
\newtheorem{alg}{Algorithm}

\begin{document}

\begin{slide}{}

\begin{center}
{\bf \large
Can Semidefinite Programming Make the Cut?
}

\vspace{5mm}

Miguel F. Anjos \\

(joint work with Prof. Henry Wolkowicz) \\
 
\vspace{5mm}

Department of Combinatorics \& Optimization \\

\vspace{10mm}

\mbox{
\begin{figure}
\psfig{file=UWlogori.ps,height=20mm}
\end{figure}
}

{\small Graduate Student Conference - Faculty of Mathematics}

{\small 27 June 2000}
\end{center}
\end{slide}

\begin{slide}{}
\begin{center} {\bf The MAX-CUT problem (MC)} \end{center}

Given a graph $G=(V,E)$ and weights $w_{ij}$
for all edges $(i,j) \in E$, find an edge-cut of maximum weight, i.e.
find a set $S \subseteq V$ s.t. the sum of the weights of the edges
with one end in $S$ and the other in $V \setminus S$ is maximum.

We assume wlog that $w_{ii} = 0$ for all $i \in V$,

and that $G$ is complete (assign $w_{ij} = 0$ if edge $ij \not\in E$).
\end{slide}

\begin{slide}{}
\begin{center} {\bf Some applications of MC} \end{center}

\begin{itemize}
\item Statistical physics: Finding the ground state of a spin glass
according to the Ising model
\item VLSI: Minimizing the number of vias in a two-sided circuit board
\item Network design: Solving the separation problem in a cutting plane
approach
\end{itemize}

\vspace{1cm}

Also: MC is one of the simplest ``hard'' problems in Combinatorial Optimization
(Knapsack Problem, Travelling Salesman Problem, Assignment Problems, etc.)
\end{slide}

\begin{slide}{}
\begin{center} {\bf Approaches to MC} \end{center}

The general MC problem is NP-hard,
even though it is tractable for some classes of graphs, e.g.
planar graphs (VLSI).

Techniques used for general MC include:
\begin{itemize}
\item Heuristics;

\item Integer programming enumerative techniques (Branch-and-Bound);

\item Approximation algorithms.
\end{itemize}

\vspace{1cm}

Our interest is in finding tight (upper) bounds on $\mu^{*}$ using
Semidefinite Programming (SDP).
\end{slide}

\begin{slide}{}
\begin{center} {\bf Semidefinite Programming (SDP)} \end{center}

We assume that we have an algorithm
to solve a semidefinite program:
\[
\begin{array}{cl} \max   & <Q,X> \\
                   \mbox{s.t.}  & {\cal A}(X) = b \\
                                & X \succeq 0,
\end{array}
\]
\begin{itemize}
\item $<Q,X> := \mbox{trace}\,(QX)$ is the inner product in the space of
symmetric matrices ${\cal S}^n$, \\
\item ${\cal A}(X) = b$ represents a collection of linear constraints, and \\
\item $X \succeq 0$ denotes that $X$ is symmetric positive semidefinite.
\end{itemize}
\end{slide}

\begin{slide}{}
The matrix $X \in {\cal S}^n$
is said to be positive semidefinite
if
\[ y^T X y \geq 0 \;\mbox{for all}\,\, y \in \Re^n.
\]

Equivalently, \\
\begin{center}
$X$ is positive semidefinite\\ {\bf iff}\\
all the eigenvalues of $X$ are non-negative.
\end{center}
\end{slide}

\begin{slide}{}
\begin{center} {\bf Formulations of MC} \end{center}

Let the vector $v \in \{\pm 1\}^n$, $n = | V |$,
represent a cut in the graph $G$
via $S = \{i : v_i = +1\}$ and $V \backslash S = \{i : v_i = -1\}$.

Then we can formulate MC as:

$\begin{array}{ccl}
\mu^{*}=&\max
    &\sum\limits_{1\leq i<j \leq n } w_{ij} \left(\frac{1-v_i v_j}{2}\right) \\
                    &\mbox{s.t.}
    & v \in \{ \pm 1\}^n.
\end{array}$

Equivalently,
\[
(\mbox{MC1}) \quad
\begin{array}{ccl}
\mu^{*}=
   &\max & v^{T} Q \, v \\
   &\mbox{s.t.}  & v_i^2 = 1, \hspace{6mm} i=1,\ldots,n,
        \end{array}
\]

where $Q = \frac{1}{4} (\Diag(A\,e)-A)$, and $A=(w_{ij})$ is the weighted
adjacency matrix of $G$.
\end{slide}

\begin{slide}{}
Consider the change of variable $X = v v^T, v \in \{\pm 1\}^n$. Then
$X_{ij} = v_i v_j$ and:
\begin{itemize}
\item $X$ is symmetric and rank-1;
\item $X \succeq 0: y^T X y = y^T v v^T y = (v^T y)^2 \geq 0$;
\item and if $v_i^2 = 1$, then $\diag(X) = e$ (all ones);
\item obj. function: $v^T Q v=\trace (v^T Q v)=\trace (Q v v^T)=\trace QX$.
\end{itemize}

In fact, MC is equivalent to
\[
(\mbox{MC2}) \quad
\begin{array}{ccl}
\mu^{*}=
    &\max & \trace Q X \\
    &\mbox{s.t.} & \diag(X)= e\\
                      && \mbox{rank}(X)=1\\
                      && X\succeq 0, \, X \in \Sn.
 \end{array}
\]
\end{slide}

\begin{slide}{}
\begin{center} {\bf How can we obtain tight upper bounds?} \end{center}

The smallest convex set containing all the
rank-one matrices $X$ corresponding to cuts is the {\it cut polytope}:
\[
C_n := \mbox{Conv}\{X : X=v v^T, v \in \{\pm1\}^n\}.
\]
Maximizing $\trace Q X$ over all $X \in C_n$ would give us exactly $\mu^{*}$.

However, it is not known how to optimize in polynomial-time over $C_n$.
\end{slide}

\begin{slide}{}
\begin{center} {\bf How can we obtain tight upper bounds?} \end{center}

One way is to find a convex set $F_n$ such that $C_n \subseteq F_n$
and $F_n \backslash C_n$ is as "small" as possible.

%Previous to this work, the best known bound followed from the
%approximation algorithm of Goemans~\&~Williamson.

Define ${\cal E}_n$ to be the feasible set of MC2
without the rank-one constraint:
\[
{\cal E}_n := \{X \in \Sn : \diag(X)= e, X\succeq 0 \}.
\]

Goemans~\&~Williamson consider the semidefinite program:

$(\mbox{SDP1}) \quad
\begin{array}{ccl}
\nu_1^{*} = &\max  & \trace Q X \\
            &\mbox{s.t.} & X \in {\cal E}_n.\\
 \end{array}
$

Since SDP1 is a relaxation of MC ($C_n \subseteq {\cal E}_n$),
$\nu_1^{*}$ is a bound on $\mu^{*}$.
\end{slide}

\begin{slide}{}
Goemans \& Williamson proved that

if $w_{ij} \geq 0\,\,\forall\: i,j$, then
\[
\mu^* \geq \alpha \nu_1^*,
\]
where $\alpha = \min_{0 \leq \theta \leq \pi} \frac{2}{\pi}
 \frac{\theta}{1-\cos \theta}
 \approx 0.87856$.

\vspace{1cm}

Since $\frac{1}{\alpha} \approx 1.13823 \leq 1.14$, this implies
\[
\mu^{*} \leq \nu_1^* \leq 1.14\:\mu^*.
\]
\end{slide}

\begin{slide}{}
Another convex relaxation is the
{\it metric polytope} $M_n$, defined as

$
\begin{array}{l}
M_n := \{X \in \Sn : \diag(X) = e,\:\mbox{and}\: \\
~~~~   X_{ij}+X_{ik}+X_{jk} \geq -1, X_{ij}-X_{ik}-X_{jk} \geq -1, \\
~~~  -X_{ij}+X_{ik}-X_{jk} \geq -1,-X_{ij}-X_{ik}+X_{jk} \geq -1, \\
~~~~    \forall\, 1 \leq i < j < k \leq n \}.
\end{array}
$

These inequalities model the fact that for any three mutually
connected vertices in the graph, it is only possible to cut
either zero or two
of the edges joining them.

It is known that:

$C_n = M_n$ for $n \leq 4$,
but $C_n \varsubsetneq M_n$ for $n \geq 5$.
\end{slide}

\begin{slide}{}
A natural idea is to consider optimizing over ${\cal E}_n \cap M_n$.

\vspace{8mm}

It is conjectured by Laurent, Poljak \& Rendl that

\begin{conj}
The worst case of this relaxation is attained for the complete
graph $K_5$ with $w_{ij} = 1$ for all the edges,
for which the ratio of the optimum over
${\cal E}_n \cap M_n$ to $\mu^*$ is $\frac{25}{24} \approx 1.042$.
\end{conj}

\vspace{8mm}

For the rest of this talk, we show how to obtain a
semidefinite program whose feasible
set corresponds (in a way that is described later)
to a convex set
$F_n$ that is larger than $C_n$ but nonetheless
is {\em strictly} contained in
${\cal E}_n \cap M_n$.
\end{slide}

\begin{slide}{}
Define the linear operators

$\dsvec \pmatrix{\alpha_1 & \alpha_2 & \alpha_4 \cr \alpha_2 & \alpha_3 &
                 \alpha_5 \cr \alpha_4 & \alpha_5 & \alpha_6} =
 \pmatrix{\alpha_1 \cr 2 \alpha_2 \cr \alpha_3 \cr 2 \alpha_4
           \cr 2 \alpha_5 \cr \alpha_6}$
\hspace{1cm} and

$\sMat \pmatrix{\alpha_1 \cr \vdots \cr \alpha_6} =
 \pmatrix{\alpha_1 & \alpha_2 & \alpha_4 \cr \alpha_2 & \alpha_3 & \alpha_5 \cr
          \alpha_4 & \alpha_5 & \alpha_6}
$.

These are defined so that, for the appropriate inner products,
\[ <X,\sMat(y)>\, = \, <\dsvec(X),y>\,\,\mbox{for all}\: X \in \Sn, y. \]
\end{slide}

\begin{slide}{}
Consider again $X = v v^T, v \in \{\pm1\}^n$, so $X_{ij} = v_i v_j$.

Let $x$ satisfy $X = \sMat(x)$. Then the matrix
\[
Y = \pmatrix{ 1 \cr x} {\pmatrix{ 1 \cr x}}^T =
    \pmatrix{1 & x^T \cr x & x x^T}
\]
has all its entries equal to $\pm 1$, and is positive semidefinite.

Furthermore,
\begin{itemize}
\item Each element of $\diag(Y)$ equals $(X_{ij})^2$ for some pair $i,j$,
	therefore $\diag(Y) = e$;
\item $Y_{0,\frac{i(i+1)}{2}}=1, i=1, \ldots , n$;
\item $X_{ij} = v_i v_j = v_i v_k^2 v_j = X_{ik} X_{kj}$, therefore
       $Y_{0,T(i,j)} = Y_{T(i,k),T(k,j)}, 
	k=1,\ldots,n, \,\,\forall\,1\leq i < j \leq n$,
%\item and clearly $Y \succeq 0$ holds.
\end{itemize}

where the indices $T(i,j)$ are appropriately defined.
\end{slide}

\begin{slide}{}
So consider the semidefinite program SDP2:

$\begin{array}{ccl}
   \mu^* \leq  \nu_2^* =
    &\max & \trace H_Q Y\\
  &\mbox{s.t.}& \diag(Y) = e\\
  &    & Y_{0,t(i)}=1, i=1, \ldots , n\\
  &    & Y_{0,T(i,j)} = Y_{T(i,k),T(k,j)}, \\
  &    & ~~~~~~~~~~~~~~~~~ k=1,\ldots,n, \,\,\forall\,1\leq i < j \leq n\\
  &    & Y \succeq 0, Y \in {\cal S}^{t(n)+1},
\end{array}
$

where $H_Q = \pmatrix{0 & \frac 12 \dsvec(Q)^T\cr
                       \frac 12 \dsvec(Q)  & 0\cr}$,

\vspace{3mm}

$
T(i,j) := \left\{
\begin{array}{l}
t(j-1)+i, \,\mbox{if}\,\, i \leq j \\ t(i-1)+j,\,\,\mbox{otherwise},
\end{array} \right.
$
and $t(i) = \frac{i(i+1)}{2} = \pmatrix{i+1 \cr 2}$.
\end{slide}

\begin{slide}{}
\begin{lem}
Suppose that $Y = \pmatrix{1 & x^T \cr x & \bar{Y}}$
is feasible for SDP2. Then
\[ \diag(\sMat (x)) = e. \]
\end{lem}

\begin{lem}
Suppose that $Y = \pmatrix{1 & x^T \cr x & \bar{Y}}$
is feasible for SDP2. Then
\[  \sMat (x) \succeq 0.  \]
\end{lem}

Hence,

every feasible $Y$ for SDP2 gives us $\sMat(x)$ feasible for SDP1.
\end{slide}

\begin{slide}{}
So if $Y^* = \pmatrix{1 & {x^*}^T \cr x^* & {\bar{Y}}^*}$ is
optimal for SDP2, then

$
\begin{array}{rcl}
\nu_2^* & = & \trace H_Q\,Y^* \\
        & = & \dsvec(Q)^T x^* \\
        & = & <\dsvec(Q), x^*> \\
        & = & <Q, \sMat(x^*)> \\
        & = & \trace Q \, \sMat(x^*) \\
        & \leq & \nu_1^*. \\
\end{array}
$
 
\vspace{5mm}

\begin{thm}
The optimal values satisfy
\[ \label{eq:ineqeq}
 \nu_2^* \leq  \nu_1^* \quad \mbox{and} \quad
\nu_2^* = \nu_1^* \Rightarrow \nu_2^* =  \mu^*.
\]
\end{thm}
\end{slide}

\begin{slide}{}
The linear operator $\sMat$ maps the feasible set of
SDP2 into $\Sn$ by defining
\[
F_n := \{ X \in \Sn : X = \sMat(Y_{0,1:t(n)}), Y\,\,
\mbox{feasible for SDP2} \}.
\]

The set $F_n$ is convex, and
$C_n \subseteq F_n \subseteq {\cal E}_n \cap M_n$ holds.

So $F_n = C_n$ for $n \leq 4$, and:

\begin{thm}
$C_n \varsubsetneq F_n \varsubsetneq {\cal E}_n \cap M_n$ for $n \geq 5$.
\end{thm}
\end{slide}

\begin{slide}{}
\begin{center} {\bf Some Numerical Results} \end{center}

{\small
\begin{tabular}{|c|c|c|c|c|c|c|}\hline
$\mu^*$ & SDP1 & SDP2 & SDP1 plus  & SDP3 & Graph \\
        & bound & bound &  all triangle & bound & \\
        & & & inequalities & & \\
\hline \hline
4 & 4.5225 & 4.2889 & 4.0000 & 4.0000 & 5-cycle \\
  & $\rho$ = 0.8845 & $\rho$ = 0.9326 & $\rho$ = 1.0000 & $\rho$ = 1.0000
  & $w_{ij} = 1$ \\
\hline
88 & 90.3919 & 89.5733 & 88.0029 & 88.0000 & $G$ def. \\
   & $\rho$ = 0.9735 & $\rho$ = 0.9824 & $\rho$ = 1.0000 & $\rho$ = 1.0000
   & by $A_1(G)$ \\
\hline
9.28 & 9.6040 & 9.4056 & 9.2961 & 9.2800 & $K_5$ def.  \\
& $\rho$ = 0.9663 & $\rho$ = 0.9866 & $\rho$ = 0.9983 & $\rho$ = 1.0000
& by $A_2$ \\
\hline
6 & 6.2500 & 6.2500 & 6.2500 & 6.2500 & $K_5$ \\
  & $\rho$ = 0.9600 & $\rho$ = 0.9600 & $\rho$ = 0.9600 & $\rho$ = 0.9600
  & $w_{ij} = 1$ \\
\hline
\end{tabular}
}
\end{slide}

\end{document}