%
% iccopt07_talk.tex
%
% This is my talk for the the Boston SIOPT meeting in 2008, May 10-13.
% Based on work done with Levent Tuncel and Henry Wolkowicz
%
% This file requires input from the following files:
%
%
%\documentclass{seminar}
\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

%Beamer loads xcolor package by Uwe Kern, which also supports color
%and pstcol.
%?xcolor? definition
\xdefinecolor{lavendar}{rgb}{0.8,0.6,1}
\xdefinecolor{olive}{cmyk}{0.64,0,0.95,0.4}
%\colorlet{structure}{green!60!black} for color substitution
%Predefined colors: red, green, blue, cyan, magenta, yellow, black,
%darkgray, gray, lightgray, orange, violet, purple, and brown
%If you want to use the options of ?color? package, pass
%[color=option] option to Beamer.
%If you want to use ?pstcol?, pass [xcolor=pst,dvips] option to
%Beamer. Now you should use ?dvips/ps2pdf?
\def\crb{\color{rblue}}
\def\cm{\color{magenta}}
\def\crr{\color{rred}}
\def\clg{\color{lgreen}}
\def\cb{\color{brown}}
\def\cc{\color{cyan}}

\def\Rnbyn{\mathbb{R}^{n\times n}}
\def\R{\mathbb{R}}
\def\Rm{\mathbb{R}^m}
\def\Rn{\mathbb{R}^n}


\newcommand{\A}{\mathcal{A}}%
\newcommand{\B}{\mathcal{B}}%
\newcommand{\C}{\mathcal{C}}%
\newcommand{\D}{\mathbb{D}}%
\newcommand{\F}{\mathcal{F}}%
\newcommand{\G}{\mathcal{G}}%
\newcommand{\K}{\mathcal{K}}%
\newcommand{\LL}{\mathcal{L}}%
\renewcommand{\L}{\mathcal{L}}%
\newcommand{\M}{\mathcal{M}}%
\newcommand{\N}{\mathcal{N}}%
\newcommand{\NN}{\mathcal{N}}%
\newcommand{\QQ}{\mathcal{Q}}%
\newcommand{\OO}{\mathcal{O}}%
\newcommand{\RR}{\mathcal{R}}%
\newcommand{\VV}{\mathcal{V}}%
\renewcommand{\S}{\mathbb{S}}%
\newcommand{\Ss}{\mathcal{S}}%
\renewcommand{\P}{\mathbb{P}}%
\newcommand{\RP}{\mathbb{RP}}%
\newcommand{\DRP}{\mathbb{DRP}}%
\newcommand{\PP}{\mathcal{P}}%
\newcommand{\X}{\mathcal{X}}%
\newcommand{\Int}{{\rm int}}% interior of a set
\newcommand{\Sn}{\S^n}%
\newcommand{\Snp}{\Sn_+}%


\newcommand{\rra}{\;\ensuremath{\Longrightarrow}\;}%       ===>
\newcommand{\llra}{\;\ensuremath{\Longleftrightarrow}\;}%  <===>
\newcommand{\ri}{{\rm ri}}% relative interior of a set
\newcommand{\face}{{\rm face}}
\newcommand{\trace}{{\rm trace}}%
\newcommand{\spanl}{{\rm span}}%
\newcommand{\rank}{{\rm rank}}%
\newcommand{\tr}{{\rm trace}}%
\newcommand{\trc}{{\rm trace\,}}%
\newcommand{\bpm}{\begin{pmatrix}}
\newcommand{\bem}{\begin{pmatrix}}
\newcommand{\epm}{\end{pmatrix}}
\newcommand{\eem}{\end{pmatrix}}







\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{
\color{blue} Strong Duality, Complementarity, 
\\[4pt]
and Duality Gaps,
\\[4pt]
in Conic Convex Optimization 
}

\author{Henry Wolkowicz\\
Dept. Comb. \& Opt, Univ. Waterloo}
\institute{
\color{lgreen} Joint work with: {\color{blue}Simon Schurr} and 
{\color{rred} Levent Tun{\c{c}}el}
%\overlays{2}{
%\begin{figure}[htb]
%\epsfxsize=50pt
%\centerline{\epsfbox{OP08.eps}}
%%\caption{}
%\end{figure}
}
\date{
HPOPT 2008, Tilburg University
}

\subject{Talks}

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

\begin{document}

\begin{frame}
  \titlepage

\end{frame}


\begin{frame}
  \frametitle{Motivation}
\begin{block}{
 Strong Duality Failure/Absence of Constraint Qualification, CQ
}
$\color{lgreen} \bullet$
{\color{brown}%
Instances: SDP relaxations for hard combinatorial problems (e.g. QAP,
GP, strengthened MC)
}
%
\end{block}
\begin{block}{ }
$\color{lgreen} \bullet$
\underline{\color{magenta}Fresh look} at known 
\underline{\color{magenta}Characterizations of Optimality} using 
\underline{\color{magenta}Subspace Formulation}
\end{block}

\begin{block}{
 Regularization, EFficient Solutions
}
{\color{magenta}%
$\color{lgreen} \bullet$
theme:
use {\color{rred}minimal representations}
}
\end{block}
\begin{block}{
 Connections Complementarity/Duality
}
{\color{magenta}%
$\color{lgreen} \bullet$
Surprising Connections {\color{rred}Complementarity of Homog. Probl.
and duality}/{\color{brown}Numerical implications}
}
\end{block}
\end{frame}


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

\section{
   Motivation, Notation, Preliminaries}

%\subsection{Problem Formulation}



\begin{frame}
   \frametitle{Cone Optimization, \color{brown}(e.g. $K=\Snp$, SDP)}
\begin{block}{
Primal-Dual Pair of Optimization Problems in {\color{brown}Conic} Form}
{\color{magenta}%
\begin{align}
\vspace{-.1in}
 {\color{rblue}(\mbox{assumed finite})}\quad \color{lgreen}
v_P &\color{lgreen}= 
   \sup\limits_{y}\;\{\langle b,y \rangle\ :\ \A^* y \preceq_K c\}, 
    \tag{$\P$}\label{eq:P}\\
\vspace{-.1in}
 {\color{rblue}(v_P \leq )}\quad \color{rred}
     v_D &\color{rred}= \inf\limits_{x}\;\{\langle c,x \rangle\ 
            :\ \A x=b,\ x \succeq_{K^*} 0\}.
    \tag{$\D$}\label{eq:D}
\end{align}
}% end of mag
\end{block}

\pause\uncover{
\begin{block}{where}
\begin{itemize}
\item
$\color{magenta} \A$ - 
        an onto linear transformation; adjoint is $\A^*$
\item
$\color{magenta} K$ -  a proper convex cone with dual/polar cone
$\color{magenta} K^* = \{x: \langle s,x \rangle \geq 0,\ \forall s \in K\}.$
\item
$\color{magenta} s' \preceq_K s'' (s' \prec_K s'')$ - 
     partial order, $\color{magenta} s''-s' \in K ( \in \Int K)$
%Also denote $\color{magenta} s' \prec_K s''$ if 
%         $\color{magenta} s''-s' \in \Int(K)$.
\end{itemize}
\end{block}
}
\end{frame}


