%
% massey08_talk.tex
%
% This is my talk at Massey University on June 10, 208.
% Based on work done with Levent Tuncel and Henry Wolkowicz
%
% This file requires input from the following files:
%   massey08_talk.mac
%   seminar.bug
%   seminar.bg2
%   seminar.bg3
%
%
\documentclass{seminar}

%%%%%%%%%%%%%%%%
%%% Packages %%%
%%%%%%%%%%%%%%%%
\usepackage{epsfig}
\usepackage{fancyhdr}
\usepackage{fancybox}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{amstext}
\usepackage{verbatim}
\usepackage{url}
\usepackage{boxedminipage}
\usepackage{graphicx}
\usepackage{dcolumn}            % column alignment
\usepackage{epic}               % enhancements to picture environment
\usepackage[usenames]{color}
\usepackage{pstricks}
\usepackage{semlayer}   % for overlays
\usepackage{semcolor}
%\usepackage{slidesec}
\usepackage{framed}
%\usepackage[draft,bookmarks=false]{hyperref} % Must come last
%\usepackage[bookmarks=false]{hyperref} % Must come last so it doesn't get overridden


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% Overlay preamble code %%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% For overlays, to force printer to print all preceding ones.
%% The general form of an overlay is:
%% \bo{1}{Overlay text here}\eo
%% \bo{2}{Overlay text here}\eo  etc.
% The following code is in my macros file
% \makeatletter
% \def\pst@initoverlay#1{%
% \pst@Verb{%
% /BeginOL {dup (all) eq exch TheOL le or {IfVisible not {Visible
% /IfVisible true def} if} {IfVisible {Invisible /IfVisible false def} if}
% ifelse} def
% \tx@InitOL /TheOL (#1) def}}
% \makeatother

%%%%%%%%%%%%%%%%%%%%
%%%% Input files %%%
%%%%%%%%%%%%%%%%%%%%

\input{massey08_talk.mac}
\input{seminar.bug}
\input{seminar.bg2} % See the Seminar bugs list
\input{seminar.bg3} % Unofficial bug fixes
%\usepackage{fixseminar}  % has to be loaded after hyperref?

%%%%%%%%%%%%%%%%%%%%
%%% Slide Set-up %%%
%%%%%%%%%%%%%%%%%%%%

%\landscapeonly
%\def\printlandscape{\special{landscape}}  % works with dvips, not dvi2pdf
 \renewcommand{\printlandscape}{\special{landscape}}
% Workaround to use hyperref and landscape slides
% Remove if you are using portrait slides
\makeatletter
% A4 paper:  \def\special@paper{297mm,210mm}
% uncomment to produce landscape; but comment the next line (and uncomment
% the \twoup line to produce portrait twoups.
%\def\special@paper{11in,8.5in}
\makeatother
 \twoup
%\psdraft

%  \setlength{\slidewidth}{8.5in}
%  \setlength{\slideheight}{6.3in}
%  \def\SeminarPaperWidth{210truemm}
%  \def\SeminarPaperHeight{297truemm}

\addtolength{\slideheight}{.5in}
\renewcommand{\slidetopmargin}{.35in}

% \sliderotation{right}

%% Note that I can also define \pagestyle immediately after \begin{document}
%\pagestyle{empty}

\slideframe{shadow}

%% only generate some slides:
% \onlyslides{1-3,4,8}

%%% The following is needed since \maketitle sets \pagestyle to plain.
%\thispagestyle{fancy}
%\rhead{\textbf{\Large{\orchid{\thepage}}}}
%% Change page number labels (MUST COME AFTER THE PAGE MARGIN SETTINGS ABOVE)
%\usepackage{fancyhdr}
%\pagestyle{fancy}
%\renewcommand{\headrulewidth}{0pt}
%\renewcommand{\footrulewidth}{0pt}
%%% I want a right-aligned header and no (default) centered footer
%\rhead{\textbf{\Large{\orchid{\thepage}}}} 
%\lhead{} 
\cfoot{\vspace{-30pt}\hfill{\scriptsize \theslide/\pageref{final_page}}\hspace{8pt}}

% Headers and footers personalization using the fancyhdr package
% \fancyhead{} % Clear all fields
\renewcommand{\headrulewidth}{0mm}
\renewcommand{\footrulewidth}{0mm}
% \fancyhead[C]{\large\textbf{My Title}}
% \fancyfoot[L]{\thedate}
% \fancyfoot[C]{}
% \fancyfoot[R]{\small Page \theslide}

% To center horizontally the headers and footers (see seminar.bug)
\renewcommand{\headwidth}{\textwidth}
%
% To adjust the frame length to the header and footer ones
\autoslidemarginstrue
% To avoid that the headers be too close of the top of the page
% \renewcommand{\slidebottommargin}{0.3in}
%\pagestyle{fancy}

% put a psbox around math in the same way that it would around text
\everypsbox{\psmathboxfalse}
%% \renewcommand{\headwidth}{\textwidth}

% import eps files at their original size.
\epsfslidesize

% Additional local settings
\setlength{\parskip}{1.5ex}%

% \enlargethispage*{30pt}

%%%%%%%%%%%%%%%%%%%%%%%%
%%% Column Alignment %%%
%%%%%%%%%%%%%%%%%%%%%%%%
\newcolumntype{d}[1]{D{.}{.}{#1}}

%%%%%%%%%%%%%
%%% Title %%%
%%%%%%%%%%%%%
\renewcommand{\title}[1]{\begin{center}{\Large \sc #1}\end{center}}

%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Centered Minipage %%%
%%%%%%%%%%%%%%%%%%%%%%%%%

\newenvironment{cminipage}[1]         % centered minipage
{\begin{center}\begin{minipage}{#1}\raggedright}
{\end{minipage}\end{center}}

%%%%%%%%%%%%%%%%%%%%%%%%
%%% Local macros    %%%
%%%%%%%%%%%%%%%%%%%%%%%%

% \renewcommand{\ss}{\smallskip\\}%  Note the line break
% \newcommand{\ms}{\medskip\\}%  Note the line break
% \newcommand{\bs}{\bigskip\\}%  Note the line break
%% The following command reduces the column separation between the
%% vertical lines in the table, and the beginning of each entry.
%\newcommand{\cs}{@{\extracolsep{4pt}}}%
% Create table with additional struts
%\newcommand\tstrut{\rule{0pt}{3.3ex}}  % Top strut
%\newcommand\bstrut{\rule[-1.9ex]{0pt}{0pt}}  % Bottom strut

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% BEGIN DOCUMENT                                                   %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%% Abstract and Keywords %%%%%%%%%%%%%%%%%%%

\begin{comment}

\textbf{Location:}  Massey University

\textbf{Title:}

\textbf{Date:} June 10, 2008

\textbf{Speaker:} Simon Schurr

\begin{abstract}



\end{abstract}

\end{comment}


\begin{comment}
Things to check:

% -- Use 10pt font or less in slide format
% -- I cannot mentioned cones before the notation slide.
% -- Use color consistently: blue for important math 
%    and red for important new terms/words.
% -- Remember the audience may not be familiar with convex/conic optimization.
% -- ensure titles of page are consistent with outline bullets.

\end{comment}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% Global setting 
\sffamily
\pagestyle{fancy}

\begin{slide}%[8.5in,7in]
\begin{cminipage}{.95\textwidth}
\begin{center}
\blue{\large Strong Duality and Stability\\[4pt]
in Conic Convex Optimization 
}\\[25pt]
\green{Simon Schurr\\[4pt]
University of Waterloo\\[4pt]
spschurr@uwaterloo.ca\\[20pt]
Joint work with Levent Tun{\c{c}}el and Henry Wolkowicz}\\[25pt]
Massey University\\[4pt]
June 2008 
\end{center}
\end{cminipage}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}
  \begin{cminipage}{.98\textwidth}
   \vspace{-0.3\semin}
   \title{Outline}
   \par\vspace{0.3\semin}
   \begin{itemize}
     \mitem \textbf{Strong duality in convex optimization}
     \mitem \textbf{Guaranteeing strong duality}
     \mitem \textbf{Solving ill-posed convex programs via stable auxiliary problems}
     \mitem \textbf{Numerical results}
     \mitem \textbf{Relating strict complementarity to finite nonzero duality gaps}
     \mitem \textbf{Conclusions and future work} 
   \end{itemize}%%%
\end{cminipage}
\end{slide}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\ptsize{9}
\begin{slide}
  \begin{cminipage}{.92\textwidth}
   \title{Duality in linear programming (LP)}
   \par\vspace{0.1\semin}

Data: $A \in \Rmn$, $b \in \Rm$, and $c \in \Rn$.\\
Primal problem:
\blue{\vspace{-6pt}
\begin{align*}
  v_P &= \min\limits_{x}\;\{c^T x :\ Ax=b,\ x \geq 0\}\\
     &= \min_x\ \max_{s \geq 0,y}\ L(x,y,s),
\end{align*}
}% end of \blue
where $L(x,y,s) := c^T x - y^T (Ax-b) - s^T x$ is the
Lagrangian.
\medskip 

Dual problem:
\blue{\vspace{-6pt}
\begin{align*}
 v_D &= \max_{s \geq 0,y}\ \min_x\ L(x,y,s)\\
     &= \max\limits_{s,y}\;\{b^T y :\ A^T y + s = c,\ s \geq 0\}.
\end{align*}
}

\red{Weak duality} holds for this pair of problems: \blue{$v_P \geq v_D$}.

Proof: $\min_x \max_y F(x,y) \geq \max_y \min_x F(x,y)$
for \textit{any} function $F(x,y)$, provided the minima
and maxima are attained.
\medskip

The nonnegative quantity $v_P - v_D$ is called the \red{duality gap}.
\end{cminipage}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}
  \begin{cminipage}{.9\textwidth}
   \title{Strong duality for LP}
   \par\vspace{-0.1\semin}
\blue{\vspace{-0.2\semin}
\begin{align*}
 v_P &= \min\limits_{x}\;\{c^T x :\ Ax=b,\ x \geq 0\},\\
 v_D &= \max\limits_{y,s}\;\{b^T y :\ A^T y + s = c,\ s \geq 0\}.
\end{align*}
}  % end of \blue
\red{Strong duality} holds for both problems. That is,\\
(1) $v_P$ finite $\rra  v_P = v_D$ and $v_D$ is attained, and\\
(2) $v_D$ finite $\rra  v_P = v_D$ and $v_P$ is attained.
\medskip

Alternatively, either:\\
(a) $v_P = v_D$ is finite and both values are attained, or\\
(b) at least one problem is infeasible.
\bigskip

Importance of strong duality:
\bi
\nitem
Optimal dual variables (``Lagrange multipliers'') can be used in 
sensitivity analysis.
\nitem
Many classes of algorithms converge only if the duality gap is $0$.
\nitem
Certificate of optimality can be found.
\ei
\end{cminipage}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}
  \begin{cminipage}{1.02\textwidth}
      \vspace{-0.1\semin}
   \title{Strong duality can fail for nonlinear problems}
      \par\vspace{-0.2\semin}
\beas
\hspace{-8pt}\mbox{Consider}\hspace{15pt}
\ptsize{8}
  \sup\limits_{y \in \R^2}\;\left\{-y_2\ :\
  S = \arr{ccc}{1+y_2&0&0\\0&y_1&y_2\\0&y_2&0},\ S \text{ is PSD}\right\}.
\eeas
\smallskip
\ptsize{9}
Solution set is\vspace{-3pt}
\begin{align*}
\ptsize{8}
y^* \in \left\{\arr{c}{y_1\\ 0}: y_1 \geq 0\right\},\qquad
S^* \in
\left\{\arr{ccc}{ 1 & 0 & 0\\
           0 & s_{22} & 0\\
           0 & 0 & 0}: s_{22} \geq 0 \right\}.
\ptsize{9}
\end{align*}
Primal and dual optimal values are attained, but
duality gap is $1$.
\smallskip

The software package Sedumi $1.1$ gives the primal ``solution''
\begin{align*}
\ptsize{8}
y = \arr{c}{ 4.6 \times 10^7 \\ -0.38 }, \qquad
S = \arr{ccc}{ 0.62 & 0 & 0 \\
         0 & 4.6 \times 10^7\hspace{-10pt}&  -0.38\\
         0 & -0.38  &  0}\!.
\end{align*}
\smallskip
\ptsize{9}
Dual solution is also found, but $S$ is not PSD
and duality gap $= -0.13$.
\end{cminipage}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}
  \begin{cminipage}{.96\textwidth}
   \vspace{-0.2\semin}
   \title{Formulations of convex optimization problems}
   \par\vspace{0.4\semin}
Minimize a convex function over a closed convex set:
\beas
  \inf\limits_{x \in S}\; f(x),
\eeas
where $f: \Rn \to \R$ is convex,
and $S \subset \Rn$ is a closed convex set.
\medskip

$S$ may be specified in terms of nonlinear inequalities
$\{x: g_i(x) \leq 0,\ i=1,\cdots,m\}$,
where each $g_i$ is a convex function.
\bigskip

Writing an explicit dual can be difficult or impossible,
so primal-dual algorithms might not be suitable.
\bigskip

$\rightarrow$ Write the problem in \red{conic form}:
the objective function becomes linear, and 
the feasible set is expressed as the intersection of an
\red{affine subspace} and a \red{convex cone}.
\end{cminipage}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}
  \begin{cminipage}{.96\textwidth}
   \title{Preliminaries and notation for cones}
\par\vspace{0.0\semin}
\begin{itemize}
\mitem
A set $K \subset \Rn$ is a \red{cone} if for every
$\lambda \geq 0$ and $x \in K$, $\lambda x \in K$.%%
\bitem
%\sloppy
%\hspace{-10pt}%
\begin{tabular}{ll}
%\hspace{-10pt}
\raisebox{20pt}{\hspace{-10pt}
 \begin{minipage}{202pt}
  \vspace{-17pt}
% \hspace{-10pt}
  Given $K \subset \Rn$, denote its \red{interior} by
  $\Int(K)$, and its \red{dual} by
  \mbox{$K^*:= \{x\in\Rn: \langle x,y \rangle \geq 0\ \forall\,y\in K\}.$}
\vspace{15pt}
\end{minipage}%
}% end of \raisebox
& \hspace{-13pt}\raisebox{-10pt}{\scalebox{.4}{\input{dual3.pstex_t}}}\vspace{-28pt}%% 
\end{tabular}\\[4pt]
%\fussy  % to over-ride sloppy command issue earlier.
% \bigskip
\vspace{15pt}

\bitem
A cone $K$ is \red{proper} if it is closed,
convex, has nonempty interior,\\
and contains no straight lines.\\
If $K$ is proper, so is $K^*$.
\medskip

E.g., the nonnegative orthant,
$K = \{x \in \Rn: x_i \geq 0,\ i=1,\cdots,n\}$, is a proper cone.

\bitem 
$x \preceq_K y$ denotes a partial order induced by $K$, 
i.e.,~$y-x \in K$.\\
Write $x \prec_K y$ if $y-x \in \Int(K)$.
\end{itemize}
\end{cminipage}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}
  \begin{cminipage}{.96\textwidth}
      \vspace{-0.2\semin}
   \title{Primal-dual conic convex formulation}
      \par\vspace{0.3\semin}
Any primal-dual pair of convex problems can be written in conic form:
\blue{
\begin{align}
 v_P &= \sup\limits_{y}\;\{\langle b,y \rangle :\ A^* y \preceq_K c\}, 
    \tag{$\P$}\label{eq:P}\\
 v_D &= \inf\limits_{x}\;\{\langle c,x \rangle :\ Ax=b,\ x \succeq_{K^*} 0\}.
    \tag{$\D$}\label{eq:D}
\end{align}
}% end of \blue
where $A$ is an onto linear operator between vector spaces,\\
its adjoint is $A^*$, and $K$ is a proper cone.
\bigskip

Important special cases:
\begin{itemize}
\item
If $K$ is the nonnegative orthant, then \eqref{eq:P} and \eqref{eq:D}
are LPs. 
\item
If $K$ is the (proper) cone of positive semidefinite matrices $\Sn_+$,
then $K^*=K$, and \eqref{eq:P} and \eqref{eq:D} are 
\red{semidefinite programs} (SDPs).
\item
If $K = \{x\in \Rn: x_1 \geq \sqrt{x_2^2 + \cdots + x_n^2}\}$,
then $K^*=K$, and \eqref{eq:P} and \eqref{eq:D} are
\red{second-order cone programs} (SOCPs).
\end{itemize}
\end{cminipage}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}
  \begin{cminipage}{.99\textwidth}
      \vspace{-0.4\semin}
   \title{Two important convex cones}
      \par\vspace{0.5\semin}
\begin{figure*}[htbp]
\hspace{-15pt}
%\centering
\includegraphics[width = 2.2\textwidth]{cone_plots.eps}
%\caption{....}
%\label{fig:cones}
\end{figure*}
\vspace{-40pt}
The cone of PSD matrices of order $2$ and the second-order cone
of dimension $3$.
\end{cminipage}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}
  \begin{cminipage}{.93\textwidth}
   \title{Application: relaxation of hard discrete optimization problems}
   \vspace{0.2\semin}
\ptsize{8}
\textbf{Maximum cut of a graph:} Given a weighted undirected
graph $G = (V,E)$, find a set $S \subset V$ such that the
weight of the cut $(S,V\setminus S)$ is maximal.

\begin{minipage}{260pt}
\begin{center}
\scalebox{0.2}{\input{max_cut.pstex_t}}
\end{center}
\end{minipage}

\vspace{7pt}
Let $V = \{1,\cdots,n\}$, $w_{ij} \geq 0$ be the weight of
edge $(i,j) \in E$, and let $x \in \{-1,1\}^n$ be the
incidence vector of a cut of $G$. We wish to solve
\begin{align*}
  w^* &:= \max_x \bigg\{\frac{1}{4} \sum_{(i,j) \in E} w_{ij}(1 - x_i x_j): x \in \{-1,1\}^n \bigg\}\\
      &=  \max_x \bigg\{\frac{1}{4} x^T L x : x \in \{-1,1\}^n \bigg\},
\end{align*}
where $L$ is the Laplacian of the graph.
\end{cminipage}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}
  \begin{cminipage}{.95\textwidth}
   \title{Application: relaxation of hard discrete optimization problems}
   \vspace{0.1\semin}
