\documentclass[notes]{beamer}
\usepackage{graphics,graphicx} 
\usepackage{xcolor} 
\usepackage{epsfig}

\definecolor{rblue}{rgb}{.255,.41,.884} % RoyalBlue of svgnames
\definecolor{rred}{rgb}{1, 0, 0} % Red of svgnames
\definecolor{lgreen}{rgb}{.196,.804,.196} % LimeGreen of svgnames
\definecolor{oyellow}{rgb}{1,.648,0} % Orange of svgnames


\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}
\newcommand{\bsl}{\begin{slide}}
\newcommand{\esl}{\end{slide}}
\newcommand{\BB}{{\mathcal B} }
\newcommand{\uu}{{\bf u}}
\newcommand{\A}{{\mathcal A\,}}
\newcommand{\SDP}{{\bf{\rm SDP\,}}}
\newcommand{\trace}{{\rm trace\,}}
\newcommand{\Sn}{{\mathcal S^n\,}}
\newcommand{\rank}{{\rm rank\,}}
\newcommand{\PP}{{\mathcal P} }
\newcommand{\DD}{{\mathcal D} }
\newcommand{\corr}{{\rm corr\,}}
\newcommand{\its}{{\rm its\,}}
\newcommand{\stitle}[1]{\begin{center} {\bf\large {#1} } \end{center}}


\mode<presentation>
{
  \usetheme{Warsaw}
  \usecolortheme{seahorse}
  \setbeamercovered{transparent}
}
\beamertemplatenavigationsymbolsempty

\usefoottemplate{\hfil\tiny{\color{black!90}\insertframenumber}} 

\usepackage[english]{babel}
\usepackage[latin1]{inputenc}

\usepackage{times}
\usepackage[T1]{fontenc}

\title{Generating and Measuring Instances of Hard Semidefinite Programs}

\author{Hua Wei and Henry Wolkowicz}
\institute{ICCOPT II \&  MOPTA-07}

\date{Monday, August 13, 2007}

\subject{Talks}

\def\defn#1{{\color{red} #1}}

\begin{document}

\begin{frame}
  \titlepage
\end{frame}

\begin{frame}
  \frametitle{Outline}
  \tableofcontents
\end{frame}

\section{SDP Background}

\subsection{Problem Statement}

\begin{frame}
\frametitle{\SDP Models}
\begin{block}{Primal \SDP}
\[
(PSDP) \qquad
        \begin{array}{ccl}
        p^* :=&\min   & \trace CX\\
        &\mbox{s.t.} & \A (X) = b \\
        &     &  X \succeq  0
        \end{array}
\]
\end{block}
\begin{block}{Dual \SDP}
\[
(DSDP) \qquad
        \begin{array}{ccl}
        d^* :=&\max   & b^Ty\\
        &\mbox{s.t.} & \A^* (y) + Z = C \\
        &     &  Z \succeq  0,
        \end{array}
\]
\end{block}

\pause\uncover{
\vskip12pt
where $C,X,Z \in \Sn$,
$n \times n$ real symmetric matrices,
$y,b\in \Re^m$, ($\succeq$) $\succ$ denotes positive
(semi)definiteness.\\
$\PP^*$ and $\DD^*$ -  are sets of optimal primal and dual solutions 
}

\end{frame}

\subsection{Theoretical/Numerical Difficulties in \SDP}

\begin{frame}


\frametitle{(Near) Loss of Slater Condition/Strict Feasibility}

\pause\uncover{
\begin{block}{Primal/Dual Slater}
\begin{itemize}
\item    $\A (X) = b,  X \succ  0$
\item    $\A^* (y) \prec C$
\end{itemize}
\end{block}
}


\pause\uncover{
\begin{block}{Theoretical/Numerical Difficulties}
\begin{itemize}
\item   Primal Slater condition implies strong duality, i.e. zero duality gap
{\color{red}AND} dual attainment.
\item    (Near) loss of strict feasibility is used as a measure in
complexity theory. (e.g. Renegar/95, Freund/01, Lara and Tuncel/02)
\pause\uncover{
\item   
{\color{lgreen}(Near) loss of strict feasibility correlates with number of
iterations and loss of accuracy in interior-point methods
}
(e.g. Freund/Ordonez/Toh 2006)
}
\end{itemize}
\end{block}
}


\end{frame}


\begin{frame}


\frametitle{Loss of Strict Complementarity, (SC)}

\begin{block}{Strict Complementary Optimal Primal-Dual Pair}
\begin{itemize}
\item    There exists an optimal primal-dual pair $X,Z$ such that
\[
X+Z \succ 0
\]
\end{itemize}
\end{block}


\pause\uncover{
\begin{block}{Theoretical Difficulties}
\begin{itemize}
\item   Convergence proofs for asymptotic quadratic superlinear
convergence require SC.
\item   Proofs of convergence to the analytic center require SC
\end{itemize}
\end{block}
}

\pause\uncover{
\begin{block}{\color{red}Numerical Difficulties ???}
increased number of iterations? loss of accuracy?
\end{block}
}


\end{frame}




\begin{frame}

\frametitle{Other Theoretical/Numerical Difficulties}

\begin{itemize}
\item    The Primal-Dual: {\color{red}Feasibility , Complementary Slackness
 Optimality Conditions} are overdetermined; symmetrizations to use
Newton's method result in ill-posed problems.
\item
High accuracy solutions are hard/impossible to obtain; sparsity is hard
to exploit; large scale is still an open area of research. 

\end{itemize}



\end{frame}





\section{Hard SDP Instances}

\subsection{Definitions}

\begin{frame}

\frametitle{Hard SDP Instances/Definitions}


\pause\uncover{
\begin{block}{Maximal Complementary Solution Pair:}
\begin{itemize}
\item
A primal-dual pair of optimal solutions
$(\bar X,\bar Z ) \in \mathcal P^* \times \mathcal D^*$ 
is called a
\underline{{\em maximal complementary solution pair}}
to the problems (PSDP) and (DSDP), if the pair maximizes the sum 
$\rank(X)+\rank(Z)$ over all primal-dual optimal solution pairs
$(X,Z)$. 
\end{itemize}
\end{block}
}

\pause\uncover{
\begin{block}{Strict Complementarity Nullity:}
\begin{itemize}
\item
$g=n-\rank(\bar X)-\rank(\bar Z)$, where $(\bar X,\bar Z)$ is a 
maximal complementary solution pair
 
\end{itemize}
\end{block}
}

\pause\uncover{
\begin{block}{Hard \SDP Instances:}
\begin{itemize}
\item
problems where strict complementarity fails (nullity is nonzero)

\end{itemize}
\end{block}
}

\end{frame}




\subsection{Generating Hard \SDP Instances}

\begin{frame}

\frametitle{Algorithm for Given Nullity $g$}


\begin{block}{Algorithm}
\begin{itemize}
\item 
Given: positive integers $r>0$ and $m>1$: the rank of an optimum $X$ and the
number of constraints, resp.
\item 
Let $Q= [ Q_P | Q_N | Q_D ]$ be an orthogonal matrix, where
the dimensions of $Q_P$, $Q_N$, $Q_D$ are 
$n\times r$, $n\times g$,  $n\times (n- r-g)$, respectively, and $r>0$.
Construct positive semidefinite matrices $X$ and $Z$ as follows:
$$
X:= Q_P D_X Q_P^T ,\hspace{1cm} 
Z:= Q_D D_Z Q_D^T,
$$
where $D_X$ and $D_Z$ are diagonal positive definite.
\item cont...


\end{itemize}
\end{block}

\end{frame}




\begin{frame}

\frametitle{Algorithm cont...}


\begin{block}{Algorithm cont...}
\begin{itemize}

\item 
Define
\[
A_1 = [Q_P |Q_N | Q_D]
\begin{bmatrix} 0 & 0  & Y_2^T \cr
    0     & Y_1  & Y_3^T \cr
    Y_2 & Y_3 & Y_4 \end{bmatrix}
[Q_P |Q_N | Q_D]^T,
\]
where $Y_1$, $Y_2$, $Y_3$, and $Y_4$ are block matrices of appropriate
dimensions, $Y_1\succ 0$, $Y_4$ symmetric, and $Q_DY_2 \neq 0$.
\item 
Choose $A_i \in \Sn, i = 2, \dots, m$, such that
$\{A_1Q_P, A_2Q_P, \dots, A_mQ_P\}$ is a  linearly independent
set. (Note that $A_1Q_P = Q_D Y_2 \neq 0$.)
\item 
Set \hspace{1cm}
$b := \A(X), \hspace{1cm} C:= \A^*(y) + Z,$\\
with $ ~y \in \Re^m $ randomly generated.
\end{itemize}

\end{block}

\end{frame}


\begin{frame}

\frametitle{Theorem for Generating Hard Instances}


\begin{block}{Theorem}
The data $(\A, b, C)$ constructed
in the above algorithm gives a {\em hard} \SDP instance with a
strict complementarity nullity $g$.
\end{block}


\begin{block}{Proof Outline}
\begin{itemize}
\item
Step 2 guarantees $X,Z \succeq 0, XZ=0$ but strict complementarity fails.
\item
step 5 guarantees primal-dual
feasibility, i.e. XZ are an optimal pair. 
\item
Steps 3,4 guarantee $X,Z$ are a maximal complementary solution pair.
\end{itemize}
\end{block}

\end{frame}




\subsection{Generating Hard \SDP Instances with Slater Condition}

\begin{frame}

\frametitle{Generating Hard Instances with Slater Condition}


\begin{block}{Corollary}
With data $(\A, b, C)$ constructed
using above algorithm:
\begin{enumerate}
\item If the following additional condition
on $A_2$ is satisfied
\[
 [Q_P |Q_N ]^TA_2 [Q_P |Q_N ] \succ 0,
\]
then Slater's condition holds for the dual program (DSDP).
\item If the following additional conditions
on  $A_i, i=1,\ldots,m$, are satisfied,
\[
\begin{array}{ccl}
& \trace Y_4=-\trace Y_1 \\
\alpha > 0,  & \trace A_i X =\alpha \trace A_i,&  i=2, \ldots, m, 
\end{array}
\]
then $\hat X= \alpha I\succ 0$ is feasible for (PSDP).
\end{enumerate}




\end{block}

\end{frame}




\section{Measures for Strict Complementarity Nullity}

\begin{frame}

\frametitle{Measures $g_t$, $g_s$, $\kappa$}


\begin{block}{$g_t$, $g_s$, $\kappa$}
\begin{itemize}
\item 
$ g_t:= |\{ w^d_i: T_l <  w^d_i < T_u \}  |   $,\\
where $w^d = \frac 12\lambda \left(X^{-1}Z + ZX^{-1}\right)$;
$T_l$,  $T_u$ are two tolerances.
($O(1)$ indicates  nullity; $0,\infty$ otherwise)
\item $g_s : = | \{ w^s_j : w^s_j \leq T\} |$,
where $w^s := \frac 1{2 \sqrt \mu}
\lambda \left(X+ Z\right)$; $T$ is a tolerance.
\item (proposed by Freund, Ord{\'o}{\~n}ez, and Toh.)
given tolerance $T$, $T^s:=\{j:w^s_j\leq T\}$.,
\begin{equation}
  \label{eq:kp51104e}
 \kappa := - \sum_{j\in T^s} \ln(w^s_j)  / |\{j: w^s_j \leq T\} |.
\end{equation}
[small (large) for str. compl holds (fails) ]
\end{itemize}


\end{block}

\end{frame}




\section{Numerical Results}
\subsection{Randomly Generated Instances}

\begin{frame}

\frametitle{Randomly Generated Instances}


\begin{block}{Random Instances}

\begin{itemize}
\item We generate 100 instances for each nullity value 0:23.
\item The Slater conditions hold for both primal and dual.
\item The x-axis of each figure represents the complementarity nullity
 ranging from 0 to 23.
\item 
On y-axes from left to right:
\begin{quote}
iteration numbers;
number of instances that satisfy the desired accuracy;
measure $g_t$;
measure $g_s$;
measure $\kappa$;
local convergence rate.
\end{quote}
\end{itemize}

\end{block}

\end{frame}


\subsection{Plots}
\begin{frame}

\frametitle{Plots}

\epsfxsize=240pt
%\centerline{\epsfbox{../program/log/mnat10_30_8_1.eps}}
\centerline{\epsfbox{SDPT3m10_n30_a8_t100_pv1_dv1_psla1_dsla1_err1.eps}}
\centerline{\epsfbox{SDPT3m10_n30_a10_t100_pv1_dv1_psla1_dsla1_err1.eps}}
\centerline{\epsfbox{SDPT3m10_n30_a12_t100_pv1_dv1_psla1_dsla1_err1.eps}}
{
Slater conditions hold; stop tolerances: $10^{-8}, 10^{-10}, 10^{-12}$
(using average of instances that attained desired accuracy)
}


\end{frame}




\begin{frame}

\frametitle{Observations}

\begin{block}{Observations}
\begin{itemize}
\item There is a {\em strong correlation} between the iteration number to 
achieve the desired stopping tolerance and the
  size of the complementarity nullity, when the accuracy requirement is
  high. 
\item Large nullity instances cause problems for SDPT3 solver.
\item The measures $g_t,~g_s$ and $\kappa$ all improve as the
accuracy increases. Measure $\kappa$ correlates well with the iteration number.
\item
Local asymptotic convergence rate is slower when nullity is larger.
\end{itemize}
\end{block}

\end{frame}

\subsection{Correlation Matrix}
\begin{frame}
\frametitle{Correlation Matrix}


The local convergence rate is for stop tolerance is $10^{-12}$.
{\small
\begin{center}
  \begin{tabular}{|c|cccccc|}
\hline
&Nullity & Iterations & $g_t$ & $g_s$ & $\kappa$ & Cvg. Rate \\
\hline
Nullity& 1.0000& 0.8341& 0.9921& 0.9993& 0.8430& 0.9263 \\ 
Iterations& 0.8341& 1.0000& 0.8417& 0.8191& 0.9958& 0.9763 \\ 
$g_t$& 0.9921& 0.8417& 1.0000& 0.9897& 0.8567& 0.9274 \\ 
$g_s$& 0.9993& 0.8191& 0.9897& 1.0000& 0.8280& 0.9164 \\ 
$\kappa$& 0.8430& 0.9958& 0.8567& 0.8280& 1.0000& 0.9785 \\ 
Cvg. Rate& 0.9263& 0.9763& 0.9274& 0.9164& 0.9785& 1.0000 \\ 
\hline
 \end{tabular}
\end{center}
}
\begin{block}{}
\begin{itemize}
\item nullity correlates well with iterations as well as
local convergence rate. 
\item The measure $\kappa$ has highest correlation
with iterations. 
\end{itemize}
\end{block}
\end{frame}


\begin{frame}
\frametitle{SDPT3 Iteration Numbers on SDPLIB Instances}

\begin{block}{}
\begin{itemize}
\item Measures $g_t$, $g_s$ and $\kappa$ are applied on the SDPLIB instances.
\item 
We only consider those
SDP instances (47 such instances),
where the error obtained was less than $10^{-7}$.
The correlation between the measures and
the iteration numbers are:
$$ \corr(g_t, \its) = 0.1472,~ \corr(  g_s , \its) = 0.4509,
$$
$$~\mbox{and}~
 \corr(\kappa, \its) = 0.4371.
$$
\item
Low accuracy in solutions yield low correlations.
\end{itemize}
\end{block}

\end{frame}


\subsection{SDPLIB Instances}
\begin{frame}
\frametitle{SDPLIB Instances}

\begin{figure}[htb]
\epsfxsize=300pt
%\centerline{\epsfbox{../program/log/sdpcorr.eps}}
\centerline{\epsfbox{sdpcorr.eps}}
\caption{
Scatter plots of $g_t,g_s,\kappa$ versus \# iterations 
for SDPLIB instances with attained tolerance $ < 10^{-7}$.
}
\end{figure}

\end{frame}


\section{Conclusion}
\begin{frame}
\frametitle{Conclusion}

\begin{block}{Generating Hard Instances}
We have presented an algorithm for generating hard \SDP instances, i.e.
problem instances where
we can control the complementarity nullity, $g$.
\end{block}


\begin{block}{Two Empirical Measures for $g$}
We introduced two empirical measures $g_t$ and $g_s$ for $g$. 
These two measures provide
accurate measurement of $g$ if high accuracy solutions are used.

\end{block}


\begin{block}{Measures: Positive Correlation with Numerical
Difficulties}
 The numerical tests show: 
number of iterations and the numerical accuracy
are positively correlated to $g$.
\end{block}

\end{frame}


%%%\subsection{Reformulation and Relaxation}
%%%
%%%\begin{frame}
%%%\frametitle{Reformulation of Max-Cut Problem}
%%%
%%%We reforumlate the Max-Cut problem:
%%%\pause\uncover{
%%%    \begin{block}{Problem: Reformulation of Max-Cut Problem}
%%%Given any cut $C$, define
%%%    \[x:=(x_{1},\hdots,x_{n})^{T},\ \ x_{i}:= \left\{\begin{array}{cc}
%%%                                                      1 & i\in C \\
%%%                                                      -1 & i\not \in C
%%%                                                    \end{array}
%%%    \right.\]
%%%
%%%\pause\uncover{
%%%    \[
%%%    \begin{array}{rl}
%%%    \text{Maximize} & t=\frac{1}{2} \sum_{i<j} w_{ij}(1-x_{i}x_{j})\\
%%%    \text{subject to} & x_{i}\in\{-1,1\} \ \ \forall\ i\in V.
%%%    \end{array}
%%%    \]
%%%}
%%%    \end{block}
%%%    
%%%    }
%%%    
%%%\pause\uncover{
%%%    Let $e:= (1,1,\hdots,1)^{T}$, where $e \in \mathbb{R}^n$.}\pause\uncover{
%%%    \[L:= \frac{1}{4}\left(Diag(We)-W\right).\]
%%%}\end{frame}
%%%
%%%\begin{frame}
%%%\frametitle{Reformulation of Max-Cut Problem}
%%%\framesubtitle{Some Equalities for $t$}
%%%
%%%\hyperlink{post_equalities}{\beamergotobutton{Skip long string of equalities for $t$}}
%%%
%%%\small
%%%    \begin{eqnarray*}
%%%     t&=&\frac{1}{2} \sum_{i<j} w_{ij}(1-x_{i}x_{j}) \pause\uncover{=\frac{1}{4} \left(2\left(\sum_{i<j} w_{ij}\right)-2\left(\sum_{i<j} w_{ij}x_{i}x_{j}\right)\right)\\}
%%%\pause\uncover{       &=&\frac{1}{4}\left(2\left(\sum_{i<j} w_{ij}x_{i}^{2}\right)+\left(\sum_{i} w_{ii}- w_{ii}\right)-2\left(\sum_{i<j} w_{ij}x_{i}x_{j}\right)\right)\\}
%%%\pause\uncover{       &=&\frac{1}{4}\left(\left(\sum_{i}\sum_{j} w_{ij}x_{i}^{2}\right)-\left(\sum_{i}\sum_{j} w_{ij}x_{i}x_{j}\right)\right)\\}
%%%\pause\uncover{     &=&\frac{1}{4}\left(\left(\sum_{i}\left(\sum_{j} w_{ij}\right)x_{i}^{2}\right)-x^{T}Wx\right)= \pause\uncover{\frac{1}{4}\left(\left(\sum_{i}(We)_{i} x_{i}^{2}\right)-x^{T}Wx\right)\\}}
%%%\pause\uncover{       &=&\frac{1}{4}\left(x^{T}Diag(We)x-x^{T}Wx\right) \pause\uncover{=x^{T}Lx}}
%%%    \end{eqnarray*}
%%%\end{frame}
%%%
%%%
%%%\begin{frame}
%%%\frametitle{Reformulation and Relaxation of Max-Cut Problem}
%%%
%%%\hypertarget{post_equalities}{}
%%%\begin{itemize}
%%%\item {\small
%%%$t=x^{T}Lx=trace(x^{T}Lx)=trace(x^{T}(Lx))=trace((Lx)x^{T})=trace(LX)=L\bullet X$}, \pause\uncover{
%%%where $X=xx^{T}$ is a real symmetric matrix, }\pause\uncover{$\Longrightarrow$ $X \succeq 0$.}
%%%\pause\uncover{\item $diag(X)=e$ $\Longleftrightarrow$ $x_{i}^{2}=1$ $\Longleftrightarrow$ $x_{i}\in \{-1,1\}$.}
%%%\end{itemize}
%%%
%%%\pause\uncover{
%%%    \begin{block}{Lemma}
%%%      $X=X^T \succeq 0, \text{rank}(X)=1 \Longleftrightarrow X=xx^{T}$
%%%    \end{block}
%%%}
%%%\pause\uncover{$W$ is the edge-weight matrix }\pause\uncover{$\rightsquigarrow L = \frac{1}{4}\left(Diag(We)-W\right)$}\pause\uncover{\ $\rightsquigarrow$
%%%
%%%  \begin{overprint}
%%%
%%% \onslide<-9>   \begin{block}{Problem: Equivalent Reformulation of Max-Cut Problem}
%%%    \[\begin{array}{rl}
%%%    \text{Maximize} & L\bullet X\\
%%%    \text{subject to} & diag(X)=e, \only<-8>{rank(X)=1}\only<9>{{\color{red} rank(X)=1}} ,\text{ and } X\succeq 0.
%%%    \end{array}\]
%%%    \end{block}
%%%
%%%\onslide<10>
%%%    \begin{exampleblock}{Problem: SDP Relaxation of Max-Cut Problem}
%%%    \[\begin{array}{rl}
%%%    \text{Maximize} & L\bullet X\\
%%%    \text{subject to} & diag(X)=e\text{ and } X\succeq 0.\phantom{rank(X)=1. ,}
%%%    \end{array}\]
%%%    \end{exampleblock}
%%%\end{overprint}
%%%}
%%%
%%%\end{frame}
%%%
%%%\subsection{Setting up an Instance}
%%%
%%%\begin{frame}[fragile]
%%%\frametitle{Setting up an Instance}
%%%
%%%    We setup an instance of the Max-Cut problem in MATLAB with the following code:
%%%\bigskip
%%%\hrule
%%%\begin{verbatim}
%%%% Fix the dimension (number of vertices in graph)
%%%n=60;
%%%
%%%% Generate a weighted graph
%%%W=sprandsym(n,.5); W(1:n+1:n^2)=zeros(1,n);
%%%
%%%% Calculate the Laplacian
%%%L=1/4 * (diag(W*ones(n,1))-W);
%%%\end{verbatim}
%%%
%%%\end{frame}
%%%
%%%\section{Solving Using SeDumi}
%%%
%%%\subsection{SeDumi Input Format}
%%%
%%%\begin{frame}[fragile]
%%%\frametitle{Interfacing with SeDumi}
%%%
%%%To be consistent with the notation of SeDumi's documentation and interface, substitute ``$x$'' for ``$z$''.  The SeDumi primal form is
%%%    \[\begin{array}{rl}
%%%    \text{\color{alert} Minimize} & c^{T}z\\
%%%    \text{subject to} & Az=b, \text{ for } z\in \mathcal{K}\\
%%%    \end{array}\]
%%%    where $c,z,b\in\mathbb{R}^{p}$, and $A$ is a $p\times p$ matrix.  In MATLAB,
%%%\bigskip
%%%\hrule
%%%{\small
%%%\begin{verbatim}
%%%c=-L(:); % Format the Laplacian to vector form
%%%
%%%% Translate constraint diag(X)=e into vector format:
%%%A=sparse(1:n,1:n+1:n^2,ones(1,n),n,n^2);
%%%b=ones(n,1);
%%%
%%%% Tell SeDumi that X must be positive semidefinite
%%%K.s=[n];
%%%
%%%[X,Y,INFO] = sedumi(A,b,c,K) % Run SeDumi
%%%\end{verbatim}}
%%%
%%%\end{frame}
%%%
%%%\subsection{Basic Relaxation: Setting up the Input to SeDumi}
%%%
%%%\begin{frame}
%%%\frametitle{Interfacing with SeDumi}
%%%\framesubtitle{A visual summary of $Az = b$}
%%%
%%%%\includegraphics[width=11.7cm]{sedumi_format.pdf}
%%%
%%%\end{frame}
%%%
%%%\subsection{Basic Relaxation: Numerical Results}
%%%
%%%\begin{frame}
%%%\frametitle{Numerical Results: Basic Relaxation $G\big(n, \frac12\big)$}
%%%\begin{columns}
%%%\column{1.0in}
%%%{\tiny
%%%\begin{tabular}{|r|l|} \hline
%%% n & {\bf Ratio}\\ \hline
%%% 50 &  6.292239e-01\\ \hline
%%% 60 &  6.202113e-01\\ \hline
%%% 70 &  6.067923e-01\\ \hline
%%% 80 &  6.074731e-01\\ \hline
%%% 90 &  5.980219e-01\\ \hline
%%% 100 &  5.894269e-01\\ \hline
%%% 110 &  5.849831e-01\\ \hline
%%% 120 &  5.837704e-01\\ \hline
%%% 130 &  5.793048e-01\\ \hline
%%% 140 &  5.777026e-01\\ \hline
%%% 150 &  5.749815e-01\\ \hline
%%% 160 &  5.715093e-01\\ \hline
%%% 170 &  5.702395e-01\\ \hline
%%% 180 &  5.686022e-01\\ \hline
%%% 190 &  5.675917e-01\\ \hline
%%% 200 &  5.654331e-01\\ \hline
%%% 250 &  5.591398e-01\\ \hline
%%% 300 &  5.538571e-01\\ \hline
%%% 350 &  5.506719e-01\\ \hline
%%% 400 &  5.472742e-01\\ \hline
%%% 450 &  5.441005e-01\\ \hline
%%% 500 &  5.422019e-01\\ \hline
%%% 600 &  5.390324e-01\\ \hline
%%% 700 &  5.359528e-01\\ \hline
%%% 800 &  5.337012e-01\\ \hline
%%% 900 &  5.320470e-01\\ \hline
%%% 1000 &  5.303538e-01\\ \hline
%%% \end{tabular}
%%%}
%%%
%%%\column{3.5in}
%%%%\includegraphics[width=3.0in]{basic_relaxation.jpg}
%%%\end{columns}
%%%
%%%\end{frame}
%%%
%%%\section{Improving the Implementation and Results}
%%%
%%%\subsection{Strengthening the Relaxation: Triangle Inequalities}
%%%
%%%\begin{frame}
%%%\frametitle{Triangle Inequalities}
%%%
%%%An idea proposed by Poljak and Rendl (1995), and further developed by Helmberg, Rendl, Vanderbei and Wolkowicz (1996):
%%%\vskip10pt
%%%For each triple, $x_{i},x_{j},x_{k}\in\{-1,1\}$ we have
%%%\begin{eqnarray}
%%%\label{additionalConstraints1}
%%%  x_{ij}+x_{jk}+x_{ki}&\geq& -1\\
%%%  x_{ij}-x_{jk}-x_{ki}&\geq& -1\\
%%%  -x_{ij}+x_{jk}-x_{ki}&\geq& -1\\
%%%  -x_{ij}-x_{jk}+x_{ki}&\geq& -1.
%%%\label{additionalConstraints4}
%%%\end{eqnarray}
%%%\pause\uncover{
%%%With (\ref{additionalConstraints1})-(\ref{additionalConstraints4}), we have the {\color{blue} strengthened} SDP relaxation:
%%%\begin{exampleblock}{Problem: Strengthened Relaxation of Max-Cut Problem}
%%%    \[\begin{array}{rl}
%%%    \text{Maximize} & L\bullet X\\
%%%    \text{subject to} & diag(X)=e, X\succeq 0, \textrm{ and }(\ref{additionalConstraints1})-(\ref{additionalConstraints4}).
%%%    \end{array}\]
%%%\end{exampleblock}}
%%%\end{frame}
%%%
%%%\begin{frame}
%%%\frametitle{Triangle Inequalities}
%%%\framesubtitle{Replacing Inequalities (\ref{additionalConstraints1})-(\ref{additionalConstraints4}) with Equalities for SeDumi's Input Format}
%%%Introduce {\color{blue} slack variables} $s_{ijk\ell}\geq 0$ to get equalities for SeDumi.
%%%\begin{eqnarray*}
%%%  x_{ij}+x_{jk}+x_{ki}-s_{ijk1}&=& -1\\
%%%  x_{ij}-x_{jk}-x_{ki}-s_{ijk2}&=& -1\\
%%%  -x_{ij}+x_{jk}-x_{ki}-s_{ijk3}&=& -1\\
%%%  -x_{ij}-x_{jk}+x_{ki}-s_{ijk4}&=& -1
%%%\end{eqnarray*}
%%%\pause\uncover{
%%%\begin{itemize}
%%%\item Considering (\ref{additionalConstraints1})-(\ref{additionalConstraints4}) when a pair of $i,j,k$ are the same is redundant.
%%%\pause\uncover{\item So we are concerned with ``only'' $N := 2n(n-1)(n-2)/3$ slack variables.}
%%%\end{itemize}
%%%}
%%%\end{frame}
%%%
%%%\begin{frame}
%%%\frametitle{Triangle Inequalities}
%%%\framesubtitle{A visual summary of $Az = b$}
%%%\begin{center}
%%%%\includegraphics[width=8.8cm]{triangle_format.pdf}
%%%\end{center}
%%%\end{frame}
%%%
%%%\begin{frame}
%%%\frametitle{Numerical Results: Triangle Relaxation $G\big(n, \frac12\big)$}
%%%
%%%\begin{columns}
%%%\column{2.4in}
%%%{\small
%%%\begin{tabular}{|c|c|c|} \hline
%%% {\bf $n$} & {\bf Ratio 1} & {\bf Ratio 2}\\ \hline
%%% 5& 7.142857e-01& 7.142857e-01 \\ \hline
%%% 6& 7.500000e-01& 7.500000e-01 \\ \hline
%%% 7& 7.177745e-01& 6.875000e-01 \\ \hline
%%% 8& 7.417858e-01& 7.368421e-01 \\ \hline
%%% 9& 7.570369e-01& 7.272727e-01 \\ \hline
%%% 10& 6.978259e-01& 6.709667e-01 \\ \hline
%%% 11& 7.433614e-01& 7.241379e-01 \\ \hline
%%% 12& 6.845083e-01& 6.808511e-01 \\ \hline
%%% 13& 6.986989e-01& 6.862745e-01 \\ \hline
%%% 14& 6.655176e-01& 6.615384e-01 \\ \hline
%%% 15& 6.613215e-01& 6.433655e-01 \\ \hline
%%%\end{tabular}
%%%}
%%%\column{3.0in}
%%%%\includegraphics[width=2.7in]{tri_relaxation.jpg}
%%%\end{columns}
%%%
%%%\end{frame}
%%%
%%%\subsection{Strengthening the Relaxation: Quadruple Equalities}
%%%
%%%\begin{frame}
%%%\frametitle{Quadruple Equalities}
%%%
%%%An idea of Goemans developed by Anjos and Wolkowicz (2002):
%%%\vskip10pt
%%%
%%%For each quadruple $x_{i},x_{j},x_{j},x_{k}\in \{-1,1\}$ we have:
%%%\begin{equation}\label{quad}
%%%x_{i}x_{j}x_{j}x_{k}=x_{i}x_{j}^{2}x_{k}=x_{i}x_{k}.
%%%\end{equation}
%%%\vskip18pt
%%%\pause\uncover{
%%%With (\ref{quad}), we have the SDP formulation:
%%%
%%%    \begin{exampleblock}{Problem: An Equivalent Formulation of Max-Cut Problem}
%%%    \[\begin{array}{rl}
%%%    \text{Maximize} & L\bullet X\\
%%%    \text{subject to} & diag(X)=e, X\succeq 0,\text{ and } x_{ij}x_{jk}=x_{ik}.
%%%    \end{array}\]
%%%    \end{exampleblock}
%%%}
%%%
%%%
%%%\end{frame}
%%%
%%%\begin{frame}
%%%\frametitle{Second lifting/relaxation}
%%%
%%%After \defn{lifting}
%%%$$Y = \left(
%%%y  y^T\right),\text{ where } y = \text{vec}(X)$$%
%%%
%%%\pause\uncover{
%%%  \begin{overprint}
%%%
%%%\onslide<-3>
%%%We have the max-cut problem:
%%%    \[\begin{array}{rll}
%%%    \text{Maximize} &\left[\begin{array}{cc}L&0\\0&0\end{array}\right] \bullet Y = L \bullet Y_{11}\\
%%%    \text{subject to} & diag(Y)=e& \text{ (S1)}\\
%%%    & Y\succeq 0 &\text{ (S2)}\\
%%%    & Y_{11} = Y_{ii}\ \ \forall i=2,\ldots, n& \text{ (S3)}\\
%%%    & \text{diag}(Y_{ij}) = Y_{ii}^{(i,j)}e &\text{ (S4)}\\
%%%    & Y_{ij}e_j = Y_{11}e_i\ \ \forall j=2,\ldots n,\ i<j &\text{ (S5)}\\
%%%    & \only<-2>{\text{rank}(Y) = 1.}\only<3>{{\color{red} \text{rank}(Y) = 1}.}  &\text{ (S6)}
%%%    \end{array}\]
%%%
%%%\onslide<4->
%%%We have the max-cut {\bf \color{blue} relaxation}:
%%%    \[\begin{array}{rll}
%%%    \text{Maximize} &\left[\begin{array}{cc}L&0\\0&0\end{array}\right] \bullet Y = L \bullet Y_{11}\\
%%%    \text{subject to} & diag(Y)=e& \text{ (S1)}\\
%%%    & Y\succeq 0 &\text{ (S2)}\\
%%%    & Y_{11} = Y_{ii}\ \ \forall i=2,\ldots, n& \text{ (S3)}\\
%%%    & \text{diag}(Y_{ij}) = Y_{ii}^{(i,j)}e &\text{ (S4)}\\
%%%    & Y_{ij}e_j = Y_{11}e_i\ \ \forall j=2,\ldots n,\ i<j &\text{ (S5)}\\
%%%    \end{array}\]
%%%    
%%%\end{overprint}
%%%
%%%\pause\uncover<5>{{
%%%\begin{block}{Theorem}
%%%The second lifting relaxation provides a tighter upper bound.
%%%\end{block}}}
%%%
%%%}
%%%\end{frame}
%%%
%%%\begin{frame}
%%%\frametitle{Tighter Upper Bound Theorem}
%%%%\begin{block}{Theorem}
%%%%The second lifting relaxation provides a tighter upper bound than the first lifting relaxation.
%%%%\end{block}
%%%
%%%\begin{itemize}
%%%\item Suppose that $X^*$ is an optimal solution to the first lifting relaxation.
%%%\begin{itemize}
%%%\pause\uncover{\item If $Rank( X^*)=1$, then we have the optimal solution to the original max-cut problem.}
%%%\pause\uncover{\item If $Rank( X^*)>1$, we will show that after lifting $X^*$ to $\overline{Y}=(yy^T)$, where $y=\text{vec } X^*$, $\overline{Y}$ is not feasible to the second relaxation. 
%%%\begin{itemize}
%%%\pause\uncover{\item By contradiction, we assume that $\overline{Y}$ is feasible to the second relaxation, then it satisfies (S4) and (S5),  which implies that  $X^*_{ik}X^*_{kj}=X^*_{ij}$ for all $i,j,k$.}
%%%\pause\uncover{\item Hence, $X^*=xx^T$, where $x=(X^*_{1k}, X^*_{2k},\cdots, X^*_{nk})$, which contradicts $\text{Rank } X^*>1$.}
%%%\pause\uncover{\item Therefore, $\overline{Y}$ is not feasible to the second lifting relaxation.}
%%%\end{itemize}
%%%}
%%%\end{itemize}
%%%
%%%\pause\uncover{\item On the other hand, if $Y$ is feasible to the second lifting relaxation,  by (S1) and (S2), $diag(Y_{11})=e$ and $Y_{11}\succeq 0$.}
%%%\pause\uncover{\item Then, $Y_{11}$ is feasible to the first lifting relaxation. \ \ \ $\square$}
%%%\end{itemize}
%%%
%%%\end{frame}
%%%
%%%\begin{frame}
%%%\frametitle{Numerical Results: Comparison of Algorithms}
%%%
%%%{\small
%%%\begin{table}
%%%\begin{center}
%%%{\bf Comparison of Algorithm Performance}
%%%\vskip18pt
%%%
%%%\begin{tabular}{lccccrr}
%%%\hline
%%% \multicolumn{1}{c}{relaxation} & n=4   & n = 6        & n = 8        & n = 10 \\ 
%%%\hline
%%% SDP  & 2.00000000 & 6.43225787 & 9.52050490 & 17.0875592 \\
%%% TRI  & 1.99999999 & 5.99999995 & 8.99999986 & 16.9999998 \\
%%% QUAD & 1.99999999 & 5.99999988 & 8.99999900 & 16.9999996
%%%\end{tabular}
%%%\label{Table:S-T-Q-results}
%%%\end{center}
%%%\end{table}
%%%}
%%%\end{frame}
%%%

\begin{frame}
\frametitle{Thanks!! Enjoy ICCOPT/MOPTA}
\vskip20pt
\begin{center}
{\bf \color{alert} Thanks for your attention! \\
   Hope you are enjoying ICCOPT/MOPTA}
\end{center}
\vskip20pt
\titlepage
\end{frame}

\end{document}