%%
%%%\subsection{SDP Formulation}
%%\begin{frame}
%%   \frametitle{Semidefinite Programming, SDP}
%%\begin{block}{SDP}
%%{\color{magenta}%
%%\begin{align}
%% \color{lgreen}
%%v_P & \color{lgreen} =\sup\limits_{y}\;\{\langle b,y \rangle\ :\ \A^* y \preceq_K c\}, 
%%    \tag{$\P$}\\
%% \color{rred}
%% v_D & \color{rred}=\inf\limits_{x}\;\{\langle c,x \rangle\ :\ \A x=b,\ x \succeq_{K^*} 0\}.
%%    \tag{$\D$}
%%\end{align}
%%}% end of mag
%%For SDP, $\A: \Sn \to \Rm$, $b \in \Rm$, $c \in \Sn$, and
%%$K = K^* = \Snp := \{x \in \Sn: x \text{ is PSD}\}$.
%%\end{block}
%%\end{frame}
%%
%%

%\subsection{Faces of Cones}


\begin{frame}
   \frametitle{Faces of Cones}
\begin{block}{Face}
A convex cone $F$ is a {\color{rred}face} of $K$, denoted $F \unlhd K$, if
\[
 x,y \in K \text{  and  } x+y \in F \rra x,y \in F.
\]
If $F \unlhd K$ and $F \ne K$, write $F \lhd K$.
\end{block}

\begin{block}{Conjugate Face}
If $F \unlhd K$, the {\color{rred}conjugate face}
(or complementary face) of $F$ is
\[
  F^c := F^{\perp} \cap K^* \unlhd K^*.
\]
If $x \in \ri(F)$, then $F^c = \{x\}^{\perp} \cap K^*$.

\end{block}
\end{frame}

\begin{frame}
   \frametitle{Minimal Face (Minimal Cone)}
\begin{block}{Feasible sets}
{\color{lgreen} $\F_P^y := \{y: c-\A^*y \succeq_K 0\}$}\\
{\color{lgreen} $\F_P^s := \{s: s=c-\A^*y \succeq_K 0, \mbox{ for some } y\}$}\\
{\color{rred} $\F_D^x := \{x: \A x =b, x \succeq_K^*0\}$}
\end{block}


\pause\uncover{
\begin{block}{Minimal Faces}
\[
{\color{lgreen} f_P := \face \F_P^s  \unlhd K} \qquad
{\color{rred} f_D := \face \F_D^x  \unlhd K^*}
\]
\end{block}
}
\end{frame}

\subsection{SDP Duality Gap Example}

\begin{frame}
    \frametitle{(Modified) SDP Example from Ramana, 1995}
  \begin{block}{Primal SDP}
\[
  {\color{lgreen} 0=v_P}=\sup\limits_{y}\;
\left\{
  y_2\ :\
  \begin{pmatrix}
0&0&y_2\cr 0&y_2&0\cr y_2 &0&y_1
\end{pmatrix}
 \preceq 
\begin{pmatrix}
0&0&0\cr 0&1&0\cr 0&0&0
\end{pmatrix}
\right\}
\]
$y^*= \begin{pmatrix} y_1^* & 0 \end{pmatrix}^T, \quad y_1^* \leq 0, \quad
s^* = c-\A^* y^* =
 \begin{pmatrix} 
        0 & 0 & 0 \cr
        0 & 1 & 0 \cr
        0 & 0 & -y_1^* \cr
    \end{pmatrix}$
\end{block}

\begin{block}{}
Slater's CQ fails for primal and dual; ${\color{rred} v_D=1} >  
         {\color{lgreen} v_P=0}$
\end{block}
\end{frame}
%%
%%\begin{frame}
%%    \frametitle{Dual of SDP Example}
%%  \begin{block}{Dual Program}
%%\[
%%  1=v_D=\inf\limits_{x}\;
%%\left\{
%%  x_{11}\ :\ x_{22}=0,\ 
%%  x_{11}+ 2 x_{23}=1,\ 
%% x  \succeq 0
%%\right\}
%%\]
%%$x^*= \begin{pmatrix} 
%%        1 & 0 & x_{13} \cr
%%        0 & 0 & 0 \cr
%%        x_{13} & 0 & x_{33} \cr
%%    \end{pmatrix}, \quad x_{33} \geq (x_{13}^2)$
%%\end{block}
%%
%%\pause\uncover{
%%\begin{block}{
%%Slater's CQ for (primal) dual \&
%%complementarity {\color{rred}fails}
%%}
%%duality gap $\color{magenta} v_D-v_P=1-0=1$,
%%$\trc x^*s^*= 
%%{\tiny{
%%\trc \begin{pmatrix} 
%%        1 & 0 & x_{13} \cr
%%        0 & 0 & 0 \cr
%%        x_{13} & 0 & x_{33} \cr
%%    \end{pmatrix}
%% \begin{pmatrix} 
%%        1 & 0 & 0 \cr
%%        0 & -y_1^* & 0 \cr
%%        0 & 0 & 0 \cr
%%    \end{pmatrix}
%%}}
%%=1>0$
%%\end{block}
%%}
%%\end{frame}

\begin{frame}
\frametitle{Minimal Face for Ramana Example}
\begin{block}{Feasible Set/Minimal Face}
${\color{lgreen}\F^y_P} = \{y \in \R^2: y_1 \leq 0,\ y_2 = 0\}$
\[
\begin{array}{rcl}
 {\color{lgreen}f_P }
&=&
 \bigcap \{F \unlhd K: {\color{lgreen}\F^s_P}= c-\A^*({\color{lgreen}\F^y_P }) \subset F\} 
     \\&=&
 \begin{pmatrix}
0&0\cr 0&\S^2_+
\end{pmatrix}
 \\& \lhd & \S^3_+
\end{array}
\]
\end{block}

\pause\uncover{
\begin{block}{Slater CQ and Minimal Face}

If \eqref{eq:P} is feasible, then 
\[
{\color{rblue}
 c - \A^*y \not\succ_K 0\ \forall y}
\left( \text{ 
 Slater's CQ fails for \eqref{eq:P}
}\right) 
{\color{lgreen} \llra f_P \lhd K\ }
\]
\end{block}
}
\end{frame}


