\documentclass[notes]{beamer}
\usetheme{Warsaw}
\usepackage{graphics,graphicx} 
\usepackage{xcolor} 
\usepackage{cite} 
%\usepackage[showframe=true]{geometry}
\usepackage{changepage}
%\usepackage[sort&compress,numbers]{natbib}  % alternative to cite???
%\usepackage{mathrsfs} 

\usepackage{amsmath, amssymb, amsmath}


\usepackage{epsfig}
\usepackage{pdfpages}
\usepackage{multirow}
%\usepackage{kbordermatrix}
\usepackage{ifthen}
\usepackage{kbordermatrix}
\usepackage{bbm}
\usepackage{algorithm}
\usepackage{algorithmic}


\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?

\newcommand{\cm}{\color{magenta}}
\newcommand{\cb}{\color{black}}
\newcommand{\cg}{\color{lgreen}}
\newcommand{\crr}{\color{rred}}
\newcommand{\co}{\color{olive}}
\def\crb{\color{rblue}}
\def\crr{\color{rred}}
\def\clg{\color{lgreen}}
\def\cbr{\color{brown}}
\def\cc{\color{cyan}}
\def\cy{\color{oyellow}}


\def\Rnpp{\mathbb{R}_{++}^n}
\newcommand{\cI}{{\mathcal I}}
\newcommand{\cC}{{\mathcal C}}
\newcommand{\cB}{{\mathcal B}}
\newcommand{\cN}{{\mathcal N}}
\newcommand{\cS}{{\mathcal S}}
\def\<{\langle}
\def\>{\rangle}

\def\Rnbyn{\mathbb{R}^{n\times n}}
\def\bY{\overline{Y\strut}}

\def\R{\mathbb{R}}
\def\Ss{\mathbb{S}}
\def\Er{\mathbb{E}}
\def\Yr{\mathbb{Y}}
\def\Rm{\mathbb{R}^m}
\def\Rmn{\mathbb{R}^{m\times n}}
\def\Rn{\mathbb{R}^n}
\def\Rnn{\mathbb{R}^{n\times n}}
\def\Rnk{\mathbb{R}^{nk}}
\def\Rno{\mathbb{R}^{n+1}}
\def\Rnp{\mathbb{R}_+^n}
\def\Rmp{\mathbb{R}_+^m}
\def\Smn{\Ss_+^{m+n}}
\def\Snn{\Ss^{n^2+1}}
\def\Sc{\mathbb{S}}

\def\Ro{\mathbbm{1}}

\def\hY{\widehat{Y}}
\def\whV{\widehat{V}}

\newcommand{\QED}{\rule{8pt}{8pt}}
\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{\II}{{\mathcal I}}
\newcommand{\GG}{{\mathcal G}}
\newcommand{\cA}{{\mathcal A}}
\newcommand{\hV}{{\widehat{V}}}
\newcommand{\cL}{{\mathcal L}}
\newcommand{\cF}{{\mathcal F}}
\newcommand{\RR}{{\mathcal R}}
\newcommand{\cR}{{\mathcal R}}
\newcommand{\VV}{{\mathcal V}}
\newcommand{\EE}{{\mathcal E}}
\newcommand{\KK}{{\mathcal K}}
\newcommand{\LL}{{\mathcal L}}
\def\Ssum{\mathop{\mathcal S_\Sigma}}
\def\Sprod{\mathop{\mathcal S_\Pi}}
\newcommand{\TT}{{\mathcal T}}
\newcommand{\CC}{{\mathcal C}}
\newcommand{\MM}{{\mathcal M}}
\newcommand{\MMm}{{\mathcal M}_m}
\newcommand{\NN}{{\mathcal N}}
\newcommand{\YY}{{\mathcal Y}}
\newcommand{\FF}{{\mathcal F}}
\newcommand{\F}{{\mathcal F}}
\newcommand{\Scal}{{\mathcal S}}
\newcommand{\ZZ}{{\mathcal Z}}
\newcommand{\PP}{{\mathcal P} }
\newcommand{\cP}{{\mathcal P} }
%\newcommand{\gglt}{{g^{\scriptsize {lt}}}}
\newcommand{\gglt}{{g^{\scriptsize {l}}}}
\newcommand{\ggeq}{{g^{\scriptsize e}}}
%\newcommand{\Plt}{{\PP^{\scriptsize {lt}}}}
\newcommand{\Plt}{{\PP^{\scriptsize {l}}}}
\newcommand{\Peq}{{\PP^{\scriptsize e}}}
%\newcommand{\Alt}{{A^{\scriptsize {lt}}}}
\newcommand{\Alt}{{A^{\scriptsize {l}}}}
\newcommand{\Aeq}{{A^{\scriptsize e}}}
%\newcommand{\clt}{{c^{\scriptsize {lt}}}}
\newcommand{\clt}{{c^{\scriptsize {l}}}}
\newcommand{\ceq}{{c^{\scriptsize e}}}
%\newcommand{\xlt}{{x^{\scriptsize {lt}}}}
\newcommand{\xlt}{{x^{\scriptsize {l}}}}
\newcommand{\xeq}{{x^{\scriptsize e}}}
\newcommand{\MC}{{\bf{\rm MC\,}}}
\newcommand{\MCp}{{\bf{\rm MC}}}
\newcommand{\sPRSM}{{\bf{\rm sPRSM\,}}}
\newcommand{\sPRSMp}{{\bf{\rm sPRSM}}}
\newcommand{\ADMM}{{\bf{\rm ADMM\,}}}
\newcommand{\ADMMp}{{\bf{\rm ADMM}}}
\newcommand{\FR}{{\bf{\rm FR\,}}}
\newcommand{\FRp}{{\bf{\rm FR}}}
\newcommand{\FRSMR}{{\bf{\rm FRSMR\,}}}
\newcommand{\FRSMRp}{{\bf{\rm FRSMR}}}
\newcommand{\DNN}{{\bf{\rm DNN\,}}}
\newcommand{\DNNp}{{\bf{\rm DNN}}}
\newcommand{\GP}{{\bf{\rm GP\,}}}
\newcommand{\GPp}{{\bf{\rm GP}}}
\newcommand{\QAP}{{\bf{\rm QAP\,}}}
\newcommand{\QAPp}{{\bf{\rm QAP}}}
\newcommand{\QQP}{{\bf{\rm QQP\,}}}
\newcommand{\QQPp}{{\bf{\rm QQP}}}
\newcommand{\rPRSM}{{\bf{\rm PRSM\,}}}
\newcommand{\rPRSMp}{{\bf{\rm PRSM}}}
\newcommand{\LSF}{{\bf{\rm LSF\,}}}
\newcommand{\LSFp}{{\bf{\rm LSF}}}
\newcommand{\BFS}{{\bf{\rm BFS\,}}}
\newcommand{\BFSp}{{\bf{\rm BFS}}}
\newcommand{\SDP}{{\bf{\rm SDP\,}}}
\newcommand{\SDPp}{{\bf{\rm SDP}}}
\newcommand{\LP}{{\bf{\rm LP\,}}}
\newcommand{\LPp}{{\bf{\rm LP}}}
\newcommand{\EDM}{{\bf{\rm EDM\,}}}
\newcommand{\EDMp}{{\bf{\rm EDM}}}
\newcommand{\EDMC}{{\bf{\rm EDMC\,}}}
\newcommand{\SNLp}{{\bf{\rm SNL}}}
\newcommand{\SNL}{{\bf{\rm SNL\,}}}
\newcommand{\NLLS}{{\bf{\rm NLLS\,}}}
\newcommand{\sd}{{\bf{\rm sd\,}}}




%\newcommand{\trace}{{\rm trace\,}}
\DeclareMathOperator{\cut}{{cut}}
\DeclareMathOperator{\nul}{{Null}}
\DeclareMathOperator{\codim}{{codim}}
\def\norm#1{{\left\lVert{#1}\right\rVert}}