\ptsize{8}
\[
\hspace{-25pt}\mbox{Since  } x \in \{-1,1\}^n \lra  x_i^2 = 1\ \forall\,i,
\quad  \blue{w^* = \max_x \bigg\{\frac{1}{4} x^T L x: x_i^2 = 1\ \forall\,i \bigg\}}.
\]

The Lagrangian dual is
\begin{align}
 (w^* \leq)\  v^* &:= \min_{\lambda}\ \max_x \bigg\{\frac{1}{4} x^T L x - \sum_{i=1}^n \lambda_i(x_i^2 - 1) \bigg\}\nn\\
      &= \min_{\lambda}\ \bigg\{\sum_{i=1}^n \lambda_i: \bigg(\diag(\lambda)- \frac{1}{4}L\bigg) \mbox{ PSD} \bigg\}. 
        \tag{MCD}\label{maxcut_dual}
\end{align}

Strong duality holds for \eqref{maxcut_dual}, so the optimal values
of \eqref{maxcut_dual} and its Lagrangian dual are equal:
\blue{%
\begin{align*}
  v^* &= \max_{X \in \Rnn} \bigg\{ \trace\bigg(\frac{1}{4}LX\bigg): X_{ii}=1\ \forall\,i,
          \ X \textrm{ PSD}\bigg\}.
\end{align*}
}
% Alternatively one could lift the original max cut problem from R^n to S^n
% by setting $X = x*x^T$, and relaxing the resulting rank constraint 
% on X (rank(X) = 1).
%
\begin{itemize}
\nitem This \red{SDP relaxation} can be efficiently solved using a poly time algorithm.
\nitem The optimal $X$ is used to obtain a cut whose weight is no
more than $14\%$ above the optimal weight [Goemans \& Williamson, 1995].
\end{itemize}
\end{cminipage}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{comment}