\subsection{SUBSPACE FORM and MINIMAL REPRESENTATIONS}
\begin{frame}
\frametitle{{\color{brown}(SYMMETRIC)} Subspace Form for \eqref{eq:P} and \eqref{eq:D}}
\begin{block}{Assume Linear Feasibility for $\color{lgreen}
 \tilde s,\tilde y$,$\color{rred} \tilde x$;
with data $A,b,c,K$}
\[
{\color{lgreen}
\A^* \tilde y +\tilde s = c}
\qquad 
{\color{rred}
\A \tilde x = b}
\]
\qquad 
\qquad 
{\color{lgreen}
$\LL^\perp = \RR(\A^*)$ (range)}
\qquad 
{\color{rred}
$\LL = \NN(\A)$ (nullspace) }
\end{block}
\pause\uncover{
\begin{block}{Equivalent Primal-Dual Pair in Subspace Form, (e.g. N\&N '94)}
$\hat{\underline{\mbox{Particular solution}}}$ $+$ \underline{solution of homogeneous
equation}
\[
\color{lgreen}
  v_P = 
c\tilde x  - \inf_s  \left\{  s \tilde x 
       : s \in (\tilde s  + \LL^\perp) \cap K\right\}.
    \tag{$\P$}
\]
\[
\color{rred}
  v_D = \tilde yb+ \inf_x \left\{ \tilde s x  : 
              x \in (\tilde x + \LL) \cap K^* \right\}.
    \tag{$\D$}
\]
\end{block}
}
\end{frame}




\begin{frame}
\frametitle{Numerical/Stability Advantages of Subspace Form}
\begin{block}{Single Bilinear Equation For Interior Point Methods}
Current p-d i-p methods {\color{rred} introduce} ill-conditioning
(ill-posedness)\\
 Solve:
\[
0 = F_\mu (y,v) = 
        {\color{lgreen}\left( c-\A^* y \right)   }
        {\color{rred}\left( \tilde x+\VV^* v \right)   } 
   -\mu I
\]
\quad 
{\color{lgreen}
$\LL^\perp = \RR(\A^*)$ (range)}
\quad 
{\color{rred}
$\LL = \NN(\A)=\RR(\VV^*)$ (nullspace) }
\end{block}
\pause\uncover{
\begin{block}{Some Applications}
$\color{lgreen} \bullet$
Gauss-Newton method for SDP (Kruk et al 2001)
\\$\color{lgreen} \bullet$
GN and CG method for SDP relaxation of Max-Cut (W. 2004)
\\$\color{lgreen} \bullet$
Large Scale LP (Wei and W. 2004)
\end{block}
}
\end{frame}

\subsection{Recession Directions and Minimal Subspaces}

\begin{frame}
\frametitle{For {\color{lgreen}\eqref{eq:P}} and {\color{rred}\eqref{eq:D}}}
\begin{block}{Faces of Recession Directions \color{magenta}(feasible case)}
\[
\color{lgreen}
f^0_{P}:=\face \left(
 \LL^{\perp} \cap K \right) 
 {\color{magenta}( \subset f_P)}
         \qquad 
\color{rred}
          f^0_{D}:=\face \left(\LL \cap K^*\right)
 {\color{magenta}( \subset f_D)}
\]
\end{block}
\pause\uncover{
\begin{block}{Recall}
\[
\begin{array}{lcc}
\color{blue} 
\mbox{minimal faces} & 
   \color{lgreen} f_P = \face \F_P^s & \color{rred} f_D = \face \F_D^x 
\end{array}
\]
\end{block}
\begin{block}{Minimal Subspaces/Linear Transformations}
\[
\begin{array}{lcc}
\color{blue} \mbox{min. subsp.} &
\color{lgreen} \LL_{PM}^\perp := \LL^{\perp} \cap (f_P-f_P)
      & \color{rred} \LL_{DM} := \LL \cap (f_D-f_D)\\
\color{blue} \mbox{min. Lin. Tr.} &
\color{lgreen} \A_{PM}^* & \color{rred} \A_{DM}
\end{array}
\]
\end{block}
}
\end{frame}



   \section{REGULARIZATION for Cone Programs}
   \subsection{Minimal Representations using  MINIMAL FACE}
\begin{frame}
   \frametitle{Regularization of \eqref{eq:P} Using Minimal Face}
\begin{block}{ Borwein-W (1981), $f_P=\face \F_P^s$}
\eqref{eq:P} is
equivalent to 
 {\color{lgreen}regularized \eqref{eq:P}}
{\color{lgreen}%
\[
 {\color{lgreen}v_{RP}} := \color{lgreen}
 \sup\limits_y\;\{\langle b,y \rangle\ :\ \A^* y \preceq_{{\color{black}f_P}} c\}.
    \tag{$\RP$}\label{eq:RP}
\]
}%
\end{block}
\pause\uncover{
\begin{block}{Lagrangian Dual DRP Satisfies Strong Duality:}
{\color{rblue}%
\[
 {\color{red}v_P=v_{RP}=v_{DRP}} 
     \color{red}:= \inf\limits_{x}\;\{\langle c,x \rangle\ :\ \A x=b,\ x \succeq_{{\color{black}f_P^*}} 0\}
    \tag{$\DRP$}\label{eq:DRP}
\]
}%
and $ {\color{red}v_{DRP}} $ is \color{rblue}\underline{attained}
\end{block}
}
\end{frame}

   \subsection{Minimal Representations using  MINIMAL SUBSPACE}
\begin{frame}
   \frametitle{Regularization of \eqref{eq:P} Using Minimal Subspace}
\begin{block}{Assume $K$ Facially Dual Complete, FDC (Pataki/07, 'nice')}
	i.e. {\crb $F\lhd K \implies K^*+F^\perp$ is closed}. 
	(e.g. ${\crr \Snp}, \Rn_+$,SOC).
\end{block}
\pause\uncover{
\begin{block}{$\LL^\perp_{PM}=\LL^\perp\cap (f_P-f_P)$}
\[
 \color{lgreen}
v_{RP} = 
c\tilde x  - \inf_s  \left\{  s \tilde x 
       : s \in (\tilde s  + \LL_{MP}^\perp) \cap K\right\}
    \tag{$\RP$}
\]
\end{block}
}
\pause\uncover{
\begin{block}{Lagrangian Dual DRP Satisfies Strong Duality:}
\[
 \color{rred}
v_{DRP} 
   = \tilde yb+ \inf_x \left\{ \tilde s x  : 
              x \in (\tilde x + \LL_{MP}) \cap K^* \right\}
    \tag{$\DRP$}
\]
and $ {\color{red}v_{DRP}} $ is \color{rblue}\underline{attained}
\end{block}
}
\end{frame}



\begin{frame}
	\frametitle{Nice and Devious Cones}
	\begin{block}{Alternate Form of BW Characterization}
		$v_P \geq \sup_{y\in g^{-1}(f_P-f_P)}
\langle b,y\rangle + \langle (c-\A^*y),\bar x\rangle$,
\cm for some $\cm \bar x \in f_P^*=K^*+f_P^\perp$;
\quad \clg WOLG $\crr \bar x \in K^*$
\end{block}

\pause\uncover{
\begin{block}{Lemma for SDP Case (Ramana,Tuncel,W./97)}
Let $0\neq F \lhd \Snp$. Then\\
	{\crb $\Snp+F^\perp$ is closed (nice)} \\
	{\crr $\Snp+\spanl F^c$ is \underline{not} closed (devious)}\\
	{\cb $\Snp+F^\perp=\overline{\Snp+\spanl F^c}$}

\end{block}
\begin{block}{  }
	Let $\LL=\spanl F^c$;
	%$0\neq f_P^0:= \face (\LL^\perp \cap \Snp) \lhd \Snp$, then
	choose $c=\tilde s=0$ and $\tilde x \in
	 (\Snp+F^\perp) \backslash (\Snp+\spanl F^c)$;\\
	 \crr then $0=v_P < v_D=\infty$.
\end{block}
}
\end{frame}

   \subsection{Constraint Qualifications, CQs, for (P)}
\begin{frame}
   \frametitle{Strong Duality for (P) \color{brown}
                 ($v_P=v_D$ and $v_D$ is attained)}
\begin{block}{Minimal Face and Minimal Subspace CQs for (P)}
\begin{enumerate}
\item
$\color{magenta} f_P=K$ is a CQ
\\ \qquad  \qquad({\color{brown}  from BW: $f_P^* = K^*$ })
\item
$\color{rred} \LL^\perp\cap (f_P-f_P) =\color{magenta} 
              \LL^\perp_{PM}=\LL^\perp$ is a CQ (if $K$ is FDC (nice))
\\   \qquad({\color{brown}  
$\tilde s \in f_P-f_P: x^*=x^*_K+x^*_f \in f_P^*=K^*+f_P^\perp \implies$
\\ \qquad \qquad $x^*(\tilde s +\LL^\perp) = x_K^*(\tilde s +\LL^\perp)
$
})
\end{enumerate}
\end{block}
\pause\uncover{
\begin{block}{Universal CQ, UCQ for (P)
(i.e. independent of \underline{feasible} data $c,b$) 
}
$\color{magenta} \LL^\perp \subset f_P^0 -f_P^0$ is a UCQ  (if $K$ is FDC)
\\   \qquad({\color{brown}  
wlog choose $\tilde s \in K$, $\tilde x \in K^*$; shows that
$f_P^0\subset f_P, f_D^0\subset f_D$
})
\end{block}
}
\end{frame}



%%   \subsection{Difficulties with Regularization}
%%\begin{frame}
%%   \frametitle{Implementation Problems with Regularization}
%%\begin{block}{ Difficulties}
%%Borwein and W. also gave an algorithm to compute $\color{rred} f_P$.
%%
%%But Difficulties:\\
%%\begin{enumerate}
%%\item
%%The algorithm requires the solution of several (homogeneous)
%%cone programs  (constraints are: 
%%$\color{rblue} \A x=0, \langle c,x\rangle =0,
%%0\neq x\succeq_K 0$)
%%%that are potentially much larger 
%%%then the original problem \eqref{eq:P}.
%%\item
%%If Slater's CQ fails for \eqref{eq:D}, then 
%%it also fails for each of these cone programs.
%%\end{enumerate}
%%\end{block}
%%\end{frame}
%%
%%   %\subsection{Regularization Using Ramana's Dual for SDP}
%%
%%\begin{frame}
%%   \frametitle{Ramana's Strong Dual for SDP}
%%\begin{block}{
%%Ramana '95:
%%{\color{red}Extended Lagrange-Slater dual (ELSD)} for \eqref{eq:P}}
%%
%%Construction of this dual takes advantage
%%of the well understood facial structure of $\Sn_+$.
%%\end{block}
%%
%%\begin{block}{Advantages:}
%%\begin{enumerate}
%%\item
%%ELSD is explicit in terms of original data $(\A,b,c)$
%%
%%\item
%%ELSD is {\color{rred} poly. size}
%%(\# vrbles is $\O(k n^2)$, $k \leq \min\{m,n\}$)
%%\end{enumerate}
%%\end{block}
%%
%%\begin{block}{Disdvantages:}
%%\begin{enumerate}
%%\item
%%Slater's CQ may fail for ELSD and its Lagrangian dual.
%%% If the original dual satisfies Slater, then so does ELSD.
%%\item
%%ELSD can potentially be very large.
%%\end{enumerate}
%%
%%% $\OO(k n^2)$ can be large, since the worst case bound on
%%%$k$ can be achieved. There exist SDP instances for which
%%%$k = m-1 = n-1$.  For such instances, an interior-point method
%%%applied to ELSD could require $\OO(n^7)$ arithmetic operations
%%%per iteration (ignoring structure and potential sparsity in ELSD).
%%\end{block}
%%\end{frame}
%%

\section{Towards a Better regularization}

\begin{frame}
   \frametitle{Our Goals:}
   
%\begin{block}{Equivalence in the case of SDP}
%Ramana, Tun{\c{c}}el, and W. '97:
%{\color{rred} Ramana's ELSD is equivalent to (DRP)} (dual of 
%regularized primal of Borwein and W.)
%
%(Both approaches may require solution of
%potentially large SDPs 
%that need not satisfy Slater's CQ.)
%\end{block}
%\pause\uncover{
\begin{block}{Goals: Derive an Algorithm that Satisfies}
\begin{enumerate}
\item
{\color{rred} recognizes} if {\color{lgreen}Slater's CQ holds} and if
\eqref{eq:P}--\eqref{eq:D} has a {\color{lgreen}zero duality gap}
(improves on stability/efficiency of B-W algorithm)
\item {\color{rred}size} of any intermediate cone program solved does
not exceed that of \eqref{eq:P} or \eqref{eq:D}
(improves on size/efficiency of Ramana's dual)
\item intermediate cone programs to be solved are {\color{rred}well
behaved} (in the Slater CQ sense)
\end{enumerate}
\end{block}
%}
\end{frame}


\begin{frame}
   \frametitle{Theorem of the Alternative for Slater's CQ}
\begin{block}{THEOREM}
Suppose that \eqref{eq:P} is feasible. Then
exactly one of the following two systems is consistent:

\smallskip
(1)\; $\color{magenta} \A x=0,\ \langle c,x \rangle = 0, \text{ and }  
         0 \ne x \succeq_{K^*} 0$

(2)\; $\color{magenta} \A^*y \prec_K c\ \qquad 
   \color{rblue} \left(\text{Slater's CQ holds for \eqref{eq:P}}\right)$
\end{block}

\pause\uncover{
\begin{block}{Difficult?}
\underline{In theory}, we can solve
\\ \qquad $\color{magenta} (*) \quad \min\{0: x \text{ satisfies (1)}\}$\\
to determine if Slater's CQ fails for \eqref{eq:P}.

{\color{rred}But} this problem {\color{magenta} (*)}
need not satisfy the generalized Slater CQ!
\end{block}
}
\end{frame}



\subsection{A {Stable} Auxiliary Problem}
\begin{frame}
   \frametitle{ {\color{rred}Stable} Theorem of the Alternative}
   \begin{block}{{\color{rred}Stable} Auxiliary Problem}
\vspace{-.1in}
Let $e \in \Int(K) \cap \Int(K^*)$; define
$\color{rred} \A_c x := \begin{pmatrix}  \A x \cr \langle c,x \rangle \end{pmatrix}$
{\color{blue}
\vspace{-.2in}
\[
\begin{array}{rcl}
\alpha^* := \left\{ \inf\limits_{x,\alpha}  \alpha  :
   \A_c x = 0,
    x + \alpha e \succeq_{K^*} 0, 
     \langle e, x \rangle \leq 1 \right\}
    \tag{$\A$}\label{eq:A}
\end{array}
\]
}
\vspace{-.2in}
\end{block}

%%%\pause\uncover{
   \begin{block}{Properties/Advantages}
\begin{itemize}
%%%\item
%%%WLOG $c \notin \RR(\A^*)$ (or remove $\langle c,x \rangle = 0$)
%%%% otherwise we can remove $\langle c,x \rangle = 0$.
\item
{\color{magenta}size} of \eqref{eq:A} essentially that of \eqref{eq:D}
%%%\item
%%%generalized Slater CQ holds for \eqref{eq:A} and its dual.
\item
A {\color{magenta}strictly feasible} primal-dual point is easily found.
\item
Apply primal-dual IPM; 
assume a barrier for $K^*$ such that
the central path defined by it converges to a point in the relative
interior of the optimal face;
{\color{magenta}follow central path closely at end} of algorithm. 
\end{itemize}
\end{block}
%}
\end{frame}



\begin{frame}
   \frametitle{Slater's Condition and the Auxiliary problem}
   \begin{block}{Solution to \eqref{eq:A} yields info on
	   \eqref{eq:P}--\eqref{eq:D}}

\textbf{Theorem:}  The $\color{blue} x$
component of the central path for \eqref{eq:A}
converges to a point in {\color{blue}$\ri(\face(G_P))$}, where
{\color{blue}%
\[
   G_P := \{x\ :\ Ax = 0,\ \langle c,x \rangle = 0,\ x \succeq_{K^*} 0\}.
\]
}%
Moreover, since
$\color{rred} f_P \subset \{x^*\}^{\perp} \cap K = [\face(G_P)]^c \unlhd K$,
one of the following holds:
\begin{enumerate}
	\item
\underline{\color{rred}$\alpha^* = 0$ and $x^* = 0$}, so Slater's CQ holds for
\eqref{eq:P}, or\\
\item
	\underline{\color{rred}	$\alpha^* = 0$ and $0 \ne x^* \succeq_{K^*} 0$}, so
$f_P \subset \{x^*\}^{\perp} \cap K {\color{red}\lhd} K$, or\\ 
\item
	\underline{\color{rred}	$\alpha^* < 0$ and $x^* \succ_{K^*} 0$}, so
the generalized Slater CQ holds for \eqref{eq:D}.
\end{enumerate}
\end{block}
\end{frame}


%%\begin{frame}
%%   \frametitle{Our Algorithm}
%%   \begin{block}{\textbf{Input:} $\A,b,c,K$, and $\varepsilon > 0$}
%%
%%Compute an optimal $\alpha^*$ and $x^* \in \ri(\face(G_P))$
%%from \eqref{eq:A} using a primal-dual IPM.
%%\end{block}
%%
%%\begin{block}{\textbf{While} $\|x^*\| > \varepsilon$}
%%\begin{quote}
%%\textbf{If} $\alpha^* < 0$, then $x^* \succ_{K^*} 0$,
%%$\color{rred} f_P = \{0\}$. Hence optimal $y$ for \eqref{eq:P}
%%satisfies $A^* y = c$; exit algorithm.
%%
%%\textbf{Else}
%%\begin{enumerate}
%%	\item $y \in \F_P$ implies
%%$c - \A^*y \in [\face(G_P)]^c \lhd K$, get {\color{red}reduced
%%primal} with cone {\color{blue}$K' = [\face(G_P)]^c$}.
%%
%%\item Replace (update) primal by reduced primal.
%%\end{enumerate}
%%\textbf{End}
%%\end{quote}
%%
%%\end{block}
%%\end{frame}


\begin{frame}
	\frametitle{Algorithm \underline{Alternates} to Obtain
	\underline{Minimal Representations}}

\begin{block}{For Minimal Face}
	From auxiliary problem, find:\\
	$\color{rred}0\neq x\in K^*, \{x\}^\perp=H,  
   \color{magenta}\{x\}^\perp \cap K \supset f_P$
\end{block}

\begin{block}{For Minimal Subspace}
	Find $\A_H$ so that $\color{magenta}\RR(A_H^*) = \RR(A^*) \cap H$\\
	to get {\color{rred} reduced problem in $H$}
\end{block}
\end{frame}


%%\subsection{The SDP Case}
%%\begin{frame}
%%   \frametitle{Regularization for SDP}
%%   \begin{block}{ The (Conjugate) Faces, $\F \unlhd \Sn_+$ are of the Form }
%%{\color{blue}
%%\begin{eqnarray*}
%%\F   &=& 
%%   \begin{pmatrix}P& Q\end{pmatrix}
%%\begin{pmatrix} \S_+^{\color{red}r}   &0\cr 0&0 \end{pmatrix}
%%          \begin{pmatrix}P& Q\end{pmatrix}^T
%%		 = P \S_+^{\color{red}r} P^T\\
%%\F^c &=& 
%%        \begin{pmatrix}P& Q\end{pmatrix}
%%		\begin{pmatrix} 
%%			 0&0\cr 0&\S_+^{\color{red}n-r}  \end{pmatrix}
%%           \begin{pmatrix}P& Q\end{pmatrix}^T
%%			= Q \S_+^{\color{red}n-r} Q^T
%%\end{eqnarray*}
%%}
%%\end{block}
%%\begin{block}{}
%%where matrix $\bpm P  & Q\epm$ is orthogonal.
%%\end{block}
%%\end{frame}
%%
%%\begin{frame}
%%	\frametitle{The Minimal Face $f_P$ Using the Auxiliary Problem}
%%   \begin{block}{With $x^* \in \ri(G_P)$ from Auxiliary Problem}
%%$x^* = 
%%{\tiny{
%%           \bpm P& Q \epm
%%		\bpm
%%		 D&0\cr 0&0  \epm 
%%           \bpm P& Q\epm^T
%%}}$,
%%%where $D \in \R^{r \times r}$
%%
%%$\face(G_P) = \face(x^*) = 
%%        \begin{pmatrix}P& Q\end{pmatrix}
%%\begin{pmatrix} \S_+^{\color{red}r}   &0\cr 0&0 \end{pmatrix}
%%        \begin{pmatrix}P& Q\end{pmatrix}^T$\\
%%Then: $\color{red} f_P \unlhd K^\prime := [\face(G_P)]^c = Q \S^{n-r}_+ Q^T$.
%%
%%\end{block}
%%
%%\begin{block}{WLOG: shift $c$ and find linear transformation $\LL^\prime$}
%% $c^\prime \leftarrow c-\A^* y^\prime \in K^\prime -K^\prime$; \quad
%%  $\RR(\A^* \LL^\prime) \subset K^\prime -K^\prime$
%%\end{block}
%%
%%\begin{block}{A Reduced Lower Dimensional Primal Problem}
%%equivalent cone constraints: 
%%   $\color{blue}
%%          \A^* \LL^\prime y^\prime \preceq_{K^\prime} c^\prime$ \\
%% $\color{blue}
%%  Q^T(A^*\LL^\prime y^\prime)Q \preceq_{\S^{n-r}_+} Q^Tc^\prime Q
%%$
%%%so the reduced primal problem lies in a lower dimensional space.
%%
%%%Using $(c - A^*y)P = 0$ we can always eliminate some $y_i$'s
%%%(if \eqref{eq:P} is feasible), so reduced primal has fewer
%%%variables \textit{and} constraints.
%%
%%% Moreover, $c - A^*y \preceq{K'} 0$ is equivalent to
%%% $Q^T(c - A^*y)Q \preceq_K' 0$ and $(c - A^*y)P = 0$.
%%% So if the linear system $(c-A^*y)P = 0$ is inconsistent, 
%%% we can conclude that \eqref{eq:P} is infeasible.
%%\end{block}
%%\end{frame}
%%

\section{Numerical Tests}
\begin{frame}
    \frametitle{Previous SDP with $K = \S^3_+$ and a Duality Gap of $1$}
    \begin{block}{SeDuMi $1.1$ Results}
{\tiny{
$ y^* = 
\begin{pmatrix}  -0.321 \times 10^6 &  0.372 \end{pmatrix}^T$\\
$s^*  = 
\begin{pmatrix}0  & 0 & -0.372 \cr
         - & 0.628 \times 10^5&0  \\
         - & -  &  -0.321 \times 10^6\end{pmatrix}
$;}} \\
%X^* =
%\arr{ccc}{ 0.255 & 0 & .392 \times 10^{-10} \\
%  0 & .486 \times 10^{-6} & .372\\
%   .392 \times 10^{-10} & .372 & .321 \times 10^6}
desired accuracy ($10^{-6}$) achieved but!!
$\color{magenta}\langle c,x^* \rangle - \langle b,y^* \rangle \approx -0.12$!
and $s^*$ is {\color{rred} not} pos. semidef.
\end{block}

\begin{block}{After One Step of the Reduction}
Our code yields correct primal solution:
\begin{align*}
y^* =
\begin{pmatrix} -1.50\cr 0\end{pmatrix} ,\quad
s^* =
\begin{pmatrix} 0 & 0 & 0\\
           - & 1.00 & 0\\
           - & - & 1.50\end{pmatrix}
\end{align*}
\end{block}
\end{frame}


\begin{frame}
   \frametitle{Higher Dimensional Numerical Experiments}
   \begin{block}{SDP with $m=n \geq 3$, $b = e_2$, $c = 0$}
{\tiny{
\[
 \A^*y = 
  \begin{pmatrix} 
y_1&y_2&y_3&&\cdots&y_{n-1}&y_n\cr
y_2&y_3&&&&&\cr
%y_3&&y_4&&&&\cr
%y_4&&&&&&\cr
\vdots&&&&\ddots&&\cr
y_{n-1}&&&&&y_n&\cr
y_n&&&&&&0
\end{pmatrix} 
 \]
}}
\end{block}

\begin{block}{SeDuMi/Our Algorithm}
	SeDuMi gives \underline{incorrect} primal/dual solution;
	{\color{rred}duality gap of $-1$}; our algorithm gives correct solution\\
	$\color{rred}F_P = \{y \in \R^n: y_1 \leq 0,\ y_2 = \cdots = y_n = 0\}$\\
min. face 
$\cm
f_P = \{s \in \Sn_+: s_{11} \geq 0,\ s_{ij} = 0\ \forall (i,j) \ne (1,1)\}$,\\
and \eqref{eq:D} is infeasible.
 
\end{block}
\end{frame}


\section{Strict Complementarity and Nonzero Duality Gaps}
%%\begin{frame}
%%   \frametitle{\eqref{eq:P}--\eqref{eq:D} in {\color{red} Symmetric Subspace} Form}
%%   \begin{block}{{\color{red} Symmetric Subspace} Form}
%%
%%Let: $\bar{s}:=c$;  $A\bar{x}=b$;
%%$\LL = {\rm Nullspace}(\A)$. Then:
%%{\color{blue} %
%%\begin{align}
%% v_P &= \langle \bar{s},\bar{x} \rangle\
%%      - \inf\limits_{s}\;\{\langle \bar{x},s \rangle\ :\ s \in (\bar{s}+\LL^{\perp}) \cap K\}, 
%%    \tag{$\PP'$}\label{eq:P'}\\
%% v_D &= \inf\limits_{x}\;\{\langle \bar{s},x \rangle\ :\ x \in (\bar{x}+\LL) \cap K^*\}.
%%    \tag{$\D'$}\label{eq:D'}
%%\end{align}
%%}% end of \blue
%%\end{block}
%%
%%\begin{block}{
%%{\color{red} Recession Cone Feasibility Problems} for
%%\eqref{eq:P'} and \eqref{eq:D'}:
%%}
%%$e \in \Int(K) \cap \Int(K^*)$; and
%%$(0 \neq x^*,0=\alpha^*)$ soln to aux. prob.
%%{\color{blue} %
%%\begin{align}
%% \Ss &:= \{s \in \LL^{\perp} \cap K: \langle e,s \rangle = 1\}, \tag{PRF}\label{PRF}\\
%%x^*/\langle e,x^* \rangle \in 
%% \X &:= \{x \in \LL \cap K^*: \langle e,x \rangle = 1\}. \tag{DRF}\label{DRF}
%%\end{align}
%%}% end of \blue
%%
%%%$\rightarrow$ Given a solution $(x^*,\alpha^*)$ to the auxiliary problem
%%%with $x^* \ne 0$ and $\alpha^* = 0$, we have $x^*/\langle e,x^* \rangle \in \X$. 
%%\end{block}
%%\end{frame}
%%
%%%%%%%%start of Wei-Wolk material

\begin{frame}


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


\begin{block}{Theoretical/Numerical Difficulties}
\begin{itemize}
\item   Primal Slater condition implies {\crr strong duality}, i.e. 
{\cm 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,s$ such that
\\\qquad ${\cm x+s \succ 0}   \qquad \left(\in \Int (K+K^*) \right)$
\end{itemize}
\end{block}


\pause\uncover{
\begin{block}{Theoretical Difficulties/Convergence}
\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/Relation to Duality Gaps???}
increased number of iterations? loss of accuracy?
\end{block}
}


\end{frame}


\begin{frame}
\frametitle{Hard SDP Instances (Wei and W. 2006)}
\begin{block}{Maximal Complementary Solution Pair:}
\begin{itemize}
\item
A p-d pair of optimal solutions
$(\bar s,\bar x )$ is a
\underline{{\em \crr maximal complementary solution pair}}
if the pair maximizes the sum 
$\rank(s)+\rank(x)$ over all p-d optimal $(s,x)$. 
\end{itemize}
\end{block}

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

\pause\uncover{
\begin{block}{Hard SDP Instances:}
\begin{itemize}
\item
problems where 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 
{\crb Given:} {\crr rank of optimum x is $r>0$}; 
{\clg number constraints is $m>1$}
\item 
Let $Q= [ Q_P | Q_N | Q_D ]$ be orthogonal matrix; 
dimensions of $Q_P$, $Q_N$, $Q_D$ are 
$n\times r$, $n\times g$,  $n\times (n- r-g)$, resp.
Construct:
${\crr  x:= Q_P D_x Q_P^T} \hspace{.3cm} {\clg s:= Q_D D_s Q_D^T}$,\\
where $D_x\succ 0$ and $D_s\succ 0$.
\item cont...


\end{itemize}
\end{block}

\end{frame}




\begin{frame}

\frametitle{Algorithm cont...}


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

\item 
Define
\[\clg
A_1 = \begin{bmatrix} Q_P |Q_N | Q_D\end{bmatrix}
\begin{bmatrix} 0 & 0  & Y_2^T \cr
    0     & {\crr Y_1}  & Y_3^T \cr
    Y_2 & Y_3 & Y_4 \end{bmatrix}
\begin{bmatrix}Q_P |Q_N | Q_D\end{bmatrix}^T,
\]
where $Y_1\succ 0$, $Y_4$ symmetric, and $Q_DY_2 \neq 0$.
\item 
Choose $A_i \in \Sn$, with
$\{A_1Q_P, A_2Q_P, \dots, A_mQ_P\}$ {\crb lin. indep.}
(Note $A_1Q_P = Q_D Y_2 {\crr \neq 0}$.)
\item 
Set ${\crr b := \A(x)}, \hspace{.3cm} {\clg c:= \A^*(y) + s}$,
with $y \in \Re^m $ random.
\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 $s,x \succeq 0, sx=0$ but strict complementarity fails.
\item
step 5 guarantees primal-dual
feasibility, i.e. s,x are an optimal pair. 
\item
Steps 3,4 guarantee $s,x$ are a maximal complementary solution pair.
\end{itemize}
\end{block}

\end{frame}




\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
\\ \qquad $\clg [Q_P |Q_N ]^TA_2 [Q_P |Q_N ] \succ 0$,
then Slater's CQ holds for (P).
\item If the following additional conditions
on  $A_i, i=1,\ldots,m$, are satisfied,
\[
\crr
\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 $\crr \hat x= \alpha I\succ 0$ is feasible for (D)
\end{enumerate}




\end{block}

\end{frame}



\begin{frame}
\frametitle{Empirical Observations}

\begin{block}{Numerical Difficulties Correlate with Large Nullity}
\begin{itemize}
\item There is a {\crb strong correlation} between the {\clg iteration
number} to achieve the desired stopping tolerance and the
  {\clg size of the complementarity nullity}, when the accuracy requirement is
  high. 
\item Large nullity instances cause problems for SDPT3 solver.
\item
Local asymptotic convergence rate is slower when nullity is larger.
\end{itemize}
\end{block}

\end{frame}



%%%%%%%%end of Wei-Wolk material




   \subsection{Complementarity Partition and Nonzero Duality Gap}
\begin{frame}
   \frametitle{Theoretical Connections Complementarity/Duality?}
   \begin{block}{Numerical Difficulties}
  (Both) {\crr  loss of Slater CQ (strict feasibility)} and 
  {\crb loss of strict
  complementarity} independently result in numerical difficulties for
 interior-point methods.
\end{block}
   \begin{block}{Theoretical Connection?}
	   Is there a theoretical connection between {\clg loss of duality}
	   (from loss of a CQ)
	   and {\clg loss of strict complementarity}?
\end{block}
\end{frame}


\begin{frame}
   \frametitle{Complementarity Partition}
\begin{block}{Recall Faces of Recession Directions}
\[
\color{lgreen}
f^0_{P}:=\face \left(
 \LL^{\perp} \cap K \right),
         \qquad 
\color{rred}
          f^0_{D}:=\face \left(\LL \cap K^*\right)
\]
\end{block}

%%   \begin{block}{Symmetric Subspace Form}
%%\vspace{-.1in}
%%{\color{blue} 
%%\begin{align}
%% \Ss &:= \{s \in \LL^\perp \cap K: \langle e,s \rangle = 1\},  
%%               \quad \LL^\perp = \RR (\A^*)
%%\tag{PRF}\label{PRF}\\
%% \X &:= \{x \in \LL \cap K^*: \langle e,x \rangle = 1\} 
%%               \quad \LL = \N (\A)
%%\tag{DRF}\label{DRF}
%%\end{align}
%%}% end of \blue
%%\vspace{-.1in}
%%\end{block}

\begin{block}{The pair $f_P^0,f_D^0$ define a
	Complementarity Partition}
{\color{lgreen} $\face(f_P^0) \subset  \face(f_D^0)^c$} and
{\color{rred} $\face(f_D^0) \subset  \face(f_P^0)^c$}.\\
it is a {\color{red} strict complementarity partition}
if both {\color{rblue} $[\face(f_P^0)]^c = \face(f_D^0)$}
and $\crb [\face(f_D^0)]^c = \face(f_P^0)$;\\
it is {\color{red} proper} if $f_P^0$ and $f_D^0$ are both nonempty.
\end{block}

\end{frame}

\begin{frame}
	\frametitle{SDP Picture}
%%\begin{block}{}
%%Strict complementarity of \eqref{PRF}--\eqref{DRF} is closely
%%related to \eqref{eq:P}--\eqref{eq:D} having a finite nonzero
%%duality gap.
%%\end{block}
\begin{block}{For SDP (after a rotation)}
	\[
	\crb
\begin{bmatrix}
	{\crr f_D^0}  & 0 & 0 \cr
	0 & 0 & 0 \cr
	0 & 0 & {\clg f_P^0}
\end{bmatrix}
\]
\end{block}

\begin{block}{Form Primal-Dual Pair}
	\[
	\crb
	{\crr \tilde x}=
	{\clg \tilde s}=
	\begin{bmatrix}
	0  & 0 & 0 \cr
	0 & {\cm v \succ 0} & 0 \cr
	0 & 0 & 0
\end{bmatrix}
\implies \cm \left\langle s,x \right\rangle \geq \|v\|_F^2,
\]
for all feasible pairs $\cm s, x$.
\end{block}

\end{frame}

\begin{frame}
   \frametitle{Strict Complementarity and Nonzero Gaps}
%%\begin{block}{}
%%Strict complementarity of \eqref{PRF}--\eqref{DRF} is closely
%%related to \eqref{eq:P}--\eqref{eq:D} having a finite nonzero
%%duality gap.
%%\end{block}
\begin{block}{ \textbf{Theorem:} {\color{brown} $K$ is a proper cone}
	}
(1) If $f_P^0,f_D^0$ define a proper complementarity partition
but {\color{blue}not a strict complementarity partition}, then there exists $\bar{s}$
and $\bar{x}$ such that \eqref{eq:P}--\eqref{eq:D}
with data $(\LL,K,\bar{s},\bar{x})$ has a {\color{rred}finite nonzero
duality gap}.
\end{block}

\begin{block}{(Partial Converse)}
(2) If (a) \eqref{eq:P}--\eqref{eq:D} with data $(\LL,K,\bar{s},\bar{x})$
has a finite nonzero duality gap with both optimal values attained, and
{\color{rblue} (b) the objective functions are constant along all
recession directions of \eqref{eq:P} and \eqref{eq:D}}, then
{\color{rred} $f_P^0,f_D^0$
has a proper complementarity partition
but not a strict complementarity partition}.

\end{block}
\end{frame}

%%\begin{frame}
%%   \frametitle{Generating SDP Instances with nonzero gaps}
%%   \begin{block}{$K = \Sn_+$ Instance}
%%Choose positive integers $n,p,d$ with $n > p+d$.
%%Let $e = I_n \in \Int(K) \cap \Int(K^*)$.
%%\end{block}
%%
%%   \begin{block}{Choose subspace $\LL$ and Orthogonal Matrix $Q$}
%%{\tiny{
%%$
%%  \face(\LL^{\perp} \cap K)= Q
%%   \begin{pmatrix} 0&&\\&0&\\&&{\color{blue} \S^p_+}
%%     \end{pmatrix}
%%            Q^T,
%%  \face(\LL \cap K^*)= Q
%%\begin{pmatrix}  {\color{blue} \S^d_+}&&\\&0&\\&&0
%%  \end{pmatrix} Q^T.
%%$
%%}}\\
%%
%%These faces form a {\color{rred} not strict} complementarity partition
%%\end{block}
%%\begin{block}{Choose a nonzero $U \in \S^{n-p-d}_+$}
%%{\tiny{$
%%\bar{s} := \bar{x} := Q 
%%\begin{pmatrix} 0&&\\&{\color{blue} U}&\\&&0
%%\end{pmatrix}  Q^T.
%%$}}
%%
%%duality gap is
%% $\color{rred} \langle \bar{s},\bar{x} \rangle = \|U\|_F^2 > 0$.
%%
%%\end{block}
%%\end{frame}
%%%
%%%\begin{comment}
%%%
%%%\begin{slide}
%%%  \begin{cminipage}{.95\textwidth}
%%%   \title{Strict complementarity and nonzero gaps (5)}
%%%   \par\vspace{0.2\semin}
%%%Failure of strict complementarity for the pair of recession
%%%feasibility problems is also related to lack of closedness of 
%%%sums of cone and subspaces.
%%%
%%%\bigskip
%%%Let $\precl(T) := \cl(T) \setminus T$ denote the preclosure
%%%of a set $T$.
%%%
%%%\medskip
%%%\textbf{Theorem:}
%%%Let $K = K^*$.
%%%If \eqref{PRF}--\eqref{DRF} has no strict complementarity 
%%%partition, then\\
%%%(1) Neither $K+\LL$ nor $K+\LL^{\perp}$ are closed, and\\
%%%(2) There exists a nonzero $x \in K$ such that
%%%$$ x \in \precl(K+\LL) \cap \precl(K+\LL^{\perp}). $$
%%%\end{cminipage}
%%%\end{slide}
%%%
%%%\end{comment}
%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Concluding Remarks}
\begin{frame}
   \frametitle{Conclusion}
\begin{block}{}
\label{final_page}
\begin{itemize}
\item
	{\color{rred}Minimal Representations of the data regularize (P)} \\
min. face $f_P$ and/or the min. L.T. $\A_{PM}$ or $\LL_{PM}^*$
\item
presented a {\color{rred}stable algorithm} to solve (feasible) conic 
problems for which {\color{rred}Slater's CQ fails}
%\item
%algorithm requires the solution of problems whose size is the
%same as that of the original dual; In special cases such as
%SDP and SOCP, these problems become progressively smaller;
\item
{\color{rred}Failure of strict complementarity}
for the associated 
recession problems is closely related to the existence of
instances having a {\color{rred}finite nonzero duality gap}; provides a
means of generating instances for testing.
\end{itemize}
\end{block}
\end{frame}


%\subsection{Near Failure of Slater's CQ/Distance to Infeasibility}
%\begin{frame}
%   \frametitle{Work in Progress}
%\begin{block}{Future:}
%\begin{itemize}
%\item
%We intend to refine our code and test it on larger SDPs
%having a finite nonzero duality gap.
%\item
%Perform backward error analysis to study how rounding errors and errors
%in computing approximate solutions to the auxiliary problems
%affects the number of iterations of our algorithm.
%\item
%In particular, we want to reduce the problem when Slater's condition
%{\color{rred} almost} fails.
%\end{itemize}
%\end{block}
%\end{frame}

%%\begin{frame}
%%   \frametitle{Auxiliary Problem for Distance to Infeasibility}
%%\begin{block}{Perturbed Auxiliary Problem}
%%let $\QQ$ denote the second order cone, SOC; relax the equality
%%constraints $\A_c x=0$ to SOC constraint $\|\A_c x\|_2 \leq \delta$. 
%%\[
%%\begin{array}{rccl}
%%v^{aux}_P := 
%%&\inf_{x,\delta} & \delta\\
%%&\mbox{s.t.} &  \bem \delta \\ \A_c x \eem \succeq_{\QQ}  0\\
%%&  &  \langle x,e \rangle = 1\\
%%&  &  x \succeq_{K^*} 0.
%%\end{array}
%%\]
%%Similar nice properties; and, near failure of Slater's CQ is identified.
%%
%%\end{block}
%%\end{frame}
%%

%\begin{frame}
%   \frametitle{Auxiliary Problem for Distance to Infeasibility}
%\begin{block}{Perturbed Auxiliary Problem}
%\end{block}
%\end{frame}
\end{document}