\DeclareMathOperator{\tr}{trace}
\DeclareMathOperator{\supp}{supp}
\DeclareMathOperator{\trace}{trace}
\DeclareMathOperator{\conv}{conv}
\DeclareMathOperator{\Null}{Null}
\DeclareMathOperator{\nullity}{nullity}
\DeclareMathOperator{\Range}{Range}
\DeclareMathOperator{\range}{Range}
\DeclareMathOperator{\face}{face}
\DeclareMathOperator{\dist}{dist}
\DeclareMathOperator{\arrow}{arrow}
\DeclareMathOperator{\BoDiag}{B^oDiag}
\DeclareMathOperator{\bodiag}{b^odiag}
\DeclareMathOperator{\oodiag}{o^odiag}
\DeclareMathOperator{\OoDiag}{O^oDiag}
\DeclareMathOperator{\Arrow}{Arrow}
%\newcommand{\face}{{\rm face\,}}% smallest face containing a set
\newcommand{\facee}{{\rm face^{ef}\,}}% smallest face containing a set
\DeclareMathOperator{\argmin}{argmin}
\DeclareMathOperator{\argmax}{argmax}
%\newcommand{\relint}{{\rm relint\,}}
\DeclareMathOperator{\cone}{cone}
%\newcommand{\cone}{{\rm cone\,}}
\newcommand{\sspan}{{\rm span\,}}
%\newcommand{\Sn}{{\mathcal S^n\,}}
\newcommand{\En}{{{\mathcal E}^n} }
\newcommand{\Ek}{{{\mathcal E}^k} }
\newcommand{\rank}{{\rm rank\,}}
\newcommand{\DD}{{\mathcal D} }
\newcommand{\cD}{{\mathcal D} }
\newcommand{\corr}{{\rm corr\,}}
\newcommand{\its}{{\rm its\,}}
\newcommand{\stitle}[1]{\begin{center} {\bf\large {#1} } \end{center}}
\newcommand{\diag}{{\rm diag\,}}
\newcommand{\Diag}{{\rm Diag\,}}
%\newcommand{\Ss}{{\mathcal S}}
\newcommand{\Ekyb}{{\mathcal E}^{n}(1\!:\!k,\bar D)}
\newcommand{\Eayb}{{\mathcal E}^{n}(\alpha,\bar D)}
\newcommand{\Snm}{{\mathcal S}^{n-1} }
\newcommand{\hn}{{\mathcal H}^n }
\newcommand{\D}{{\mathcal D_n} }
\newcommand{\E}{{\mathcal E_n} }
\newcommand{\Sd}{{\mathcal S}_d }
\newcommand{\Sh}{{\mathcal S}_H }
\newcommand{\svec}{{\rm svec\,}}
\newcommand{\sMat}{{\rm sMat\,}}
\newcommand{\sblk}{{\rm sblk\,}}
\newcommand{\sBlk}{{\rm sBlk\,}}
\newcommand{\blk}{{\rm Blk\,}}
\DeclareMathOperator{\offDiag}{{offDiag}}
\DeclareMathOperator{\embdim}{{embdim}}
\DeclareMathOperator{\usMat}{{us2Mat}}
\DeclareMathOperator{\usvec}{{us2vec}}
\newcommand{\kvec}{{\rm vec\,}}
\newcommand{\Mat}{{\rm Mat\,}}
\newcommand{\Sk}{\Ss^k}%
\newcommand{\Skp}{\Ss^k_+}%
\newcommand{\Sno}{\Ss^{n+1}}%
\newcommand{\Snop}{\Ss^{n+1}_+}%
\newcommand{\Snp}{\Ss^n_+}%
\newcommand{\Snpp}{\Ss^n_{++}}%
\newcommand{\Smnp}{\Ss^{m+n}_{+}}%
\newcommand{\Srpp}{\Ss^r_{++}}%

\newcommand{\Sayb}{{\mathcal S}^{n}(\alpha,\bar Y)}
\newcommand{\Sapyb}{{\mathcal S}_+^{n}(\alpha,\bar Y)}
\newcommand{\Skyb}{{\mathcal S}^{n}(1\!:\!k,\bar Y)}
\newcommand{\Skpyb}{{\mathcal S}_+^{n}(1\!:\!k,\bar Y)}
\newcommand{\Sok}{{\mathcal S}^{1\!:\!k}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% from cone paper

\newcommand{\B}{\mathcal{B}}%
\newcommand{\C}{\mathcal{C}}%
\newcommand{\G}{\mathcal{G}}%
\newcommand{\K}{\mathcal{K}}%
\renewcommand{\L}{\mathcal{L}}%
\newcommand{\M}{\mathcal{M}}%
\newcommand{\N}{\mathcal{N}}%
\newcommand{\QQ}{\mathcal{Q}}%
\newcommand{\OO}{\mathcal{O}}%
\renewcommand{\S}{\mathbb{S}}%
\renewcommand{\P}{\mathbb{P}}%
\renewcommand{\D}{\mathbb{D}}%
\newcommand{\RP}{\mathbb{RP}}%
\newcommand{\DRP}{\mathbb{DRP}}%
\newcommand{\X}{\mathcal{X}}%
\newcommand{\Int}{{\rm int}}% interior of a set


\newcommand{\rra}{\;\ensuremath{\Longrightarrow}\;}%       ===>
\newcommand{\llra}{\;\ensuremath{\Longleftrightarrow}\;}%  <===>
\newcommand{\spanl}{{\rm span}}%
\newcommand{\trc}{{\rm trace\,}}%
\newcommand{\bpm}{\begin{pmatrix}}
\newcommand{\bem}{\begin{pmatrix}}
\newcommand{\epm}{\end{pmatrix}}
\newcommand{\eem}{\end{pmatrix}}

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


% Vris'

\newcommand*{\real}{\mathbb{R}}
\newcommand{\set}[1]{\left\{ #1 \right\} }
\newcommand{\inprod}[1]{\left\langle #1 \right\rangle}
\newcommand{\bmat}[1]{\begin{bmatrix} #1 \end{bmatrix}}
\newcommand{\pmat}[1]{\begin{pmatrix} #1 \end{pmatrix}}

\DeclareMathOperator{\interior}{int}
\DeclareMathOperator{\relint}{ri}
\DeclareMathOperator{\ri}{ri}
% cone of positive semidefinite matrices
% \Sn
% \Sn[V]
\newcommand{\Sn}[1][]{\mathcal{S}^{\ifthenelse{\equal{#1}{}}{n}{#1}}\,}
% cone of positive semidefinite matrices
% \Snp
% \Snp[V]
%\newcommand{\Snp}[1][]{\mathcal{S}_+^{\ifthenelse{\equal{#1}{}}{n}{#1}}\,}
% cone of positive semidefinite matrices
% \Snpp
% \Snpp[V]
%\newcommand{\Snpp}[1][]{\mathcal{S}_{++}^{\ifthenelse{\equal{#1}{}}{n}{#1}}\,}

\newenvironment{noteV}{\begin{quote}\color{olive}
    \footnotesize\sf VC $\heartsuit$~}{\end{quote}}
\newenvironment{noteH}{\begin{quote}\small\sf HW $\clubsuit$~}
    {\end{quote}}



\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}

\begin{document}


\title{
\color{blue} 
Linear Programming:
\begin{flushleft}
Part (i): Strict Feasibility and Degeneracy 
\\Part (ii): Exterior Point Path Following Algorithm
\end{flushleft}
}
\author[Wolkowicz]
{
Henry Wolkowicz
\\{\tiny Dept. Comb. and Opt., University of Waterloo, Canada}
\vspace{-.35in}
}
\vspace{-3in}
%\vspace{-.23in}

%\institute{
%\begin{small}
%%\vspace{1em}
%\end{small}
%%(Parts of this talk represent work based on Refs:
%%\cite{bw2,bw1,KrislockWolk:10,ScTuWonumeric:07,ForbesVrisWolk:11}
%%)\\

%}

\date{
%\vspace{-.48in}
%\begin{figure}[htb]
%\includegraphics[width=0.5\textwidth]{SNLfig.eps}
%\includegraphics[width=0.75\textwidth]{fig300.eps}
%\includegraphics[angle=270,width=1.00\textwidth]{CMSpic.pdf}
%\includegraphics[width=.5]{CMSpic.pdf}
%\includegraphics[width=0.25\textwidth]{18-fall-Campus.pdf}
%\includegraphics[width=2.8cm,height=2.8cm,keepaspectratio]{ospreyTHREEjul2520.pdf}
%\epsfxsize=180pt
%\centerline{\epsfbox{fig300.eps}}
%\centerline{\epsfbox{SNLfig.eps}}
%\end{figure}
%\vspace{.09in}
\tiny Monday April 10, 2023 
\vspace{.09in}
\small{
%\href{https://www2.cms.math.ca/Events/winter21/sessions_scientific#vaa}
%{
%Variational Analysis: Applications and Theory\\ 
%\\ 
%At: 
%{\crr
%\href{https://www.informs.org/Meetings-Conferences/INFORMS-Conference-Calendar/2022-INFORMS-Annual-Meeting}{
 %2022 INFORMS Annual Meeting
%}}
%\\ Thursday 19th and Friday 20th May 2022 
%Workshop on Numerical Linear Algebra and Optimization
\begin{figure}[htb]
\epsfxsize=105pt
\centerline{at: \hspace{.4in} \epsfbox{logo-mathstat-orng-dip.pdf}}
%\centerline{\epsfbox{CAIMSubc.jpg}}
%\centerline{\epsfbox{ttl-western-logo-trans.eps}}
%\centerline{\epsfbox{Mallardjpg.pdf}}
%\centerline{\epsfbox{ttl-western-logo-trans.pdf}}
%\vspace{-.12in}
\end{figure}
%\vspace{.09in}
%	{\crb   
% joint work with:  Jiyoung Im, Univ. of Waterloo
%	}
}
}


\subject{Talks}

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

%\input{ainput}
%----------------------------------------------------------
\begin{frame}
\titlepage
\end{frame}
%----------------------------------------------------------


\title{
\color{blue} 
LP Part (i): Strict Feasibility and Degeneracy 
}
\author[Wolkowicz]
{
Henry Wolkowicz
\\{\tiny Dept. Comb. and Opt., University of Waterloo, Canada}
\vspace{-.35in}
}
\vspace{-3in}
%\vspace{-.23in}

%\institute{
%\begin{small}
%%\vspace{1em}
%\end{small}
%%(Parts of this talk represent work based on Refs:
%%\cite{bw2,bw1,KrislockWolk:10,ScTuWonumeric:07,ForbesVrisWolk:11}
%%)\\

%}

\date{
%\vspace{-.48in}
%\begin{figure}[htb]
%\includegraphics[width=0.5\textwidth]{SNLfig.eps}
%\includegraphics[width=0.75\textwidth]{fig300.eps}
%\includegraphics[angle=270,width=1.00\textwidth]{CMSpic.pdf}
%\includegraphics[width=.5]{CMSpic.pdf}
%\includegraphics[width=0.25\textwidth]{18-fall-Campus.pdf}
%\includegraphics[width=2.8cm,height=2.8cm,keepaspectratio]{ospreyTHREEjul2520.pdf}
%\epsfxsize=180pt
%\centerline{\epsfbox{fig300.eps}}
%\centerline{\epsfbox{SNLfig.eps}}
%\end{figure}
%\vspace{.09in}
\tiny Monday April 10, 2023 
\vspace{.09in}
\small{
%\href{https://www2.cms.math.ca/Events/winter21/sessions_scientific#vaa}
%{
%Variational Analysis: Applications and Theory\\ 
%\\ 
%At: 
%{\crr
%\href{https://www.informs.org/Meetings-Conferences/INFORMS-Conference-Calendar/2022-INFORMS-Annual-Meeting}{
 %2022 INFORMS Annual Meeting
%}}
%\\ Thursday 19th and Friday 20th May 2022 
%Workshop on Numerical Linear Algebra and Optimization
\begin{figure}[htb]
\epsfxsize=105pt
\centerline{at: \hspace{.4in} \epsfbox{logo-mathstat-orng-dip.pdf}}
%\centerline{\epsfbox{CAIMSubc.jpg}}
%\centerline{\epsfbox{ttl-western-logo-trans.eps}}
%\centerline{\epsfbox{Mallardjpg.pdf}}
%\centerline{\epsfbox{ttl-western-logo-trans.pdf}}
%\vspace{-.12in}
\end{figure}
%\vspace{.09in}
	{\crb   
 joint work with:  Jiyoung Im, Univ. of Waterloo
	}
}
}


\subject{Talks}

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

%\input{ainput}
%----------------------------------------------------------
\begin{frame}
\titlepage
\end{frame}
%----------------------------------------------------------


%----------------------------------------------------------
%\begin{frame}
%	\frametitle{Contents}
%\tableofcontents
%\end{frame}
%----------------------------------------------------------


%----------------------------------------------------------
%\begin{frame}[allowframebreaks]

\begin{frame}
\frametitle{ {Motivation/Main Results} }


\begin{block}{Background}
\begin{itemize}
\item 
Currently: {\crr simplex and interior point} methods are
{\crb most popular} algorithms for solving linear programs, \LPp s.

\item
Unlike general conic programs, (finite) \LPp s 
do {\crr not require strict feasibility} for {\crb strong duality}.
 Hence strict feasibility is often less emphasized. 

\end{itemize}

\end{block}
\begin{block}{We show that lack of strict feasibility, \LSF:}
\begin{enumerate}

\item
causes {\crr numerical difficulties} in both simplex and interior point methods.

\item 
 and {\crr \LSF $\implies$ all} basic feasible solutions, {\crr \BFSp}, 
are \\ \qquad \qquad \qquad \qquad   {\crr degenerate}
\end{enumerate}
\end{block}
\begin{block}{We present}
an extension of Phase-I of simplex method for {\crr
preprocessing} for {\crr strict feasibility}
\end{block}


\end{frame}
\begin{frame}
\frametitle{Standard Background and Notation for \LPp}



	\begin{block}{Feasible \LPp s; {\crr standard form} (with \underline{FINITE} 
opt. value)}
\[
\begin{array}{rcl}
(\cP) \quad \text{(finite)  } p^*=&
          \min_x & c^Tx\\ 
           &\text{s.t.}&  Ax =b \in \Rm \\
           &&  x \in \Rnp
\end{array}
\] 
		$\rank(A) = m$;  with {\crr feasible set} 
\[
\cF = \{x \in \Rn: Ax = b, \ x \ge 0 \}
\]
\end{block}
\begin{block}{Dual LP}
\[
\begin{array}{rcl}
(\cD) \quad  p^*=d^*=&
          \max & b^Ty\\ 
           &\text{s.t.}&  A^Ty \leq  c \in \Rn \\
           &&  y \in \Rm
\end{array}
\] 
(equivalently $A^Ty+s = c, s\geq 0$ slack)
\end{block}


\end{frame}
\begin{frame}
\frametitle{Strict Feasibility, Slater, Mangasarian-Fromovitz CQ}



\begin{block}{Feasible \LPp s; standard form (with \underline{FINITE} 
opt. value)}
\[
\begin{array}{rcl}
(\cP) \quad \text{(finite)  } p^*=&
          \min_x & c^Tx\\ 
           &\text{s.t.}&  Ax =b \in \Rm \\
           &&  x \in \Rnp
\end{array}
\] 
there exists $\hat x$ with $A\hat x=b, x>0$ \qquad ({\crr MFCQ})

\end{block}
\begin{block}{Dual LP}
\[
\begin{array}{rcl}
(\cD) \quad  p^*=d^*=&
          \max & b^Ty\\ 
           &\text{s.t.}&  A^Ty \leq  c \in \Rn \\
           &&  y \in \Rm
\end{array}
\] 
there exists $\hat y$ with $A^T\hat y<c$ \qquad ({\crr Slater CQ})
\end{block}


\begin{block}{Stability}
MFCQ/Slater  is equivalent to stability wrt RHS perturbations
\end{block}


\end{frame}
\begin{frame}
\frametitle{ Basic (Feasible) Solutions, \BFS }


\begin{definition}[basic (feasible) solution, \BFSp; basis $\cB$]
\begin{itemize}
\item
Given: $x\in \Rn, Ax=b$ and
$\cB \subset \{1,\ldots,n\}$,
\\$|\cB|=m$; let $\cN = \{1\ldots n\}\backslash B$. 
\\Then $x$ is a {\crr basic solution} with {\crr basis $\cB$} if 
\\\quad \fbox{ $A(:,\cB)$ is nonsingular 
 and $x_i = 0, \ \forall i \in \cN$}
\item
$x$ is a basic \underline{feasible} solution, \BFSp, if in addition $x\geq 0$.
\end{itemize}
\end{definition}

\begin{block}{Equivalently, with $Ax=b$; lin. indep. active set:}
$x$ is basic if there exists $\cN\subset\{1,\ldots,n\}, |\cN|=n-m,
x_i=0, \forall i\in \cN$; 
\\and the matrix of {\crr active} constraints
\[
\begin{bmatrix}
A \cr
I_\cN
\end{bmatrix} \quad \text{ is nonsingular}.
\]
\end{block}


\end{frame}
\begin{frame}
\frametitle{Two Kinds of Degeneracy}



\begin{definition}[Degenerate \BFSp]

\[
x \text{ \BFS is}\quad
\left\{
\begin{array}{rl}
     \text{\crb nondegenerate}, & \text{if $x_i>0 , \ \forall i \in \cB$},
 \\  \text{{\crr degenerate}}, & \text{otherwise}
\end{array}
\right.
\]
\end{definition}
\begin{definition}[variable fixed at $0$] Let $i_0\in \cI=\{1,\ldots,n\}$.
$x_{i_0}$ is \underline{fixed at $0$} if 
$x_{i_0} = 0, \forall x \in \cF$. Let
\[
\cI^= = \{ i\in \cI : x_i \text{ is fixed at } 0\},\, 
\cI^< = \cI \backslash \cI^=
\]
\end{definition}


\begin{block}{$\bar x$ a degenerate \BFS with basis $\cB$ is of type:}
\begin{enumerate}
\item 
$i \in \cB, \bar x_i=0 \implies i \in \cI^<$
\item 
\label{item:bfs2}
there exists $i\in \cB \cap \cI^=$
\end{enumerate}
Below: if type two exists, then ALL \BFS are of type 2.
\end{block}


\end{frame}
\begin{frame}
\frametitle{Facial Reduction for \LPp s without Strict Feas.}


\begin{block}{Two Steps}
$\bullet$ obtain an equivalent problem with {\crr strict feasibility};
\\$\bullet$ recover {\crb full-row rank} for the constraint matrix
(always needed)
\end{block}



\begin{definition}[Face]
A convex set $F \subseteq K\subseteq\Rn$ is called a face of the 
convex set $K$, 
denoted {\crr $F\unlhd K$}, if
\\ \qquad $
 \crb y,z \in K, x = \frac{1}{2}(y +z) \in F  \implies  y,z \in F
$
\\Given a convex set $\cC\subseteq K$, the {\crr minimal face} for $\cC$ 
is the intersection of all faces of $K$ containing the set $\cC$.
\end{definition}

\begin{block}{faces of $\Rnp$, nonnegative orthant}
for fixed indices $\hat \cI \subseteq \{1,\ldots,n\}$
\\\qquad $F=\{x\in\Rnp : {\crr x_i=0},\,\forall i\in \hat \cI\}$
\end{block}

\end{frame}
\begin{frame}
\frametitle{Facial Reduction; Basics}
\begin{theorem}[{DW: \cite[Theorem 3.1.3]{DrusWolk:16} Theorem of the
Alternative}]
For the feasible system $\cF$ of the \LPp, exactly one of the 
following statements holds:
\begin{enumerate}
\item There exists $x \in \R^n_{\crr ++}$ with $Ax = b$, i.e.,~strict
feasibility holds;
\item There exists $y\in \Rm$ such that 
\[
{\crr (*)} \quad 0\neq z := A^Ty \in  \Rm_+,  \ \text{ and } \  \<b,y\>=0,
\]
\end{enumerate}
\end{theorem}

\begin{block}{exposing vector $z\in \Rnp$}
{\crr (*)} is equivalent to:
 \\{\crr exposing vector} $0\neq z\geq 0$ exists for the 
{\crb minimal face containing the feasible set}, i.e.,
$
\begin{array}{rcl}
x\in \cF 
&\iff & 
Ax=b, x\geq 0 
\\&\implies&
\langle z,x \rangle =
\langle A^Ty,x \rangle =
\langle y,Ax \rangle =
\langle y,b \rangle  =0
\end{array}
$
\end{block}


\end{frame}
\begin{frame}
\frametitle{Facial Reduction; Outline}

\begin{block}{suppose strict feasibility fails; get {\crr exposing
vector} $z$}

\begin{enumerate}
\item
Thm of Alternative implies: $\exists 0\lneq z=A^T y\in \Rm$:
\[
\begin{array}{rcl}
x \in \cF & \implies & 0\leq \<x,z\> =\<x,A^Ty\> = \<Ax,y\> = \<b,y\> = 0
      \\ & \implies & 0 = x \circ z
\end{array}
\]
{\crb cardinality of support of $z$}: $s_z = \left| \{i : z_i > 0\}\right|$

\item
$z = \sum\limits_{j=1}^{s_z} z_{t_j} e_{t_j}$, $t_j$ nondecreasing order


$x = \sum\limits_{j=1}^{n-s_z} x_{s_j} e_{s_j}$, $s_j$ nondecreasing order. 

$
V  =\begin{bmatrix}e_{s_1} & e_{s_2} & \ldots & e_{s_{n-s_z}}
    \end{bmatrix} \in \R^{n\times (n-s_z)}$
\quad ($\cong x_{s_j} >0$)
\item
{\small $\cF = \{x \in \Rn_+ : Ax = b\} =
\{x = Vv \in \Rn :   AVv = b, v \in \R^{n-s_z}_+\}$}
\item
Recover full row rank:  $A \leftarrow P_{\bar m}AV, 
b\leftarrow P_{\bar m}b$
\end{enumerate}
\end{block}

\end{frame}
\begin{frame}
\frametitle{Facial Reduction, \FRp; Two Steps}


\begin{block}{matrix $V \in \R^{n\times (n-s_z)}$,  {\crr facial range
vector}}

Every facial reduction step yields at least one constraint is redundant,
BW: \cite{bw3},IW: \cite[Lemma 2.7]{ImWolk:21},S: \cite[Section 3.5]{Sremac:2019}.
\end{block}

\begin{lemma}[step 2: redundant constraint]
Consider the facially reduced feasible set
\[
\cF_r = \left\{v :  AVv = b, v \in \R^{n-s_z}_+\right\} .
\]
Then at least one linear constraint of the \LP is redundant.
\begin{proof}
Let: $0\neq z=A^Ty\geq 0$ exposing vector; $V$ corresponding
facial range vector; Then:
\\$\qquad 0 = V^Tz = V^T A^Ty  = (AV)^Ty =\sum_{i=1}^m y_i ((AV)^T)_i$
\\Since $0\neq y\in \Rm$, the rows of $AV$ are linearly dependent.
\end{proof}
\end{lemma}



\end{frame}
\begin{frame}
\frametitle{Summary \FRp}



\begin{block}{Result of full two step \FRp: strict feas.; full rank}
\[
\begin{array}{rcl}
\cF 
&=& \{x \in \Rn_+ : Ax = b\} 
\\&=&
\{x = Vv \in \Rn :   (P_{\bar m} AV)v = (P_{\bar m} b), \ v \in \R^{n-s_z}_+\},
\end{array}
\]
\begin{itemize}
\item
$\exists {\crr \hat v>0},  (P_{\bar m} AV)v = (P_{\bar m} b)$
\item
{\crr full rank $P_{\bar m}AV$:} $P_{\bar m} : \Rm \to \R^{\bar m}$, 
{$\bar m ={\rank(AV)}<m$}

{\crr $P_{\bar m}$} is
projection that chooses the linearly independent rows of $AV$.
\item
BOTH \# variables, \# constraints are {\crr strictly reduced}.
\end{itemize}
\end{block}

\begin{block}{}
This emphasizes the ill-conditioning of problems where strict feasibility
fails, i.e.,~{\crb Implicit singularity} is eliminated using \FRp.
\end{block}


\end{frame}
\begin{frame}
\frametitle{Singularity Degree  Sturm: \cite{S98lmi},
$sd(\cF)$: min \# FR steps}



\begin{definition}
[H\"{o}lder regularity]
pair closed, convex subsets $A, B$. is $\gamma${\em-H\"{o}lder regular} if 
$\forall U$ compact, $\exists c> 0:$\\
$\dist(x,A\cap B)\leq
c\cdot\Big(\dist^{\gamma}(x,A)+\dist^{\gamma}(x,B)\Big)\qquad \textrm{
for all }x\in U.$
%We say that $(A,B)$ {\em is} $\gamma${\em-H\"{o}lder regular, up to
%displacement,} if the displacement vector $\disp(A,B)$ exists and the
%pair $\big(A-\disp(A,B),B\big)$ is $\gamma$-H\"{o}lder regular.
\end{definition}

\begin{block}{Sturm \cite{S98lmi} error bound for SDP:} $d=sd(\cF)$
$\cF = \cL\cap \Snp$, $(\cL,\Snp)$ is $\frac 1{2^d}$-H\"older regular.
\end{block}



\begin{block}{}

%For a general conic problem, such as semidefinite programs (\SDPp), 
%the facial reduction iterations do not necessarily end in one iteration; see
%\cite{Sremac:2019,SWW:17,ScTuWonumeric:07}.
%And there is a special name for the minimum length of \FR iterations.
%Given a spectrahehedron $\cS$, the {singularity degree} of $\cS$, denoted by $\sd(\cS)$, is the smallest number of facial reduction iterations for finding $\face(\cS)$.
$\bullet$ for {\crr \LPp s}, it is known that 
\FR can be done in {\crr \emph{one} iteration},
i.e., 
\[
\sd(\cF) \le 1
\] % see~\cite[Theorem 4.4.1]{DrusWolk:16}.

$\bullet$  \FR performed on the \LPp s does not alter the 
sparsity pattern of the data matrix $A$.
(only involves discarding rows and columns of $A$)

\end{block}



\end{frame}
\begin{frame}
\frametitle{Main Theoretical Result}

\begin{theorem}
Suppose that strict feasibility of $\cF$ fails.
Then every basic feasible solution, \BFSp, $x\in  \cF$ with basis $\cB$
has $\cB\cap \cI^=\neq \emptyset$ and thus is degenerate.
\end{theorem}
%%%
%%%\subsubsection{An Algebraic Proof of~\Cref{thm:LPdegen}
%%%via the Definition of Basic Feasible Solution}
%%%
%%%
\begin{proof}
$\bullet$  
$\cF = \{x \in \Rn  \ : \ AVv = b, \ v\in \R^{n-s_z}_+ \}$,
{\crr facial range vctr $V$}

$\bullet$  wlog
%%%By permuting the columns of $A$, we may assume that the matrix $V$ is of the form 
$V = \begin{bmatrix} I_{r}  \\ 0  \end{bmatrix}  \text{ and } r = n-s_z$;

$\bullet$ recall by redundant constraint lemma:
{\crr $\rank AV<m$}

$\bullet$  implies {\crr $\rank A(:,\{1,\ldots,r\})<m$}

$\bullet$  \BFS implies $\rank A(:,\cB)=m$; implies $\exists i\in\cB, i>r$

$\bullet$  implies $\exists i\in\cB\cap \cI^=, x_i=0$  (degeneracy)
\end{proof}

\end{frame}
\begin{frame}
\frametitle{Corollary, Stability, Converse}



\begin{corollary}[motivates phase I part 2]
If there exists a nondegenerate basic feasible solution, then there exists a strictly feasible point in $\cF$.
\end{corollary}

\begin{block}{Stability from above corollary}
Recall: strict feasibility (and full rank, MFCQ) is equivalent to
stability wrt RHS perturbations.
\end{block}
\begin{example}[converse fails]

$\tiny A = \begin{bmatrix}
1 & 0 & 2 & 0 & -2 \\ 1 & -3 & 2 & 1 & -2
\end{bmatrix};
b = \begin{pmatrix}  1 \\ 1 \end{pmatrix}$,\quad
$\small 0<x=\frac{1}{10} \begin{pmatrix} 1 & 1 & 5.5 & 3 & 1\end{pmatrix}^T$


4 deg. feas. bases: $\cB = \{ \{1,2\}, \{1,4\}: x=(1,0,0,0,0)^T$
\\\qquad $\cB = \{2,3\},\{3,4\}: x=(0,0,1/2,0,0)^T$

(Also, the linear assignment problem is highly degenerate but has a
strictly feasible point (average).)
\end{example}


\end{frame}
\begin{frame}
\frametitle{ Interior Point Methods }


\begin{block}{Optimality Conditions at current $(x>0,y,s>0), \mu>0$}
$X=\Diag(x),\,S=\Diag(s)$.
\[
\begin{array}{rcll}
     A^T\Delta y +\Delta s - c &=& 0   & \text{dual feasibility}
     \\ A\Delta x -b  &=& 0   & \text{primal feasibility}
     \\ S\Delta x + X\Delta s  &=& \mu e   & \text{complementary slackness}
\end{array}
\]
\end{block}


\begin{block}{After block elimination, solve normal equations for
$\Delta y$}
\begin{itemize}
\item
Use $\Delta s$ in eqn 1 to eliminate $\Delta s$ in eqn 3.
\item
Solve for $\Delta x$ in eqn 3 and eliminate it in eqn 2.
\item We get the normal equations
\[
AS^{-1}XA^T \Delta y = RHS.
\]
\item 
Backsolve for $\Delta x,\Delta s$ to get the Newton direction.
\end{itemize}
\end{block}


\end{frame}
\begin{frame}
\frametitle{Numerical Experiments with Interior Point Methods}

%%%\section{Numerics}
%%%\label{sec:Numerics}
%%%We now provide empirical evidence that \FR indeed is a useful
%%%preprocessing tool in reducing the size of the problem, and in
%%%particular improving the condition number of the problem. We do this
%%%first for interior point methods and then for simplex methods.
%%%
%%%\subsection{Numerical Experiments with Interior Point Methods}
%%%\label{sec:NumericIntPtMethod}
%%%
%%%In this section we compare the behaviour for finding near-optimal points 
%%%with instances that have strictly feasible points and instances that do not.
%%%More specifically, given a near optimal primal-dual point $(x^*,s^*)\in
%%%\Rnpp \oplus \Rnpp$ from interior point method solvers, 
%%%we observe the condition number, i.e.,~the ratio of largest
%%%to smallest eigenvalues of the normal matrix at $(x^*,s^*)$:

\begin{block}{condition numbers of normal matrix; $x^*,s^*$ near optimal}
\begin{equation}
\kappa\left( AD^*A^T \right) , \ \text{ where } D^* = \Diag(x^*)\Diag(s^*)^{-1}
\end{equation}
\end{block}

\begin{block}{three families of instances}
\begin{enumerate}
\item $(\cP_{(A,b,c)})$ do not have strictly feasible points;
\item $(\bar{\cP}_{(A,\bar{b},c)})$ have strictly feasible points;
\item $(\cP_{(A_{FR},b_{FR},c_{FR})})$  facially reduced instances of $(\cP_{(A,b,c)})$.
\end{enumerate}
\end{block}
%%%
%%%% A Note on Performance Profiles for Benchmarking Software
%%%

\end{frame}
\begin{frame}
\frametitle{Condition Numbers of Normal Matrix Near Optimum}

\begin{figure}[h!]
\centering
%\includegraphics[height=6cm]{condnumplot.eps}
\includegraphics[height=5.5cm]{condnumplotPerformanceProfile.eps}
\caption{Performance profile on $\kappa\left(ADA^T\right)$ with(out) strict
feasibility near optimum; various solvers }
\label{fig:condnums}
\end{figure}
%%%
%%%We use the {performance profile} \cite{MR1875515,GouldNicholas2016ANoP} to observe the overall behaviour on different families of instances using the three solvers.
%%%The performance profile provides a useful graphical comparison for solver performances.
%%%\Cref{fig:condnums} displays the performance profile on the condition numbers of the normal matrix $AD^*A^T$ near optimal points from different solvers. We generate $100$ instances for each family that have $\dim(\relint(\cF))\in [300,1350]$. The instance sizes are fixed with $(m,n) = (500,1500)$.
%%%The vertical axis in~\Cref{fig:condnums} represents the statistics of the performance ratio on $\kappa\left(AD^*A^T\right)$, the condition number of normal matrix near optimum $(x^*,s^*)$; see \cref{eq:condNumnearOpt}.
%%%The solid lines in \Cref{fig:condnums} represent the performance of the instances $(\cP_{(A,b,c)})$ that fail strict feasibility.  
%%%They show that the condition numbers of the normal
%%%matrices near optima are significantly higher when strict feasibility fails.
%%%That is, when strict feasibility fails for $\cF$, the matrix $AD^*A^T$ is more ill-conditioned and it is difficult to obtain search directions of high accuracy.
%%%We also observe that facially reduced instances yield smaller condition numbers near optima. We note that the instances $(\cP_{(A,b,c)})$ and $(\cP_{(A_{FR},b_{FR},c_{FR})})$ are equivalent.
%%%
%%%%The markers $\bullet$,\text{\scriptsize$ \blacktriangle, \blacksquare $} represent instances $(\cP_{(A,b,c)})$ solved by linprog, SDPT3 and MOSEK, respectively. Similarly, the markers  $\circ$,\text{\scriptsize$ \triangle, \square $} represent the instances $(\bar{\cP}_{(A,\bar{b},c)})$ solved by linprog, SDPT3 and MOSEK, respectively. Finally, the markers $+,*,\times$ represent the instance $(\cP_{(A_{FR},b_{FR},c_{FR})})$ solved by linprog, SDPT3 and MOSEK, respectively. 
%%%

\end{frame}
\begin{frame}
\frametitle{Empirics on Stopping Criteria}
%%%
%%%
%%%We now use the three solvers to observe the accuracy of the
%%%first-order optimality
%%%conditions (KKT conditions), and the running time for the instances $(\cP_{(A,b,c)})$ and $(\cP_{(A_{FR},b_{FR},c_{FR})})$. \Cref{table:KKTtable} exhibits the numerics on these instances. 
%%%Given solver outputs $(x^*,y^*,s^*)$, the header `KKT' exhibits the
%%%average of the triple consisting of the primal feasibility, dual feasibility 
%%%and complementarity;

\begin{block}{}
test the average performance of $10$ instances of 
\\size $(n,m,r) = (3000,500,2000)$
\end{block}
%%%The headers `iter' and `time'  in \Cref{table:KKTtable} refer to
%%%the average of the number of iterations and the running time in seconds, respectively.
 

\begin{block}{
$
\text{KKT} = \left( \frac{\|Ax^*-b\|}{1+ \|b\|}, \ \frac{\|A^T y^*+s^*-c\|}{1+ \|c\|} , \ \frac{\<x^*,s^*\>}{n} \right)
$}

\tiny
\begin{table}[h!]
\centering
\begin{tabular}{|c|c|c|c|}\hline 
\multicolumn{2}{|c|}{\multirow{1}{*}{  }} & \multicolumn{1}{c|}{Non-Facially Reduced System} & \multicolumn{1}{c|}{Facially Reduced System}  \\ \cline{1-4}
\multirow{3}{*}{ linprog }
&\multirow{1}{*}{KKT} & (9.58e-16, 1.80e-12, 5.17e-09) & (5.78e-16, 1.51e-15, 5.57e-08) \\ \cline{3-4} 
&\multirow{1}{*}{iter} & 23.30 & 17.60 \\  \cline{3-4} 
&\multirow{1}{*}{time} &     1.10 &     0.76 \\ \cline{1-4} 
\multirow{3}{*}{ SDPT3 }
&\multirow{1}{*}{KKT} & (1.51e-10, 1.49e-12, 4.67e-03) & (8.54e-12, 3.75e-16, 4.19e-06) \\ \cline{3-4} 
&\multirow{1}{*}{iter} & 25.40 & 19.80 \\  \cline{3-4} 
&\multirow{1}{*}{time} &     0.82 &     0.53 \\ \cline{1-4}
\multirow{3}{*}{ MOSEK }
&\multirow{1}{*}{KKT} & (8.40e-09, 7.54e-16, -5.16e-06) & (5.16e-09, 3.81e-16, -2.03e-08) \\ \cline{3-4} 
&\multirow{1}{*}{iter} & 35.90 & 10.10 \\  \cline{3-4} 
&\multirow{1}{*}{time} &     0.58 &     0.31 \\ \cline{1-4} 
\end{tabular}
\caption{Average of KKT conditions, iterations and time of (non)-facially reduced problems}
\label{table:KKTtable}
\end{table}
\end{block}
%%%
%%%
%%%From \Cref{table:KKTtable} we observe that facially reduced instances
%%%provide significant improvement in first order optimality conditions, 
%%%the number of iterations and the running times for all solvers. 
%%%We note that the instances $(\cP_{(A,b,c)})$ and
%%%$(\cP_{(A_{FR},b_{FR},c_{FR})})$ are equivalent. Hence, our empirics
%%%show that  performing facial reduction as a preprocessing step not only improves the solver running time but also the \emph{quality} of solutions.
%%%
%%%
%%%
%%%
%%%\begin{comment}  % saving some tables I formed in case needed in the future
%%%\begin{table}[h!]
%%%\begin{tabular}{|l|l|l|l|}\hline
%%%  \multicolumn{2}{|l|}{\multirow{1}{*}{ RPOTOTYPE }} 
%%%  & \multicolumn{1}{l|}{NO} 
%%%  & \multicolumn{1}{l|}{FR}  \\ \cline{1-4}
%%%  \multirow{3}{*}{linprog} & \multirow{1}{*}{KKT} & (1e-1,1e-1,1e-1) & (1e-1,1e-1,1e-1) \\ \cline{3-4}
%%%  &\multirow{1}{*}{iter} & 1000 & 105 \\ \cline{3-4}
%%%  &\multirow{1}{*}{time} & 1034 & 102 \\ \cline{1-4}
%%%   \multirow{3}{*}{SDPT3} & \multirow{1}{*}{KKT} & 1e-1 & 1e-2 \\ \cline{3-4}
%%%  &\multirow{1}{*}{iter} & 1000 & 105 \\ \cline{3-4}
%%%  &\multirow{1}{*}{time} & 120 & 18 \\ \cline{1-4}
%%%   \multirow{3}{*}{mosek} & \multirow{1}{*}{KKT} & 1e-1 & 1e-2 \\ \cline{3-4}
%%%  &\multirow{1}{*}{iter} & 1000 & 105 \\ \cline{3-4}
%%%  &\multirow{1}{*}{time} & 102 & 34 \\ \cline{1-4}
%%%\end{tabular}
%%%\end{table}
%%%
%%%
%%%\begin{tabular}{|l|l|l|l|}\hline
%%%  \multirow{10}{*}{numeric literals} & \multirow{5}{*}{integers} & in decimal & \verb|8743| \\ \cline{3-4}
%%%  & & \multirow{2}{*}{in octal} & \verb|0o7464| \\ \cline{4-4}
%%%  & & & \verb|0O103| \\ \cline{3-4}
%%%  & & \multirow{2}{*}{in hexadecimal} & \verb|0x5A0FF| \\ \cline{4-4}
%%%  & & & \verb|0xE0F2| \\ \cline{2-4}
%%%  & \multirow{5}{*}{fractionals} & \multirow{5}{*}{in decimal} & \verb|140.58| \\ \cline{4-4}
%%%  & & & \verb|8.04e7| \\ \cline{4-4}
%%%  & & & \verb|0.347E+12| \\ \cline{4-4}
%%%  & & & \verb|5.47E-12| \\ \cline{4-4}
%%%  & & & \verb|47e22| \\ \cline{1-4}
%%%  \multicolumn{3}{|l|}{\multirow{3}{*}{char literals}} & \verb|'H'| \\ \cline{4-4}
%%%  \multicolumn{3}{|l|}{} & \verb|'\n'| \\ \cline{4-4}          %% here
%%%  \multicolumn{3}{|l|}{} & \verb|'\x65'| \\ \cline{1-4}        %% here
%%%  \multicolumn{3}{|l|}{\multirow{2}{*}{string literals}} & \verb|"bom dia"| \\ \cline{4-4}
%%%  \multicolumn{3}{|l|}{} & \verb|"ouro preto\nmg"| \\ \cline{1-4}          %% here
%%%\end{tabular}
%%%
%%%\begin{tabular}{|c|c|ccccc|}\hline
%%%\multicolumn{2}{|c|}{  } &  \multicolumn{5}{|c|}{ $(r / n) \% $ } \\   \cline{3-7}
%%%\multicolumn{2}{|c|}{  } & 20\% & 40\% & 60\% & 80\% & 100\%  \\ \hline
%%%  \multirow{4}{*}{ $(n,m)$ } 
%%% & \multirow{1}{*} (100,20) & & & & &  \\
%%% & \multirow{1}{*} (1000,200) & & & & &  \\
%%% & \multirow{1}{*} (5000,1000) & & & & &  \\
%%% & \multirow{1}{*} (10000,2000) & & & & &  \\
%%%\hline
%%%\end{tabular}
%%%
%%%
%%%\begin{table}[h!]
%%%\begin{tabular}{|c|c|c|c|c|c|}\hline
%%%  \multicolumn{3}{|c|}{\multirow{1}{*}{ Primal Simplex }} 
%%%   & \multicolumn{3}{c|}{Dual Simplex}  \\ \cline{1-6}
%%%  \multicolumn{1}{|c|}
%%%   {\multirow{1}{*}{ $(m,n)$ }} 
%%%   & {\multirow{1}{*}{ $r$ }}
%%%   & {\multirow{1}{*}{ degiter (\%) }} 
%%%   & {\multirow{1}{*}{ $(m,n)$ }} 
%%%   & {\multirow{1}{*}{ $r$ }}
%%%   & {\multirow{1}{*}{ degiter (\%) }} 
%%%    \\ \cline{1-6}
%%%  \multirow{4}{*}{ (500,1000) } 
%%%  & \multirow{1}{*}  100  & 10 
%%%  &  \multirow{4}{*}{ (500,1000) }  
%%%  & 100 & 11 \\  \cline{2-3} \cline{5-6}
%%%  & \multirow{1}{*}  500  & 10 & & 500 & 11   \\ \cline{2-3} \cline{5-6}
%%%  & \multirow{1}{*} 900  & 10 & & 900 & 11 \\ \cline{2-3} \cline{5-6}
%%%  & \multirow{1}{*} 1000  & 10 & & 1000 & 11 \\ \cline{1-6}
%%%  \multirow{4}{*}{ (5000,1000) } 
%%%  & \multirow{1}{*}  1000  & 10 
%%%  &  \multirow{4}{*}{ (5000,1000) }  
%%%  & 1000 & 11 \\  \cline{2-3} \cline{5-6}
%%%  & \multirow{1}{*}  3000  & 10 & & 3000 & 11   \\ \cline{2-3} \cline{5-6}
%%%  & \multirow{1}{*}  4000  & 10 & & 4000 & 11 \\ \cline{2-3} \cline{5-6}
%%%  & \multirow{1}{*}  5000  & 10 & & 5000 & 11 \\ \cline{1-6}
%%%\end{tabular}
%%%\end{table}\\
%%%
%%%
%%%\end{comment}
%%%
%%%
%%%\subsubsection{Empirics on Distance to Infeasibility}
%%%\label{sec:numericsDistInfes}
%%%
%%%In this section we present a numerical experiment that illustrates the affect of the perturbation imposed on the right-hand-side vector of the system $\cF$ when strict feasibility fails.
%%%We recall, from \Cref{prop:distInfrhsPert}, that there exists an arbitrarily small perturbation of the right-hand-side vector $b$ of $\cF$ that renders the set $\cF$ infeasible, i.e., $\dist(b,\cF=\emptyset)=0$.  
%%%Moreover, the vector $\Delta b = y$ that satisfies the auxiliary system \eqref{eq:auxsystem} is a perturbation that makes the set $\cF$ empty; see \eqref{eq:FarkasInfea}.
%%%
%%%
%%%We follow the steps in \Cref{sec:GenerationPrimal} to generate instances of the order $(n,m)=(1000,200)$ and $r = \relint(\cF) = 900$.
%%%The objective function $c^Tx$ is chosen as presented in \Cref{sec:GenerationPrimal}.
%%%For the fixed $(n,m,r)$, we generate $10$ instances and observe the 
%%%average performance of these instances as we gradually increase the magnitude of the perturbation. 
%%%We recall the matrix $AV$ from \eqref{eq:setEqauivalence}.
%%%We use two types of perturbations for $b$;
%%%\[
%%%\Delta b, \text{ where } \Delta b \in \range(AV)^\perp, \quad
%%%\Delta \bar{b}, \text{ where } \Delta \bar{b}\in \range (AV).
%%%\]
%%%We choose $\Delta b$ to be the vector $y$ that satisfies $\eqref{eq:auxsystem}$.
%%%For $\Delta \bar{b}$, we choose $AV d$, where $d\in \R^r$ is a randomly chosen vector.
%%%As we increase $\epsilon>0$, we observe the performance of the two families of the systems
%%%\[
%%%\begin{array}{lll}
%%%Ax = b_\epsilon := b - \epsilon \Delta b \ \text{ and } \ Ax = \bar{b}_\epsilon := b - \epsilon \Delta \bar{b} .
%%%\end{array}
%%%\]
%%%We use the interior point method from MATLAB's linprog for the test. 
%%%\Cref{fig:firstoptcond} contains the average of the first-order optimality conditions evaluated at the solver outputs $(x^*,y^*,s^*)$ of these instances; primal feasibility, dual feasibility and the complementarity.
%%%
%%%\begin{figure}[ht!]
%%%\centering
%%%\includegraphics[height=6cm]{firstoptBpert.eps}
%%%\caption{Changes in the first-order optimality condition as the perturbation of $b$ increases}
%%%\label{fig:firstoptcond}
%%%\end{figure}
%%%The horizontal axis of \Cref{fig:firstoptcond} indicates the degree of the perturbation imposed on the right-hand-side vector $b$, $\epsilon \| \Delta b\|$ and $\epsilon \|\Delta \bar{b}\|$.
%%%The vertical axis indicates the individual component of the first-order optimality. 
%%%From \Cref{fig:firstoptcond}, we observe that the KKT conditions with the perturbation $\Delta \bar{b}$ display a steady performance regardless of the perturbation degree;
%%%see the markers  $\circ$,\text{\scriptsize$ \square, \triangle $} with the dotted lines.
%%%In contrast, the markers $\bullet$,\text{\scriptsize$ \blacksquare, \blacktriangle $} in \Cref{fig:firstoptcond} exhibit the performance of the instances that are perturbed with $\Delta b$ and they display a different performance.
%%%In particular, we see that the relative primal feasibility $\|Ax^*-b_\epsilon \|/(1+\|b_\epsilon \|)$, marked with $\bullet$, consistently increases as the perturbation magnitude $\epsilon \|\Delta b\|$ increases when strict feasibility fails for $\cF$.
%%%
%%%
%%%
%%%

\end{frame}
\begin{frame}
\frametitle{Numerical Experiments with (Dual) Simplex Method}
%%%
%%%
%%%In this section we compare the behaviour of the dual simplex method with 
%%%instances that have strictly feasible points and instances that do not.
%%%
%%%\subsubsection{Generating Dual \LPp s without Strict Feasibility}
%%%\label{sec:GenerationDual}
%%%
%%%We first show how to generate an instance for the dual feasible set
%%%$\cG$ that fails strict feasibility.
%%%The construction is similar to the one in \Cref{sec:GenerationPrimal}.
%%%We generate a degenerate problem by finding a feasible auxiliary system~\cref{eq:auxsystem:Dual}.
%%%Given $m,n,r\in \N$, we construct $A\in \Rmn$ and $c\in \Rn$ that satisfy \cref{eq:auxsystem:Dual}  with $\dim(\relint (\cG) ) = m+r$.
%%%\begin{enumerate}
%%%\item 
%%%Pick any $0 \ne w \in \Rnp$ with $|\supp(w)| = n-r$.
%%%Let 
%%%\[ 
%%%\{w\}^\perp = \spann \{a_i\}_{i=1}^{n-1} \quad \left( = \nul (w^T) \right) . 
%%%\]
%%%We let the rows of the matrix $A \in \Rmn$ consist of a random linear combination of the row vectors in the set $ \{a_i^T\}_{i=1}^{n-1}$.
%%%We note that $Aw=0$.
%%%\item Pick $s\in \Rnp$ so that 
%%%\[
%%%s_i  =
%%%\left\{
%%%\begin{array}{ll}
%%%0 & \text{if } i\in \supp(w) \\
%%%\text{positive } & \text{if } i \notin \supp(w).
%%%\end{array} 
%%%\right.
%%%\]
%%%We note that $\<w,s\> =0$ holds.
%%%\item Pick $y \in \Rm$ and set $c = A^T y +s$. We note that $\<c,w\> =0$ holds.
%%%\end{enumerate}
%%%For the empirics, we construct the objective function $b^Ty$ of $(\cD)$ by choosing a vector $\hat{x}\in \Rnpp$ and setting $b = A\hat{x}$. 
%%%

\begin{block}{Empirics on the Number of Degenerate Iterations}
$\bullet$
MOSEK (values in the table) reports percentage of degenerate iterations i.e,,
{\crr `DEGITER($\%$)' is ratio of degenerate iterations}. (smaller value is
better).

$\bullet$
$r = |\supp(s)|$;
smaller value $(r/n)\%$
means entries of $s$ are identically $0$; $100\%$ means 
strict feasibility holds. 

$\bullet$ note {\crr significant decrease in  `DEGITER($\%$)'}.
\end{block}
%%%
%%%Given a set $\cG$ and a point $(y,s)\in \relint(\cG)\subseteq \Rm \oplus \Rn_+$, let $r$ be the number of positive entries of $s$, i.e., $r = |\supp(s)|$. 
%%%In our tests, we gradually increase $r$ for fixed $n,m$ and generate instances for $\cG$ as described in \Cref{sec:GenerationDual}. We then observe the behaviour of the dual simplex method. 
%%%\Cref{table:dualsimplex} contains the results.
%%%In \Cref{table:dualsimplex}, a smaller value for the header $(r/n)\%$
%%%means that there are more entries of $s$ that are identically $0$ in the set $\cG$; and the value $100\%$ means that strict feasibility holds. 
%%%For each triple $(n,m,r)$, we generated $10$ instances and we report the average 
%%%of `DEGITER($\%$)' of these instances.
%%%
%%%
%%%


\begin{block}{}

\begin{table}[h!]
\centering
\begin{tabular}{|c|c|ccccc|}\hline 
\multicolumn{2}{|c|}{  } & 
\multicolumn{5}{|c|}{ $(r / n) \% $ } \\
\cline{3-7}
\multicolumn{2}{|c|}{  } &
60 & 70 & 80 & 90 & 100 
\\ \hline
\multirow{ 4 }{*}{ $(n,m)$ }
& \multirow{1}{*} (1000, 250) &36.62& 10.18& 0.01& 0.02& 0.00\\ 
& \multirow{1}{*} (2000, 500) &39.72& 18.28& 0.07& 0.15& 0.01\\ 
& \multirow{1}{*} (3000, 750) &25.99& 10.66& 0.32& 0.75& 0.02\\ 
& \multirow{1}{*} (4000, 1000) &29.78& 18.25& 0.25& 0.53& 0.02\\ 
\hline\end{tabular}
\caption{Average of the ratio of degenerate iterations}
\label{table:dualsimplex}
\end{table}
\end{block}




\end{frame}
\begin{frame}
\frametitle{Phase I(b): Towards Strict Feasibility}

\begin{itemize}
\item
$\bar x,\cB$ degenerate \BFSp/basis;
Wlog basic variables located first $\bar{x}$ as are degenerate variables.
Solve (using basis from phase I simplex method)
\[
p^*_1 = \max \{x_1 \,:\, Ax=b, \, x\geq 0\}.
\]
\begin{enumerate}
\item Suppose that $p_1^*>0$.
Then, the the variable $x_1$ is not an identically $0$ variable, i.e., $1\notin \cI_0$.
\item Suppose that $p_1^*=0$. 
Then, the variable $x_1$ is an identically $0$ variable, i.e., $1\in \cI_0$.
Let $\cB^*$ be an optimal basis. Then we have an exposing vector
\[
y^* = A(:,\cB^*)^T e_1, \  \<b,y^*\>=0 \ \text{ and }
A^Ty^*  \ge e_1 .
\]
\end{enumerate}
\item
Add up certificates: $y^\circ = \sum_j y^j$ to get exposing vector
\[
A^T y^\circ = \sum_j A^T y^j \ge 0, 
A^Ty^\circ \ne 0, 
\<b,y^\circ\> = \sum_j \<b,y^j\> = 0.
\]

\end{itemize}



\end{frame}
\begin{frame}
\frametitle{Conclusion}

\begin{itemize}
\item
The loss of strict feasibility arises in many applications in
convex optimization, e.g.,recent survey Drusvyatskiy-W.\cite{DrusWolk:16}.
\item
Strict feasibility is not needed theoretically in linear programming,
however, we have shown that loss of strict feasibility results in
stability/numerical issues.  \LPp.
In fact, loss of strict feasibility implies that \underline{every} BFS
is degenerate.
\item
In the paper, we have introduced a new concept of singularity degree related to
stability of problems. It uses the  notion of Implicit
Singularity Degree and the \underline{max}imum number of \FR steps.
\item
We have presented an algorithm, phase I (b), that regularizes an \LPp,
i.e.,~results in strict feasibility holding.
\end{itemize}
\end{frame}











%%
%----------------------------------------------------------
\begin{frame}[allowframebreaks]
	\frametitle{References}
%\tiny
\bibliographystyle{plain}
\bibliography{.master,.edm,.psd,.bjorBOOK,.qap,.haesol}
\end{frame}



\begin{frame}
\frametitle{
Thanks for your attention!}
%\hypertarget{targetname}{text} to create target.
%Some useful buttons are \beamerbutton, \beamergotobutton,
%and \beamerreturnbutton.
%To go to the last slide, click here .
\titlepage
\end{frame}


\end{document}