\begin{slide}
  \begin{cminipage}{.95\textwidth}
   \vspace{-0.8\semin}
   \title{Application: worst-case robust optimization}
   \vspace{0.5\semin}
Least squares problem with certain data
$A \in \Rmn$ and $b \in \Rm$, where $m > n$:
\[
  \min_{x \in \Rn}\ \|Ax-b\|_2\ .
\]
\bigskip
\smallskip

It's more realistic to assume $A$ is not known with certainty,
but instead lies inside some nonempty bounded
\red{uncertainty set} $\U \subset \Rmn$.
\bigskip

The worst-case error associated with a point $x$ is 
\[
  \sup_{A \in \U}\ \|Ax-b\|_2\ .
\]
\end{cminipage}
\end{slide}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}
  \begin{cminipage}{.95\textwidth}
   \title{Application: worst-case robust optimization}
   \vspace{0.2\semin}

Goal: find the worst-case robust approximation
\[
  \min_{x \in \Rn}\ \sup_{A \in \U}\ \|Ax-b\|_2\ .
\]

This is a convex problem (even if $\U$ is nonconvex),
but its difficulty depends on the description of $\U$.
\smallskip

Suppose $\U$ is the convex hull of the matrices
$A_1,\cdots,A_k$, where each $A_i \in \Rmn$.
I.e.,~$\U$ is a polyhedron.
\medskip

Then the problem becomes
\[
  \min_{x \in \Rn, t}\ \{t: t \geq \|A_i x-b\|_2,\ i=1,\cdots,k\},
\]
which is a convex problem (SOCP).
\medskip

Other possibilities for $\U$, such as an ellipsoidal 
uncertainty for each row of $A$, also lead to SOCP
formulations.
% See Section 3.1 of Alizadeh/Goldfarb paper for more extensions.
% For example, $b$ may also lie in an uncertainty ellipsoid.
\end{cminipage}
\end{slide}

\end{comment}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}
  \begin{cminipage}{.96\textwidth}
   \title{Sufficient conditions (constraint qualifications) for strong duality}
      \par\vspace{0.0\semin}
\bi
\sitem
\textbf{Slater CQ for \eqref{eq:P}:}
if \eqref{eq:P} is strongly feasible, i.e.,\\
\hspace{50pt} \blue{$\exists\ y,s$ such that $A^* y + s = c,\ s \in \Int(K)$},\\
then\hspace{32pt} $v_P$ finite $\rra  v_P = v_D$ and $v_D$ is attained.
\sitem
\textbf{Slater CQ for \eqref{eq:D}:}
if \eqref{eq:D} is strongly feasible, i.e.,\\
\hspace{50pt} \blue{$\exists\ x$ such that $Ax=b,\ x \in \Int(K^*)$},\\
then\hspace{32pt} $v_D$ finite $\rra  v_P = v_D$ and $v_P$ is attained.
\ei
\medskip

Weaker sufficient conditions also exist, but strong
feasibility of \eqref{eq:P} and \eqref{eq:D} is necessary
for many classes of algorithms to work.
\bigskip

Q. What can we do if strong feasibility fails for \eqref{eq:P}?

A. Construct a \red{regularized} primal problem that:
\begin{itemize}
\item has the same feasible set as \eqref{eq:P};
\item is strongly feasible.
\end{itemize}
\end{cminipage}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}
  \begin{cminipage}{.9\textwidth}
   \title{Faces and minimal faces}
   \par\vspace{0.1\semin}
\begin{itemize}
\item
A convex set $F$ is a \red{face} of $K$, denoted $F \unlhd K$, if
\beas
 x,y \in K \text{  and  } \frac{x+y}{2} \in F \rra x,y \in F.
\eeas

\item
If $F \unlhd K$ and $F \ne \{0\},K$, write $F \lhd K$ (\red{a proper face}).
\bigskip

\begin{tabular}{ll}
\hspace{-9pt}
\begin{minipage}{150pt}
\item
If $F \unlhd K$, the \red{conjugate face} of $F$ is
\beas
  F^c := F^{\perp} \cap K^* \unlhd K^*.
\eeas
\end{minipage}
\hspace{3pt}\raisebox{-46pt}{\scalebox{.4}{\input{conjugate_face.pstex_t}}}%\vspace{-28pt}%%
\end{tabular}
\smallskip
\item
If $x \in \relint(F)$, then $F^c = \{x\}^{\perp} \cap K^*$.

\mitem
Let $\F_P := \{y: A^*y \preceq_K c\}$ denote the feasible
set of \eqref{eq:P}.

Assuming $\F_P$ is nonempty, the \red{minimal face}
of \eqref{eq:P} is
\beas
\blue{ f_P := \bigcap \{F \unlhd K: F \supset c-A^*(\F_P)\}. }
\eeas
\end{itemize}
\end{cminipage}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}
  \begin{cminipage}{.92\textwidth}
   \par\vspace{-0.4\semin}
   \title{Example}
   \par\vspace{0.3\semin}
In the earlier SDP example
\beas
  \sup\limits_y\;\left\{-y_2\ :\ \arr{ccc}{1+y_2&0&0\\0&y_1&y_2\\0&y_2&0} \mbox{ is PSD}\right\},
\eeas
Slater's CQ fails and the duality gap is $1$.
\medskip

The feasible set is
$\F_P = \{y \in \R^2: y_1 \geq 0,\ y_2 = 0\}$,\\
so the minimal face is
\beas
 f_P = \arr{cc}{\S^2_+&0\\0&0} \lhd \S^3_+ \ .
\eeas
\smallskip

More generally, if \eqref{eq:P} is feasible, then 
\beas
\blue{%
  A^*y \not\prec_K c \ \forall y
\text{ \black{ [Slater's CQ fails for \eqref{eq:P}] }} \llra f_P \lhd K.
}
\eeas
\end{cminipage}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}
  \begin{cminipage}{.99\textwidth}
   \title{Primal feasible set $\{y: A^* y \preceq_K c\}$}
   \par\vspace{0.2\semin}
\begin{center}
\scalebox{.5}{\input{feasible_set.pstex_t}}
\end{center}
\end{cminipage}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}
  \begin{cminipage}{.92\textwidth}
   \title{Regularization}
   \par\vspace{0.2\semin}
Borwein \& Wolkowicz (1981):
If Slater's CQ fails for \eqref{eq:P}, then \eqref{eq:P} is
equivalent to the \red{regularized primal problem}
\blue{%
\begin{align}
 \red{v_{RP}} &= \sup\limits_y\;\{\langle b,y \rangle :\ A^* y \preceq_{\red{f_P}} c\}.
    \tag{RP}\label{eq:RP}
\end{align}
}%
Its Lagrangian dual is
\blue{%
\begin{align}
 \red{v_{DRP}} &= \inf\limits_{x}\;\{\langle c,x \rangle :\ Ax=b,\ x \succeq_{\red{f_P^*}} 0\}.
    \tag{DRP}\label{eq:DRP}
\end{align}
}%
Slater's CQ holds for \eqref{eq:RP}, so if $v_{RP} = v_{DRP}$
is finite, then $v_{DRP}$ is attained, i.e.,~strong duality
holds for \eqref{eq:RP}.

Borwein \& Wolkowicz also gave an algorithm to compute $f_P$.

\bigskip
Difficulties:\\
(1) The algorithm requires the solution of 
several convex programs that are potentially much larger 
then the original problem \eqref{eq:P}.\\
(2) If Slater's CQ fails for \eqref{eq:D}, then 
each of these convex programs also fail to
satisfy Slater's CQ.
\end{cminipage}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}
  \begin{cminipage}{.92\textwidth}
   \title{Ramana's strong dual}
   \par\vspace{0.2\semin}
In 1995 Ramana proposed the
\red{Extended Lagrange-Slater dual (ELSD)} for \eqref{eq:P}
in the case of SDP. The construction of the dual takes advantage
of the well understood facial structure of $\Sn_+$.

\medskip
\textbf{Advantages:}\\
(1) The ELSD is written explicitly in terms of the original
data $(A,b,c)$, unlike the regularized dual of Borwein \& Wolkowicz.

\smallskip
(2) The size of the ELSD is polynomial in the size
of \eqref{eq:P}. In particular, the number of variables in
the ELSD is $\O(k n^2)$, where $k \leq \min\{m,n\}$ depends on
the original data. 

\medskip
\textbf{Disadvantages:}\\
(1) Solving ELSD using a primal-dual interior-point method may be
difficult since it might not satisfy Slater's CQ.
Slater's CQ may also fail for the Lagrangian dual of ELSD.
% If the original dual satisfies Slater, then so does ELSD.

\smallskip
(2) Size of the ELSD can potentially be very large.
% The SDP paper of Nesterov and Todd on page 787 shows a
% complexity per itertion of O(m^2 n^2), giving a complexity
% of O(m^2 n^2.5) for the IPM.
% $\O(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 $\O(n^2 (n^3)^2.5)$ arithmetic
% operations (ignoring structure and potential sparsity in ELSD).
\end{cminipage}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}
  \begin{cminipage}{.92\textwidth}
   \title{Towards a better regularization (1)}
   \par\vspace{0.3\semin}
In 1997, Ramana, Tun{\c{c}}el, \& Wolkowicz showed that
Ramana's ELSD is equivalent to (DRP) (the dual of the
regularized primal of Borwein \& Wolkowicz) in the case of SDP.

\medskip
For SDP, both approaches require the solution of one or more
potentially large SDPs (compared to the size of the original
problem) that need not satisfy Slater's CQ.

\bigskip
\textbf{Goal}: An algorithm to solve \eqref{eq:P} that
satisfies the following properties:\\[2pt]
(1) It recognizes if \eqref{eq:P} satisfies Slater's CQ and if
\eqref{eq:P}--\eqref{eq:D} has a zero duality gap;\\
(2) The size of any intermediate convex program solved does
not exceed that of \eqref{eq:P} or \eqref{eq:D};\\
(3) Any intermediate convex programs to be solved are well-posed,
i.e.,~Slater's CQ holds for primal and dual.
\end{cminipage}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}
  \begin{cminipage}{.92\textwidth}
   \vspace{-0.3\semin} 
   \title{Towards a better regularization (2)}
   \par\vspace{0.6\semin} 
Suppose that \eqref{eq:P} is feasible.\\
Then exactly one of the following two systems is consistent:

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

(2)\; $A^*y \prec_K c$\; [Slater's CQ holds for \eqref{eq:P}].

\bigskip
$\rightarrow$ In theory, we can solve
\[
\min\{0: Ax=0,\ \langle c,x \rangle = 0,\ 0 \ne x \succeq_{K^*} 0\}
\]
to determine if Slater's CQ fails for \eqref{eq:P}.

\bigskip
But this problem need not satisfy Slater's CQ.

\bigskip
So how can we solve (1)?
\end{cminipage}
\end{slide}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}
  \begin{cminipage}{.95\textwidth}
   \title{The Auxiliary problem (1)}
   \par\vspace{0.1\semin} 
Let $e \in \Int(K) \cap \Int(K^*)$, and consider the following
auxiliary problem:
\blue{%
\be
\begin{array}{rcl}
\alpha^* := \min\limits_{x,\alpha} & \alpha \\
\mbox{s.t.} & Ax = 0 \\
  &  \langle c,x \rangle = 0\\
  &  x + \alpha e \succeq_{K^*} 0\\
  &  \langle e, x \rangle \leq 1.
    \tag{$\A$}\label{eq:A}
\end{array}
\ee
}

\bi
\item
Assume $c \notin \Range(A^*)$, otherwise we can
remove $\langle c,x \rangle = 0$.
\item
The size of \eqref{eq:A} is essentially that of \eqref{eq:D}.
\item
Slater's CQ holds for \eqref{eq:A} and its dual.
\item
A strongly feasible primal-dual point is easily found.
\item
Applying a primal-dual IPM, we need to follow the central
path closely at the end of the algorithm. 
\ei
\end{cminipage}
\end{slide}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}
  \begin{cminipage}{1.00\textwidth}
   \vspace{-0.1\semin} 
   \title{The Auxiliary problem (2)}
   \par\vspace{-0.3\semin} 
\blue{%
\be
\begin{array}{rcl}
\alpha^* := \min\limits_{x,\alpha} & \alpha \\
\mbox{s.t.} & Ax = 0 \\
  &  \langle c,x \rangle = 0\\
  &  x + \alpha e \succeq_{K^*} 0\\
  &  \langle e, x \rangle \leq 1.
    \tag{$\A$}\label{eq:A}
\end{array}
\ee
}\\[-4pt]

\ptsize{9}
What does a solution to \eqref{eq:A} tell us about
\eqref{eq:P}--\eqref{eq:D}?

\textbf{Theorem:} Let \eqref{eq:P} be feasible. Then the $x$
component of the central path for \eqref{eq:A} and its dual
converges to a point in \blue{$\relint(\face(R))$}, where
\blue{%
\beas
   R := \{x :\ Ax = 0,\ \langle c,x \rangle = 0,\ x \succeq_{K^*} 0\}.
\eeas
}%
Moreover, since
$f_P \subset \{x^*\}^{\perp} \cap K = [\face(R)]^c \unlhd K$,
either:

\smallskip
(1) $\alpha^* = 0$ and $x^* = 0$, so Slater's CQ holds for
\eqref{eq:P}, or\\
(2) $\alpha^* = 0$ and $0 \ne x^* \succeq_{K^*} 0$, so
$f_P \subset \{x^*\}^{\perp} \cap K \red{\lhd} K$, or\\ 
(3) $\alpha^* < 0$ and $x^* \succ_{K^*} 0$, so
Slater's CQ holds for \eqref{eq:D}.
\end{cminipage}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}
  \begin{cminipage}{.96\textwidth}
   \vspace{-0.2\semin}
   \title{Our algorithm}
   \par\vspace{0.3\semin}
\textbf{Input:} $A,b,c,K$, and $\varepsilon > 0$.

\smallskip
\textbf{Output:} optimal $\alpha^*$ and $x^* \in \relint(\face(R))$
for \eqref{eq:A}.

\medskip
\textbf{While} $\|x^*\| > \varepsilon$\\[2pt]

\hspace{20pt}
\begin{minipage}{250pt}
\smallskip
\textbf{If} $\alpha^* < 0$, then $x^* \succ_{K^*} 0$, so
$f_P = \{0\}$.\\   Hence optimal $y$ for \eqref{eq:P}
satisfies $A^* y = c$, and exit algorithm.

\medskip
\textbf{Else}
(1) Any feasible $y$ for \eqref{eq:P} satisfies
$c - A^*y \in [\face(R)]^c \lhd K$, giving a \red{reduced
primal problem} with cone \blue{$K' = [\face(R)]^c$}.

\smallskip
(2) Solve \eqref{eq:A} and its dual with cone $K'$ to find
optimal $\alpha^*, x^*$.\\
\textbf{End}
\end{minipage}

\textbf{End}

\medskip
Finally, solve reduced primal problem for which Slater's CQ holds.\\
(This provides a \red{certificate of optimality}.)

\bigskip
For cones such as $\Sn_+$ \& SOC, auxiliary problems
get progressively smaller.
\end{cminipage}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}
  \begin{cminipage}{.92\textwidth}
   \par\vspace{-0.1\semin}
   \title{The SDP case}
   \par\vspace{0.1\semin}
The faces of $\Sn_+$ are of the form 
\blue{
\beas
\hspace{8pt}
 F   &=& [P\:\: Q]\sarr{\S^{\red{r}}_+&0\\0&0} [P\:\: Q]^T = P \S^{\red{r}}_+ P^T,\\
\text{with}\quad
 F^c &=& [P\:\: Q]\sarr{0&0\\0&\S^{\red{n-r}}_+} [P\:\: Q]^T = Q \S^{\red{n-r}}_+ Q^T,
\eeas
}
where $[P\:\: Q]$ is orthogonal.

\medskip
Suppose that $x^* = [P\; Q]\sarr{D&0\\0&0}[P\; Q]^T$,
where $D \in \R^{r \times r}$.

\medskip
Then
$\face(R) = \face(x^*) = [P\:\: Q]\sarr{\S^r_+&0\\0&0} [P\:\: Q]^T$,
so $K' = [\face(R)]^c = Q \S^{n-r}_+ Q^T$.

\medskip
So reduced primal problem has constraints 
\blue{$A^*y \preceq_{K'} c$}.

This is equivalent to 
[\blue{$Q^T(A^*y)Q \preceq_{\S^{n-r}_+} Q^TcQ$ and $(c - A^*y)P = 0$}],
so the reduced primal problem lies in a lower dimensional space.

\medskip
Using $(c - A^*y)P = 0$ we can always eliminate some $y_i$'s,
so reduced primal has lower dimension \textit{and} fewer variables.
% We've assumed that \eqref{eq:P} is feasible).
% 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{cminipage}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}
  \begin{cminipage}{.98\textwidth}
      \vspace{-0.6\semin}
   \title{Numerical Experiments (1)}
      \par\vspace{0.5\semin}
For the earlier SDP with $K = \S^3_+$ and a duality gap of $1$,
we obtained (using Sedumi) the primal ``solution''
\begin{align*}
y = \arr{c}{ 4.6 \times 10^7 \\ -0.38 }, \qquad
S = \arr{ccc}{ 0.62 & 0 & 0 \\
         0 & 4.6 \times 10^7\hspace{-10pt}&  -0.38\\
         0 & -0.38  &  0}\!.
\end{align*}
\bigskip

Our code requires two iterations, giving a correct primal solution:
\begin{align*}
y^* =
\arr{c}{ 1.50\\ 0},\quad
S^* =
\arr{ccc}{ 1.00 & 0 & 0\\
           0 & 1.50 & 0\\
           0 & 0 & 0}.
\end{align*}
\end{cminipage}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\ptsize{9}
\begin{slide}
  \begin{cminipage}{.92\textwidth}
   \title{Numerical Experiments (2)}
   \par\vspace{0.1\semin}
Let $e_i$ be the $i$th unit vector in $\Rn$.\\
Consider the SDP with $m=n \geq 3$, $b = e_2$, $c = 0$, and
\ptsize{8}
\beas
 A^*y = 
  \arr{ccccccc}{y_1&y_2&y_3&y_4&\cdots&y_{n-1}&y_n\\y_2&y_3&&&&&\\y_3&&y_4&&&&\\y_4&&&&&&\\\vdots&&&&\ddots&&\\y_{n-1}&&&&&y_n&\\y_n&&&&&&0}.
\eeas 
\ptsize{9}
Here $\F_P = \{y \in \R^n: y_1 \leq 0,\ y_2 = \cdots = y_n = 0\}$,
$f_P = \{Z \in \Sn_+: Z_{11} \geq 0,\ Z_{ij} = 0\ \forall (i,j) \ne (1,1)\}$,\\
and \eqref{eq:D} is infeasible.
 
\smallskip
For various $n$, Sedumi gives an incorrect primal and dual solution
with a duality gap of $-1$, whereas our algorithm gives a correct
primal optimal solution.
\end{cminipage}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}
  \begin{cminipage}{.95\textwidth}
   \vspace{-1.1\semin}
   \title{Strict complementarity and nonzero gaps (1)}
   \par\vspace{0.6\semin}
Write \eqref{eq:P}--\eqref{eq:D} in \red{symmetric subspace} form:
\medskip

Let $\bar{x}, \bar{y}$, and $\bar{s}$ satisfy $A\bar{x}=b$ and
$A^*\bar{y} + \bar{s} = c$, and let $\L = {\rm Nullspace}(A)$.
\bigskip

The original primal-dual pair \eqref{eq:P}--\eqref{eq:D} 
can then be written as
\blue{%
\begin{align*}
 v_P &= \langle b,\bar{y} \rangle
      - \inf\limits_{s}\;\{\langle \bar{x},s \rangle :\ s \in (\bar{s}+\L^{\perp}) \cap K\},\\ 
 v_D &= \langle c,\bar{x} \rangle
      + \inf\limits_{x}\;\{\langle \bar{s},x \rangle :\ x \in (\bar{x}+\L) \cap K^*\}.
\end{align*}
}% end of \blue

\bigskip
Set of primal \red{recession directions} is \blue{$\L^{\perp} \cap K$};\\
set of dual \red{recession directions} is \blue{$\L \cap K^*$}.
\end{cminipage}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}
  \begin{cminipage}{.99\textwidth}
    \vspace{-0.5\semin}
   \title{Strict complementarity and nonzero gaps (2)}
   \vspace{0.4\semin}
The faces $F_1 \unlhd K$ and $F_2 \unlhd K^*$ form a:
\begin{itemize}
\mitem
\red{complementarity partition} of $K$ and $K^*$ if
\blue{$F_1 \subset F_2^c$} and \blue{$F_2 \subset F_1^c$};
\mitem
\red{strict complementarity partition} of $K$ and $K^*$ if 
\blue{$F_1 = F_2^c$} and \blue{$F_2 = F_1^c$}.
\end{itemize}

\bigskip
A complementarity partition is said to be \red{proper} if
$F_1$ and $F_2$ are proper faces.
\bigskip

$\rightarrow$ Existence of a proper strict complementarity
partition is important in optimization.
\bigskip

Fact: $\face(\L^\perp \cap K)$ and $\face(\L \cap K^*)$ form a
complementarity partition.
\bigskip

$\rightarrow$ Whether \eqref{eq:P}--\eqref{eq:D} has a finite nonzero
duality gap depends on whether the complementarity partition
is proper and strict. 
\end{cminipage}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}
  \begin{cminipage}{.95\textwidth}
   \vspace{-0.3\semin}
   \title{Strict complementarity and nonzero gaps (3)}
   \par\vspace{0.4\semin}
\textbf{Theorem:} Let $K$ be a proper cone, and let\\
$F_1 := \face(\L^\perp \cap K)$ and $F_2 := \face(\L \cap K^*)$.
\smallskip

(1) If $(F_1,F_2)$ form a proper complementarity partition
but not a strict complementarity partition, then there exists $\bar{s}$
and $\bar{x}$ such that \eqref{eq:P}--\eqref{eq:D}
with data $(\L,K,\bar{x},\bar{y},\bar{s})$ has a finite nonzero duality gap.

\medskip

(2) If (a) \eqref{eq:P}--\eqref{eq:D} with data $(\L,K,\bar{x},\bar{y},\bar{s})$
has a finite nonzero duality gap, and\\
(b) the primal and dual objective functions are constant along all
feasible recession directions,\\
then $(F_1,F_2)$ forms a proper complementarity partition
but not a strict complementarity partition.

\bigskip
This result can be used to generate primal-dual instances
possessing a finite nonzero duality gap.
\end{cminipage}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}
  \begin{cminipage}{.95\textwidth}
   \par\vspace{-0.2\semin}
   \title{Generating problems with nonzero gaps}
   \par\vspace{0.2\semin}
For SDP, an instance with $K = \Sn_+$ is generated as follows:
\medskip

(1) Choose positive integers $n,p,d$ with $n > p+d$.\\
Take $e = I_n \in \Int(K) \cap \Int(K^*).$

\smallskip
(2) Choose a subspace $\L$ and orthogonal matrix $Q$ such that
\beas
  \face(\L^{\perp} \cap K)= Q\sarr{0&&\\&0&\\&&\blue{\S^p_+}}Q^T, \quad
  \face(\L \cap K^*)= Q\sarr{\blue{\S^d_+}&&\\&0&\\&&0}Q^T.
\eeas

These faces form a complementarity partition,
but not a strict complementarity partition.

\smallskip
(3) Choose a nonzero $U \in \S^{n-p-d}_+$, and let 
\beas
\bar{s} = \bar{x} = Q \sarr{0&&\\&\blue{U}&\\&&0} Q^T.
\eeas

The duality gap between the resulting SDPs is
 $\langle \bar{s},\bar{x} \rangle = \|U\|_F^2 > 0$.

\medskip
We have written a code to implement this.
\end{cminipage}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}
  \begin{cminipage}{.95\textwidth}
   \title{Conclusions and future work}
   \vspace{-0.1\semin}
\label{final_page}
\begin{itemize}
\mitem
We gave a stable algorithm to solve conic problems for which 
Slater's CQ fails.
\mitem
The 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.
\mitem
Failure of strict complementarity for the associated 
recession problems is closely related to the existence of
instances having a finite nonzero duality gap, giving a
means of testing our algorithm.
\mitem
We intend to refine our code and test it on larger SDPs
having a finite nonzero duality gap.
\mitem
Perform 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.
\end{itemize}
\end{cminipage}
\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}
