\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}
\usepackage{subfigure}
\usepackage{hyperref}


\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}}
\newcommand{\notimplies}{%
  \mathrel{{\ooalign{\hidewidth$\not\phantom{=}$\hidewidth\cr$\implies$}}}}

\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{\cU}{{\mathcal U}}

\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{\LM}{{\bf{\rm LM\,}}}
\newcommand{\LMp}{{\bf{\rm LM}}}
\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{\cPN}{{\cP_\cN}}

\DeclareMathOperator{\sd}{\textbf{sd}}  % singularity degree
\DeclareMathOperator{\maxsd}{\textbf{\text{maxsd}}}  % singularity degree
\DeclareMathOperator{\ips}{\textbf{ips}}  % singularity degree





%\newcommand{\trace}{{\rm trace\,}}
\DeclareMathOperator{\bdry}{bdry}
\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 
%(Pg \pageref{pg:strfeasDeg})
\\Part (ii): Best Approximation and 
\\ ~~ \quad \qquad Exterior Point Path Following 
%Algorithm~(Pg \pageref{pg:regulNewton})
\end{flushleft}
}
\author[Wolkowicz]
{
{
\begin{figure}[htb]
\includegraphics[width=0.8\textwidth]{deptlogo.jpg}
%\centerline{\epsfbox{ttl-western-logo-trans.eps}}
%\centerline{\epsfbox{ttl-western-logo-trans.pdf}}
%\vspace{-.12in}
\end{figure}
\vspace{-.55in}
}
}
\vspace{-4in}
%\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 11:15AM, April 10, 2023, in  M103
\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}
%----------------------------------------------------------

%\section{LP Part (i): Strict Feasibility and Degeneracy}

\title{
\color{blue} 
LP Part (i): Strict Feasibility and Degeneracy 
\label{pg:strfeasDeg}
}
\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 11:15AM, April 10, 2023, in  M103
\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 (no variable fixed at zero; one type of
degeneracy) is often less emphasized. 
\end{itemize}


\end{block}
\begin{block}{History Degeneracy}
\begin{itemize}
\item
  techniques for resolving degeneracy:
\\$\bullet$ (symbolic) perturbation Charnes~'52~\cite{MR0056264};
\\$\bullet$ lexicographic Dantzig-Orden-Wolfe~'55~\cite{MR0069584}; 
\\$\bullet$ modified lexicographic Wolfe~'63~\cite{w} 
(more efficient Ryan-Osborne~'88~\cite{ro}); 
\\ $\bullet$ Bland finite pivoting rule~77~\cite{MR459599} (simple/less efficient)

\item
Megiddo~'86~\cite{MR850380}: ``exiting degenerate vertex as hard as solving
general LP''
\end{itemize}


\end{block}


\end{frame}
\begin{frame}
\frametitle{ {Motivation cont...} }


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

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

\item 
 and {\crr $\implies$ all} basic feasible solutions, BFS, are degenerate
\end{enumerate}
\end{block}
\begin{block}{We introduce:}
\begin{enumerate}
\item
the notion of \alert{implicit singularity} when strict feasibility
fails;
\item
an extension of Phase-I of simplex method for {\crr
the two part preprocessing} for {\crr strict feasibility}


\end{enumerate}
\end{block}


\end{frame}
\begin{frame}
\frametitle{Background and Notation}



\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}
\] 
assume wlog $\rank(A) = m$;  
\[
\text{with feasible set:    }\quad 
\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{History: Kantorovich; Dantzig, Karmarkar}

\begin{block}{Kantorovich '39, USSR, WWII}
$\bullet$ transportation models and optimal solutions (algorithm)
\\$\bullet$ helped NKVD with transportation problems
\end{block}


\begin{block}{Dantzig '47, USA, SIMPLEX METHOD}
$\bullet$  following duality/game-theory by Von Neumann
\\$\bullet$ Hotelling: ``but the world is nonlinear''
\\$\bullet$ Von Neumann: ``if you have a linear model, you can now solve it''
\\$\bullet$ SIAM survey 1970's:  70\% of ALL world computer time is
spent on the simplex method
\end{block}


\begin{block}{Karmarkar '84, Interior Point Revolution}
$\bullet$ Lustig-Marsten-Shanno OB1 code '90;  
large went 
\\ \qquad from: $\big(m=1e3 \times n=1e4\big)$ to $\big(m=1e5 \times
n=1e7\big)$ 
\\$\bullet$ to modern day: $\big( m=1e6 \times n=1e10\big)$ 

\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 & c^Tx\\ 
           &\text{s.t.}&  Ax =b \in \Rm \\
           &&  x \in \Rnp
\end{array}
\] 
there exists $\hat x$ with $A\hat x=b, \hat x>0$ \qquad (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 (Slater CQ)
\end{block}

%%\begin{verbatim}
%%while ($True) {
%% #Run evince with a file
%% start-sleep -seconds 300
%% (get-process -Name evince).Kill()
%%}
%%
%%save with .ps1   extension     .\Run-Evince.ps1 "filename.pdf"
%%\end{verbatim}




\begin{block}{Stability: MFCQ/Slater $\crr \iff $ }
stability wrt RHS perturbations
\\$\, \crr \iff \,$
compact set of dual variables
\end{block}


\end{frame}
\begin{frame}
\frametitle{ Basic (Feasible/Degenerate) Solutions }


\begin{definition}[basic (feasible) solution]
\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 {\crb basic solution} if 
\\\quad \fbox{\crr $A(:,\cB)$ is nonsingular 
 and $x_i = 0, \ \forall i \in \cN$}
\item
$x$ is a basic \underline{\crr feasible} solution, {\crr BFS}, 
if in addition $\crr x\geq 0$. It is {\crr \underline{degenerate}}, if $\exists i\in\cB,
x_i=0$
\end{itemize}
\end{definition}

\begin{block}{Equivalently, if $Ax=b, x\geq 0$ (feasible):}
$x$ is {\crr basic} if there exists $\cN\subset\{1,\ldots,n\}, |\cN|=n-m,
x_i=0, \forall i\in \cN$; 
\\and the corresponding matrix of {\crr active constraints}
\[
\begin{bmatrix}
A \cr
I_\cN
\end{bmatrix} \quad \text{ is nonsingular}.
\]
It is {\crr \underline{degenerate}} if there are redundant active constraints.
\end{block}


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



\begin{definition}[Degenerate BFS]

\[
x \text{ BFS is}\quad
\left\{
\begin{array}{rl}
     \text{\crb nondegenerate}, & \text{if $x_i>0 , \ \forall i \in \cB$},
 \\  \text{{\crr \underline{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 \underline{degenerate} BFS with basis $\cB$ is of type:}
\begin{enumerate}
\item 
if: $i \in \cB, \bar x_i=0 \implies i \in \cI^<$
\item 
\label{item:bfs2}
if: there exists $i\in \cB \cap \cI^=$
\end{enumerate}

~\\
Below we see that: 
\\if $\cI^=\neq \emptyset$, then {\crr ALL BFS are of Type 
\ref{item:bfs2}}.
\end{block}


\end{frame}
\begin{frame}
\frametitle{{\crr Facial Reduction, \FRp}, for \LPp s that fail Strict
Feasibility}


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



\begin{definition}[Face of a convex set $K$]
A convex set $F \subseteq K\subseteq\Rn$ is a face of $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.
$
\\ The {\crr minimal face} for $F, \face(F)$, 
is the intersection of all faces of $K$ containing $C$.
\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 {\crr z} := A^Ty \in  \Rm_+,  \ \text{ and } \  \<b,y\>=0,
\]
\end{enumerate}
\end{theorem}

\begin{block}{exposing vector ${\crr z}\in \Rnp$}
{\crr (*)} is equivalent to:
 \\{\crr exposing vector} $0\neq {\crr 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 {\crr 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 two steps; Outline}

\begin{block}{suppose strict feasibility fails; i.e.,~get {\crr exposing
vector $z$}}

\begin{enumerate}
\item
Thm of Alternative implies: $\exists 0\lneq {\crr z}=A^T y\in \Rm$:
\[
\begin{array}{rcl}
x \in \cF & \implies & 0\leq \<x,{\crr z}\> =\<x,A^Ty\> = \<Ax,y\> = \<b,y\> = 0
      \\ & \implies & 0 = x \circ {\crr z}
      \\ & \iff & 0 = x_j  {\crr z_j} = 0, \forall j 
          \\&&   \qquad \text{yields complementary unit vectors $e_k$}
\end{array}
\]
{\crb cardinality of support of ${\crr z}$}: $s_{\crr z} = \left| \{i :
{\crr z}_i > 0\}\right|$

\item
${\crr z} = \sum\limits_{j=1}^{s_{\crr z}} {\crr z}_{t_j} e_{t_j}$, $t_j$ nondecreasing order


$x = \sum\limits_{j=1}^{n-s_{\crr 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_{\crr z}}}
    \end{bmatrix} \in \R^{n\times (n-s_{\crr z})}$,
\quad ${\crr Vz = 0}$.
\item
{\small $\cF = \{x \in \Rn_+ : Ax = b\} =
\{x = Vv \in \Rn :   AVv = b, v \in \R^{n-s_{\crr 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 redundant constraint,
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 {\crr redundant}.
\begin{proof}
Let: $0\neq {\crr 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 :   \bar Av:=(P_{\bar m} AV)v = (P_{\bar m} b)=:\bar b, 
       \\&&  \qquad  v \in \R^{n-s_z}_+\}
\end{array}
$
\begin{itemize}
\item
{\crr after substit: }  $\min (V^Tc)^Tv$ s.t. $\bar A v = \bar v, \, v
\in \R^{n-s_z}_+$
\item
$\exists {\crr \hat v>0},  \bar A \hat v = \bar b$
\qquad (MFCQ)
\item
{\crr full rank $\bar A=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 {\crr ILL-CONDITIONING} of problems where strict feasibility
fails, i.e.,~{\crb Implicit singularity} is eliminated using \FRp.
\end{block}


\end{frame}









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





\begin{frame}{Two-Step Facial Reduction; $Ax=b,\,x\geq 0$}

\visible<1-4>{ 
\begin{block}{Facial Reduction, \FR}
a journey to reformulate a problem until strict feasibility is met
\end{block}
}
\begin{columns}
            \column{0.5\textwidth}

\visible<3-4>{
[STEP 1]
}

\visible<2-4>{
Solve the auxiliary system:
\vspace{-0.1cm}
\[ 
\begin{array}{l}
\text{Find } y \in \Rm  \text{ s.t. } 
A^T y  \in \hspace{-0.05cm} \Rnp  \setminus  \{ 0 \} , \\
\hspace{2.7cm} \<b,y\>  = 0  
\end{array}
\vspace{-0.2cm}
\]
Set $V = I(:,\text{supp}(A^Ty )^c)$

$x \leftarrow  Vv$

$\cF \leftarrow \{ v \ge 0 :  (AV) v = b  \}$ 
}
\visible<3-4>{
\vspace{0.2cm}
\column{0.5\textwidth}
[STEP 2]
\textcolor{red}{
\vspace{-0.27cm}
\[
\begin{array}{l}
\text{Any nontrivial \FR} 
\\ \qquad \qquad \Downarrow  \\  
\text{discovery of \underline{redundant equalities}}
\end{array}           
\]
}
\vspace{-0.1cm}
Use $P_{\bar{m}}$ to discard redundancies

\vspace{0.53cm}

$\cF \leftarrow \{ v \ge 0 : P_{\bar{m}} AV (v) = P_{\bar{m}} b  \}$ 
}
\end{columns}
        
\visible<4>{
\begin{figure}
\centering
%\hspace{-0.9cm}  % left bottom right top
\includegraphics[height=1.8cm,trim={2.8cm 0.9cm 2.2cm 0.8cm},clip]{Images/FRpicLP.eps}
\end{figure}
}
\end{frame}


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

\begin{frame}

\begin{small}
\begin{example}
Consider $\cF$ with the data
\[
A = \begin{bmatrix}
1 & 1 & 3 & 5 & 2 \\ 0 & 1 & 2 & -2 & 2
\end{bmatrix} \text{ and  }
b = \begin{pmatrix}  1 \\ 1 \end{pmatrix} .
\vspace{-0.2cm}
\]
\vspace{-0.2cm}
Set 
$y = \begin{pmatrix} 1 \\ -1 \end{pmatrix} \implies $ 
$
A^T y = \begin{pmatrix} 1 & 0 & 1 & 7 & 0  \end{pmatrix}^T \ge 0  \ \text{ and } \ 
\<b,y\> = 0.
$
\[
\tiny
V = \begin{bmatrix}
0 & 0 \\
1 & 0 \\
0 & 0 \\
0 & 0 \\
0 & 1 \\
\end{bmatrix},  \quad
x \leftarrow Vv 
= \begin{pmatrix} 0 \\ v_1 \\ 0 \\ 0 \\ v_2 \end{pmatrix} ,
\quad
Ax=b \leftarrow  AV v = b  \equiv 
\begin{bmatrix}
1 & 2 \\
1 & 2 
\end{bmatrix} v 
= \begin{pmatrix} 1\\1 \end{pmatrix}
\]
\end{example}

\pause

(*) Side note

There are exactly six feasible bases in $\cF$; (BFS all degenerate).
\begin{itemize}
\item
$\cB \in \{\{1,2\},\{2,3\},\{2,4\}\}$ is
$ x = \begin{pmatrix} 0 & 1 & 0 & 0 & 0  \end{pmatrix}^T$;  
\item
$\cB \in \left\{
\{1,5\},\{3,5\},\{4,5\}\right\}$ is
$ x = \begin{pmatrix} 0 & 0 & 0 & 0 & \frac{1}{2}  \end{pmatrix}^T$.
\end{itemize}

\end{small}

\end{frame}

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


\begin{frame}{Detect Redundancy}

\begin{small}
Recall:
\begin{lemma}[$AV$ is rank deficient]
\label{lemma:ConstrRedundant}
Consider the facially reduced feasible set
\[
\cF_r = \left\{v :  AVv = b, v \in \R^{n-s_z}_+\right\} .
\]
Then at least one linear equality of $ AVv = b$ is redundant.
\end{lemma}

\pause


\begin{scriptsize}
(proof) Let $z=A^Ty$ be the exposing vector, $V$ be a facial range vector induced by $z$. Then
\[
0 = V^Tz = V^T A^Ty  = (AV)^Ty .
\]
Found a nontrival row combination of $AV$, i.e., detected redundancy
\end{scriptsize}

\pause

\begin{definition}[implicit problem singularity]
The \alert{implicit problem singularity ($\ips$)} = The number of implicit redundant equalities of $\cF$
\end{definition}

\end{small}

\end{frame}







\begin{frame}
\frametitle{Singularity Degree $sd(\cF)$,  Sturm '20 \cite{S98lmi}}



\begin{definition}[${\crr d}=sd(\cF) = \min |FR~steps|$]
\end{definition}
\begin{definition}
[H\"{o}lder regularity]
the pair of closed, convex subsets $A, B$ is $\gamma${\em-H\"{o}lder regular} 
if
\ $\forall U$ compact, $\exists c> 0$ with:\\
$\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 Theorem for \SDPp,
$\cF = \cL\cap \Snp$
} 
$(\cL,\Snp)$ is $\frac 1{2^{\crr d}}$-H\"older regular.
\qquad ($\cL$ linear manifold)
\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}, 
\FR in {\crr \emph{one} iteration} using {\crr maximal exposing vector}, i.e., 
\qquad ${\crr d}= \sd(\cF) \le 1$
%\] % see~\cite[Theorem 4.4.1]{DrusWolk:16}.

$\bullet$  \FR for \LPp s does not alter
sparsity pattern of $A$.
(only involves discarding columns of $A$; rows of $A,b$)

\end{block}



\end{frame}
\begin{frame}
\frametitle{A Theoretical Result on degenerate BFS $\leftrightarrow$
MFCQ
}

\begin{theorem}
\footnote{Contrapositive found in 
Bertsimas-Tsitsiklis book~\cite[Exer. 2.19]{BT97}.}
Suppose that strict feasibility of $\cF$ fails.
Then every basic feasible solution, BFS, $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}[contrapositive 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; all BFS degenerate $\notimplies$ MFCQ
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{Empirics for \FR Preprocessing} 

\begin{block}{We want to {\crr avoid implicit singularity}}
$\bullet$  improve conditioning, number of iterations
\end{block}


\begin{block}{interior point methods}
$\bullet$ Condition number of {\crr normal equation system}
\\$\bullet$  stopping criteria
\[
\text{KKT} = \left( \frac{\|Ax^*-b\|}{1+ \|b\|}, \ \frac{\|A^T y^*+s^*-c\|}{1+ \|c\|} , \ \frac{\<x^*,s^*\>}{n} \right) .
\]

\end{block}
\begin{block}{simplex methods (NETLIB data set)}
$\bullet$ percentage of {\crr degenerate iterations}
\end{block}


\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=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)|$;
{\crr 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 ratio of degenerate iterations {\crr DEGITER($\%$)}}
\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 BFS/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
loss of strict feasibility has {\crr many applications}
recent survey Drusvyatskiy-W.\cite{DrusWolk:16}.
\item
though not needed theoretically in \LPp,
loss of MFCQ results in stability/numerical issues.
\item
In the paper we introduced new concept:
{\crr Implicit Singularity Degree}, \underline{max}imum number of \FR steps,
\\and
presented an algorithm, phase I (b), that regularizes an \LPp,
for strict feasibility holding.
\end{itemize}
\end{frame}


\title{
\color{blue} 
	Regularized Nonsmooth Newton Algorithms\\
	for Best Approximation\\ 
	with Applications to Large Scale LP
%\label{pg:regulNewton}
}
\author[Wolkowicz]
{
\begin{figure}[htb]
\includegraphics[width=0.8\textwidth]{deptlogo.jpg}
%\centerline{\epsfbox{ttl-western-logo-trans.eps}}
%\centerline{\epsfbox{ttl-western-logo-trans.pdf}}
%\vspace{-.12in}
\end{figure}
\vspace{-.35in}
}
\vspace{-3in}

\date{
\small{
\tiny Monday 11:15AM, April 10, 2023, in  M103
\vspace{.09in}


\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:  
Yair Censor (Univ. of Haifa);\\
~\hspace{1.5in}~ Walaa Moursi and Tyler Weames (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}{Main Problem/Best Approximation}
Given $v\in \Rn$ and $P\subset \Rn$ a polyhedral set,
\\find the {\crr nearest point to $v$ from the set $P$}

\end{block}


\begin{block}{Nonsmooth Algorithms}
$\bullet$
Application of {\crr Moreau Decomposition/elegant equation}
\\$\bullet$
present regularized nonsmooth method; singular Jacobian
\\$\bullet$
compare computational
performance to classical projection methods 
(e.g.,~\ref{tag:HLWB} projection method)
\end{block}

\begin{block}{Applications}
{\crr solving large scale linear programs}; triangles from branch and
bound methods; generalized constrained linear least squares.
\end{block}




\end{frame}
\begin{frame}
\frametitle{Notation}


	\begin{block}{best approximation problem to polyhedral set
$P\subset \Rn$}
 find the nearest point $x^* \in P$ to a given point $v\in \Rn$

~~\\
uniquely attained optimum (projection of $v$ onto $P$)
\[
\text{optimum:  } x^*(v) = \argmin\limits_{x\in P} \frac 12\|x-v \|^2
\]

optimal value:  $p^*(v) = \frac 12 \|x^*(v)-v\|^2$
\end{block}

\begin{block}{Nonsmooth Newton Method}
We apply a 
\\{\crr (regularized/scaled) nonsmooth Newton method} 
to a special form of the optimality conditions based on a 
\\{\crr Moreau decomposition}.
\end{block}



\end{frame}
\begin{frame}
\frametitle{Background}
\begin{itemize}
\item
The special Moreau decomposition for the optimality
conditions comes from work
in infinite dimensional Hilbert space 
e.g.,~\cite{MR1027508,MR1186970,MiSmSwWa:85,BoWo:86},
where the projection is actually differentiable, and typically $P$ is the
intersection of a cone and a linear manifold of finite co-dimension
(finite \# constraints). 
\item
parametrized quadratic problem to solve finite dimensional
linear programs \cite{smw2} applied in our work here below. 
(In this finite dimensional case differentiability was lost.)
\item
infinite dimensional applications appear
in the theory of 
\emph{partially finite programs} in~\cite{BoLe1:92,BoLe2:92}
 Further references in~\cite{MR0270044,MR1922763,MR1346302}. 
\end{itemize}


\end{frame}
\begin{frame}
\frametitle{ {Semismoothness} }


\begin{itemize}
\item
differentiability is lost in finite dimensional;
 this led to application of 
semismoothness~\cite{Mif:77b,QiSun:93nonsmooth,QiSun:06}. 
\item
More recently: applications 
for nearest Euclidean distance matrices and nearest doubly stochastic
in~\cite{homwolkA:04,HuImLiWo:21}.

\item
The optimum $x^*(v)$ is often called the \emph{projection onto the
polyhedral set} and is known to be unique. Differentiability properties
are nontrivial as discussed in e.g.,~\cite{MR1539982}. 
A characterization of differentiability in terms of normal
cones is given in~\cite{facchinei2003finite}. Further results and
connections to semismoothness is in e.g.,~\cite{MR1539982,MR2249554}.
A survey presentation is at \cite{Sarabi:22}.

\end{itemize}




\end{frame}
\begin{frame}
\frametitle{ {Basic Theory} }



\begin{block}{Projection onto a Polyhedral Set}

\[
    \text{(P)} \qquad  
	  \begin{array}{rcl}
	    x^*(v) := & \argmin_{x}  &\frac12 \norm{x-v}^2 \\ 
	    &  \text{s.t. } &Ax = b\in \Rm  \\
	    &         &x \in \Rnp, \\
         ~~\\
 \text{optimal value:   }    p^*(v) &= & \frac12 \norm{x^*(v)-v}^2,
    \end{array}
\]
Assumptions: $A$ full row rank; feasible set nonempty
\end{block}



\end{frame}
\begin{frame}
\frametitle{ {Optimality Conditions} }


\begin{theorem}[$F:\Rm\to \Rm$; find root $\crr y^*$; Newton]
The optimum $x^*(v)$ exists and is unique. Let
$
\crr
(*)\quad \fbox{$F(y) := A{\crr (v+A^Ty)_+} -b$}, 
\quad f(y) := \frac 12\|F(y)\|^2
$
\\Then $F(y)=0$ has a root $\crr y^*$, $F(y^*)=0 \iff y \in \argmin
f(y^*)$
\[
{\crr x^*(v) =  (v+A^Ty^*)_+}, \text{ for any root }  {\crr F(y^*) = 0}.
\]
Moreover, strong duality holds and the dual problem is
\[
\begin{array}{rcl}
p^*(v)
&=&
d^*(v) 
\\&:=&
 \max_{z \geq 0, y} \phi(y,z) \quad \left(=\min_x L(x,y,z) \right) 
\\&:=  &
    -\frac12 \norm{ z- A^Ty }^2 + y^T(Av - b)-z^Tv.
\end{array}
\]
\end{theorem}



\begin{block}{AND}
{\tiny

At each iteration, we get a provable/calculable lower bound 
\[
 \max_{z \geq 0, y} \phi(y,z) =
    -\frac12 \norm{ z- A^Ty }^2 + y^T(Av - b)-z^Tv
\]
}
\end{block}



\end{frame}
\begin{frame}
\frametitle{ {Proof of Optimality Conditions} }


\begin{proof}
$L(x,y,z) = \frac12 \norm{x-v}^2 + y^T(b-Ax)-z^Tx$;
 	 \\$ \nabla_x L(x,y,z) = x-v - A^Ty -z$;

$ \text{stationarity:  } 0=\nabla_x L(x,y,z) \implies  x = (v + A^Ty) +z$
$\implies L(x,y,z) = -\frac12 \norm{ z+ A^Ty }^2 + y^T(b-Av)-z^Tv$.


\begin{block}{KKT optimality conditions} 
\[
    \begin{array}{rclcll}
    \frac{\partial}{\partial x} L(x,y,z) &=& x - v - A^Ty - z  &=& 0& \text{(dual feasibility)} \\ 
        \frac{\partial}{\partial y} L(x,y,z) &=& Ax - b  &=& 0& \text{(primal feasibility)}\\ 
    \frac{\partial}{\partial z} L(x,y,z) &\cong &  x  \in (\Rnp-z)^+ &&& 
\text{(compl. slackness, }\\
       &&&&&  z^Tx=0 \text{  or  } \\
        &&&&&       z\circ x = 0)\\ 
    \end{array}
\]
\end{block}
\end{proof}


\end{frame}
\begin{frame}
\frametitle{ {Proof continued... } }


\begin{proof} [(cont...  Solve opt. cond.]
\[
\tiny
		\begin{bmatrix} x - v - A^Ty - z \\ Ax - b \\ z^Tx \end{bmatrix}
	= \begin{bmatrix} 0 \\ 0 \\ 0\end{bmatrix}, \quad x,z \in \R^n_+, y \in
	\R^m.
\]


{\crr Moreau Decomposition:}
\\${\crr v+A^Ty = x-z} \quad = x+(-z), x^Tz = 0$
\\ {\crr $x = (v+A^Ty)_+;\,\, z=-(v+A^Ty)_-$}

\begin{block}{}
\[
F:\Rm\to\Rm; \quad
\fbox{\crr $F(y)= A(v+A^Ty)_+ -b = 0, \,\, y\in \Rm$}
\]
\end{block}
\end{proof}

\begin{block}{Apply Newton at current $y_c$; Newton direction $\Delta y$}
$F^\prime(y_c) \Delta y = -F(y_c); \qquad y_p = y_c + \Delta y$
\end{block}




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


\begin{block}{Block Elimination on Perturbed KKT Conditions}
\[
\tiny
\begin{bmatrix} r_d \\ r_p \\ r_c\end{bmatrix}
:=		\begin{bmatrix} x - v - A^Ty - z \\ Ax - b \\ 
Zx-\mu e \end{bmatrix}
, \quad x,z \in \R^n_+, y \in
	\R^m.
\]
\[
\tiny
F_\mu^\prime \Delta s=	\begin{bmatrix} 
{\crr \underline{\Delta x}}  - A^T\Delta y - \Delta z \\ 
A\Delta x - b \\ 
X\Delta z+ Z\Delta x 
\end{bmatrix}
\begin{bmatrix} \Delta x\\ \Delta y\\ \Delta z \end{bmatrix}
=	
-\begin{bmatrix} r_d \\ r_p \\ r_c\end{bmatrix}
, \quad x,z \in \R^n_+, y \in
	\R^m.
\]

\end{block}
\begin{block}{Normal Equations Reduction to $\Delta y$}
Currently, normal equations are not considered efficient. But the Newton
equation was a percursor and appears to be efficient?
\[
F:\Rm\to\Rm; \quad
\fbox{\crr $F(y)= A(v+A^Ty)_+ -b = 0, \,\, y\in \Rm$}
\]

$F^\prime(y_c) \Delta y = -F(y_c); \qquad y_p = y_c + \Delta y$
\end{block}



\end{frame}
\begin{frame}
\frametitle{Nonlinear Least Squares, Generalized Jacobians}


\begin{block}{minimize squared residual $f(y)=\frac 12 \|F(y)\|^2$}
differentiable case $\{i : (v+A^Ty)_i=0\}=\emptyset$: 
 \quad $\nabla f(y) = (F^\prime(y))^*F(y)$
\end{block}


\begin{definition}[(local) Lipschitz Continuity]
Let $\Omega \subseteq \Rn$.
A function $F:\Omega \to \Rn$ is \emph{Lipschitz continuous} on $\Omega$
if there exists $K > 0$ such that 
\[
|F(y) - F(z)| \leq K \|y - z\|, \, \forall y,z \in \Omega.
\] 
$F$ is \emph{locally Lipschitz continuous} on $\Omega$ if for each
$x\in \Omega$ there exists a neighbourhood $U$ of $x$ such that $F$ is
Lipschitz continuous on $U$.
\end{definition}


\end{frame}
\begin{frame}
\frametitle{ {Generalized Jacobian} }

\begin{block}{Rademacher's Theorem \cite{Rademacher,MR41:1976}}
$F:\Omega \to \Rn$ locally Lipschitz on $\Omega$ implies that it 
is Frech\'et differentiable almost everywhere on $\Omega$.
\end{block}



\begin{definition}[Clarke \cite{Clarke:83} Generalized Jacobian]
Suppose that $F:\Rm \to \Rm$ be locally Lipschitz.
Let $D_F$ be the set of points such that $F$ is differentiable.
Let $F^\prime(y)$ be the usual Jacobian matrix at $y\in D_F$. The
\emph{generalized Jacobian of $F$ at $y$, $\partial F(y)$} is
\[
\partial F(y) = \conv \left\{\lim\limits_{\stackrel{y_i \to y}{y_i\in D_F}}
F^\prime(y_i) \right\}.
\]
In addition, $\partial F(y)$ is nonsingular if every $V\in \partial
F(y)$ is nonsingular.
\end{definition}



\end{frame}
\begin{frame}
\frametitle{Case: Differentiable and $F^\prime(y)$ invertible}

\begin{block}{Newton Direction; Newton Equation}
\[
(F^\prime(y))^*(F^\prime(y)) \Delta y = -(F^\prime(y))^*F(y) 
\iff  F^\prime(y) \Delta y = -F(y).
\]
\[
\Delta y = -\left((F^\prime(y))^*(F^\prime(y))\right)^{-1} 
               (F^\prime(y))^*F(y) = 
               -(F^\prime(y))^\dagger F(y)
\]
\end{block}

\begin{block}{directional derivative: $\Delta y^T \nabla f(y)=\ldots $}
$
\begin{array}{l}
 - \left[(F^\prime(y))^*F(y)\right]^T
\fbox{\crr $\left((F^\prime(y))^*(F^\prime(y))\right)^{-1}$ }
               \left[(F^\prime(y))^*F(y)\right]
\\ < 0
\end{array}
$
\end{block}


\end{frame}
\begin{frame}
\frametitle{Levenberg-Marquardt, \LM, Regularization Method}
We now see that we maintain a descent
direction.
\begin{lemma}[for handling singularity in 
$(F^\prime(y))^*(F^\prime(y))$] 
\LM direction is always a descent direction.
\end{lemma}
\begin{proof}
($J\cong F^\prime(y)$)
\[
(J^*J+\lambda I)\Delta y =  -J^* F.
\]
\[
\Delta y = -\left(J^TJ+\lambda I\right)^{-1} (J^TF).
\]
Therefore, the directional derivative is
\[
\begin{array}{rcl}
\Delta y^T \nabla f(y) 
&=&
 -\left(\left(J^TJ+\lambda I\right)^{-1} (J^TF)\right)^T (J^TF)
\\&=&
 -(J^TF)^T\left(\left(J^TJ+\lambda I\right)^{-1} \right) (J^TF)
\\&<&
 0.
\end{array}
\]
\end{proof}




\end{frame}
\begin{frame}
\frametitle{Max. Rank Generalized Jacobian}

\begin{block}{Cols chosen $\cong$  pos. variables of $w$}
$Aw_+ = A (\cPN w)  = (A\cPN)w_+ = \sum_{w_i>0} A(:,i)w_i$
\end{block}


\begin{block}{Index Set of Columns}
Note: $v+A^Ty\geq 0 \implies  F^\prime(\Delta y) = AIA^T\Delta y=
AA^T\Delta y$
$
\cU(y):= \left\{u \in \Rn \;|\; 
u_i \in 
\begin{array}{cl}
&\\
\left\{\begin{array}{cl}
1 & \text{ if } ( v +A^{T}y)_i>0 \\
 \left[0,1\right]  & \text{ if } ( v +A^{T}y)_i=0 \\
0 & \text{ if } ( v +A^{T}y)_i<0
\end{array} \right. \\
&
\end{array} 
\right \}
$
\end{block}



\begin{block}{generalized Jacobian at $y$; after convex hull}
$   \partial F(y) = \{A \, \Diag(u) \, A^T\,|\, u \in \cU (y) \}$
\\({\crr max-rank}: choose $u_i=1$ when possible)
\end{block}


\end{frame}
\begin{frame}
\frametitle{Semismooth Newton Method solving $F(y) = 0$}


\begin{block}{}
Solve $(V_k+\lambda I)d_{Newton} = - F(y^k)$, with
	$V_k \in \partial F(y^k), \lambda > 0, c \in (0,1)$
\[
	y^{k+1} =  y^k + d_{Newton}; \text{   \big(or avging   }
	y^{k+1} = (1-c)y^k + +c d_{Newton}\big)
\]
\end{block}


\begin{block}{Max-rank Jacobian}
\[
\begin{array}{rcl}
    AMA^T 
&:=  &
  A\Diag(u)  A^T  
\\&=& 
\sum_{i\in\cI_+}A_{:i}A_{:i}^T+ \sum_{i\in\cI_0}\alpha_i A_{:i}A_{:i}^T,
\, \alpha_i\in [0,1], \forall i\in \cI_0
\end{array}
\]
maximum (resp. minimum) rank for AMA:
\\$\alpha_i=1, \forall i \in \cI_0$ ($\alpha_i=0, \forall i \in \cI_0$,
resp.)
\end{block}


\end{frame}
\begin{frame}
\frametitle{Vertices and Polar Cones}

\begin{block}{Choosing the optima for the tests; (nondegenerate) vertex}
In our tests we can decide on the characteristics of the optimal
solution using the properties of (degenerate) vertices.
\\Recall: $x$ optimal iff $x-v\in \cF(x)^+$
\end{block}

\begin{lemma}[vertex and polar cone]
$y\in \Rm, x(y) = (v+A^Ty)_+ \in \cF$. Then:
\\$x(y)$ vertex $\iff$ $A_{\cI_+}$ nonsingular 
\\$~~\qquad \iff$ corresp. gen. Jac. nonsingular.
\\$x=x(y)\in \cF \implies$
\\$\cF(x)^+ = \{w : w = A^Tu + z, u \in  \Rm, z\in \Rnp, x^Tz=0\}$
\end{lemma}



\end{frame}
\begin{frame}
\frametitle{ Proof of Lemma }



\begin{proof}
wlog $A=[A_{\cI_+}~A_{\cI_0}]$ implies
active set is
$ \begin{bmatrix} A_{\cI_+}&A_{\cI_0}\cr 0     &     I
\end{bmatrix} x = 
\begin{pmatrix} b \cr 0
\end{pmatrix}$;
This has unique solution $x(y)$ iff $A_{\cI_+}$ is
nonsingular.

gradient of objective satisfies 
\[
x-v = A^Ty+ \sum_{j\in \cI_0} z_j e_j.
\]
Optimality conditions yield polar cone at a vertex.
\end{proof}

\begin{block}{degeneracy of optimal solutions}
Let $x\in \bdry \cF$;
\\$x$ is
optimal iff $x-v \in \cF(x)^+$, i.e.,~we can choose $v$ with
\\$ v = x - A^Tu +z, \, z\geq 0, \, z^Tx=0.  $
\\and
\\$ x^*(v) \text{  is differentiable at $v$  } \iff \,\,
(x^*(v)-v)  \in \relint (\cF-x^*(v))^+$

\end{block}



\end{frame}
\begin{frame}
\frametitle{Best Approx.; Nonsmooth Algor.}

\begin{algorithm}[H]
\small
	\begin{algorithmic}[1]
		\REQUIRE $v \in \Rn,y_0\in \Rm, \, (A \in \R^{m \times
		n},\rank(A)=m),\, \varepsilon>0$, maxiter% $\in \N$.
		\STATE \textbf{Output.} Primal-dual opt: $x_{k+1},(y_{k+1},z_{k+1})$
		\STATE \textbf{Initialization.} 
		$k \gets 0$, 
		$x_0 \gets (v+A^Ty_0)_+$,
		$z_0 \gets (x_0-(v+A^Ty_0))_+$,\\
		\qquad \qquad\qquad  $F_0 = Ax_0-b$,
		stopcrit $\gets \norm{F_0} / (1 + \norm{b})$ 
		\WHILE{((stopcrit $> \varepsilon) \,\&\, (k\leq
                $ maxiter)) }
		%	\IF{(Generalized Jacobian $V_k$ is nonsingular)}  
		%		\STATE $\bar V = V_k$ 
		%	\ELSE
				\STATE $\lambda = \min(1e^{-3}, \text{ stopcrit})$  
				\STATE $\bar V = (V_k+\lambda I_m)$ 
		%	\ENDIF	
			\STATE $\text{solve pos. def. } \bar V d = -F_k$ for Newton direction $d$ 
			\STATE \textbf{updates}  
			\STATE $ y_{k+1} \gets y_k + d$  
			\STATE $x_{k+1} \gets (v + A^Ty_{k+1})_+$ 
			\STATE $z_{k+1} \gets  (x_{k+1}-(v+A^Ty_{k}))_+$ 
			\STATE $F_{k+1} \gets Ax_{k+1} - b$ \text{  (residual)} 
			\STATE stopcrit $\gets \norm{F_{k+1}} / (1+\norm{b})$  
			\STATE $k \gets k + 1$
		\ENDWHILE
	\end{algorithmic}		
	\caption{Best Approx. of $v$ in $P$; Exact Newton}
	%\label{alg:ExactNonsmoothNewton}
\end{algorithm}


%C:\Users\hwolkowi\Dropbox\inprogress.d\21inprogress.d\21Censor-M-Wolkowicz-Tyler\CMWWcodes\semismoothCodesTests\tabletestresultsfiles\ProjTables\nondegVertexTables\sizeM3.tex




\end{frame}
\begin{frame}
\frametitle{
Halpern-Lions-Wittmann-Bauschke \cite{1996_Ba}}
{\tiny
\begin{equation}
\tiny
\label{tag:HLWB}
\text{Halpern-Lions-Wittmann-Bauschke \cite{1996_Ba}}
\tag{HLWB}
\end{equation}
}

		
\begin{algorithm}[H]
\tiny
	\begin{algorithmic}[1]
		\REQUIRE $v \in \Rn, (A \in \R^{m \times
		n},\rank(A)=m),\, \varepsilon>0$, maxiter $\in \N$.  
		\STATE \textbf{Output.}  $x_{k+1}$
		\STATE \textbf{Initialization.} 
		$k \gets 0$, $msweeps \gets 0$ 
               	$x_0 \gets max(v,0)$, $y_0 \gets x_0$, $i_0 = 1$ \\ 
		\qquad\qquad  \qquad 
		stopcrit $\gets \norm{Ay_0 - b} / (1 + \norm{b})$ ($=\norm{F_0} / (1 + \norm{b})$)
		\WHILE{((stopcrit $> \varepsilon) \,\&\, (k\leq
                $ maxiter))}  
			\IF{$1 \leq i(k) \leq m$} 
				\STATE $y_k = x_k +
				\frac {b_{i_k}-\langle
				a_{i_k},x^k\rangle}{\|a_{i_k}\|^2}a_{i_k}$ 
			\ELSE
				\STATE $y_k =\max(0,x_k)$ 
			\ENDIF
			\STATE \textbf{updates}  
			\STATE $\sigma_k = \frac{1}{k+1}$ ( change to  $\sigma_k = \frac{1}{msweeps+1}$??)
			\STATE $ x^{k+1} \gets \sigma_k v + (1 - \sigma_k) y^k$ 
			\STATE stopcrit $\gets  \norm{Ay_0 - b} / (1 + \norm{b})$ 
			\STATE $k \gets k + 1$ 
			\IF{$k \mod (m + 1) == 0$} 
				\STATE $msweeps = msweeps + 1$
			\ENDIF 
			\STATE $ i_k = k (\text{mod } m) + 1$
		\ENDWHILE
	\end{algorithmic}
	\caption{Extended HLWB algorithm}
	\label{alg:HLWB}
\end{algorithm}





\end{frame}
\begin{frame}
\frametitle{ {Numerical Tests BAP; varying sizes $m,n$} }

%%\input{../../CMWWcodes/NonsmoothNewtonLPapplic/tabletestresultsfiles/ProjTables/nondegVertexTables/data_tables_V2/sizeM3.tex}
%%\input{../../CMWWcodes/NonsmoothNewtonLPapplic/tabletestresultsfiles/ProjTables/nondegVertexTables/data_tables_V2/sizeN3.tex}
%%\input{../../CMWWcodes/NonsmoothNewtonLPapplic/tabletestresultsfiles/ProjTables/nondegVertexTables/data_tables_V2/dense3.tex}
%%\input{../../CMWWcodes/NonsmoothNewtonLPapplic/tabletestresultsfiles/LPApplTables/data_tables_V2/LP.tex}
%%\input{../../CMWWcodes/NonsmoothNewtonLPapplic/tabletestresultsfiles/ProjTables/degVertexTables/data_tables_V2/sizeM3.tex}
%%\input{../../CMWWcodes/NonsmoothNewtonLPapplic/tabletestresultsfiles/ProjTables/degVertexTables/data_tables_V2/sizeN3.tex}
%%\input{../../CMWWcodes/NonsmoothNewtonLPapplic/tabletestresultsfiles/ProjTables/degVertexTables/data_tables_V2/dense3.tex}


\begin{table}[H]
\begin{adjustwidth}{-4.1cm}{}
{\tiny
\caption{\tiny $n=3000$, \% density=$.81$; varying $m=100,600,1100,1600$}
{\tiny \input{sizeM3.tex}}
\label{table: nondegenerate sizeM3}
}
\end{adjustwidth}
\end{table}

\begin{table}[H]
\begin{adjustwidth}{-4.0cm}{}
{\tiny
\caption{\tiny $m=200$, \% density=$.81$, varying
$n=3000,3500,4000,4500,5000$}
\input{sizeN3.tex}
\label{table: nondegenerate sizeN3}
}
\end{adjustwidth}
\end{table}


\end{frame}
\begin{frame}
\frametitle{ {Numerical Tests BAP varying density} }


\begin{table}[H]
\begin{adjustwidth}{-4.0cm}{}
{\tiny
\caption{\tiny $m=300,~n=1000$, Varying \% density=$1,6,1.1,1.6$}
\input{dense3.tex}
\label{table: nondegeneratedense3}
}
\end{adjustwidth}
\end{table}

\end{frame}


\begin{frame}
\frametitle{Performance Profiles BAP}

\vspace{-.4in}
%\includepdf[pages=-,width=3in]{PerfProfBAP.pdf}
\includegraphics[page=1,width=5in]{PerfProfBAP.pdf}

\end{frame}



\begin{frame}
\frametitle{Applications: Solving (maximization) Large Scale LP}


\begin{block}{primal (maximization) LP in standard form}

\[
    \text{(PLP)} \qquad  
	  \begin{array}{rcl}
	    p_{LP}^* := & \max  & c^Tx \\
	    &  \text{s.t. } &Ax = b\in \Rm  \\
	    &         &x \in \Rnp.
    \end{array}
\]

\end{block}
\begin{block}{dual LP}
\begin{equation}
\label{eq:DLP}
    \text{(DLP)} \qquad  
	  \begin{array}{rcl}
	    d_{LP}^* := & \min  & b^Ty \\
	    &  \text{s.t. } &A^Ty -z = c\in \Rn \\
	    &         &z \in \Rnp.
    \end{array}
\end{equation}
\end{block}



\begin{block}{Assumptions: full rank; finite optimal value}
$A$ full row rank;
\\$p^*_\LP\in \R$ (so $p^*_\LP = d^*_\LP\in \R$ and both attained)
\end{block}



\end{frame}
\begin{frame}
\frametitle{Geometric Algorithm}


\begin{block}{}

solution can be
found from the limit as $R\uparrow \infty$ of the projection of the
vector $v_R=Rc\in \Rn$ onto the feasible set.
\begin{lemma}[\cite{MR83c:90098,MR774243,MR2062967,smw2}]
Let the given LP data be
$A,b,c$ with finite optimal value $p_{LP}^*$. For each $R>0$ define
\\$
\begin{array}{rcl}
	    x(R) := & \argmin_{x}  &\frac12 \norm{x-Rc}^2 \\ 
	    &  \text{s.t. } &Ax = b\in \Rm  \\
	    &         &x \in \Rnp.
    \end{array}
$
\\Then $x^*$ is the {\crr minimum norm solution} of (PLP) if, and only if,
there exists $\bar R > 0$ such that
\[
R \geq \bar R \implies
x^* \in \argmin \left\{ \frac12 \norm{x-Rc}^2 \,:\,
	    Ax = b, \, x \in \Rnp \right\}.
\]
\qed
\end{lemma}
We use the estimate
$R=\min\left\{50,\frac{\sqrt{mn}\|b\|}{1+\|c\|}\right\}$
\end{block}



\end{frame}
\begin{frame}
\frametitle{Avoid numerical/roundoff from large numbers}



\begin{corollary}[scaling $\frac 1Rb$]
$A,b,c,R,x(R)$ as in Lemma. Then
\[
	  \begin{array}{rcl}
	   \frac 1Rx(R) = w(R) := & \argmin_{w}  &\frac12 \norm{w-c}^2 \\ 
	    &  \text{s.t. } &Aw = \frac 1Rb\in \Rm  \\
	    &         &w \in \Rnp.
    \end{array}
\]
\end{corollary}
\begin{proof}
From 
\[
\norm{x-Rc}^2 =R^2\norm{\frac 1Rx-c}^2 =R^2\norm{w-c}^2, \, x=Rw,
\]
we substitute for $x$ and obtain $A(Rw) = b \iff Aw = \frac 1Rb$.
The result follows from the observation that $\argmin$ does not change
after discarding the constant $R^2$.
\end{proof}
%%
%%%%\subsubsection{Optimality Conditions for Scaling $c\leftarrow Rc$}
%%%%Recall the standard KKT optimality conditions for primal-dual 
%%%%variables $(x,y,z)$ for the projection problem from the proof
%%%%of~\Cref{thm:projoptndual}:
%%%%\begin{equation}
%%%%\label{eq:KKTRc}
%%%%	\begin{bmatrix} x  - A^Ty - z \\ Ax - b \\ z\circ x \end{bmatrix}
%%%%= \begin{bmatrix}  Rc \\ 0 \\ 0\end{bmatrix}, \quad x,z \in \R^n_+, y \in
%%%%\R^m.
%%%%\end{equation}
%%%%
%%%%We note that the main step of the algorithm uses the current value
%%%%$y$; and the following steps
%%%%\begin{enumerate}
%%%%\item
%%%%projection $x_+ = (Rc+A^Ty)_+$, (and $z_+ = x_+-(Rc+A^Ty)$);
%%%%\item
%%%%residual $F = Ax_+-b$;
%%%%\item
%%%%\[
%%%%d_i = \left\{
%%%%\begin{array}{cl}
%%%%1 & \text{if $(v+A'*y) \geq 0$} \\
%%%%0 & \text{otherwise}
%%%%\end{array}
%%%%\right.
%%%%\]
%%%%\item 
%%%%	??????? etc????
%%%%\end{enumerate}
%%%%The optimality conditions are now
%%%%\[
%%%%Rc+A^Ty = x - z, \, x^Tz = 0, x,z\geq 0, \quad
%%%%b = Ax = A(Rc+A^Ty)_+.
%%%%\]
%%%%This becomes
%%%%\[
%%%%A^T\left(-\frac 1Ry_R\right) -c - \frac 1Rz_R = - \frac 1Rx_R, \quad
%%%%x_R=x(R). 
%%%%\]
%%%%Since $\lim_{R\uparrow \infty} x_R = x^*,\, 
%%%%\lim_{R\uparrow \infty} \frac 1Rx_R = 0$, 
%%%%we conclude that  if one of the sequences converges, then both converge
%%%%and
%%%%\[
%%%%\lim_{R\uparrow \infty} \frac 1Ry_R = y^*,\quad \lim_{R\uparrow \infty} \frac
%%%%1Rz_R = z^*, 
%%%%\text{   a dual optimal pair}.
%%%%\]
%%%%
%%%%%Note that we can replace the objective with 
%%%%%$\frac 12\left\|\frac 1Rx -c\right\|^2$, and substitute $x\leftarrow
%%%%%\frac 1R x$. Therefore, the equivalent linear constraint 
%%%%%becomes $Ax_R = \frac 1R b$. We can recover the original optimal
%%%%%solutions $x\leftarrow Rx$.
%%%%
%%
%%\subsubsection{Optimality Conditions for Scaling $b\leftarrow\frac 1Rb$}
%%\label{sect:scalRb}
%%We consider the scaling in~\Cref{cor:wRargmin} and recall the relation 
%%between the scaling for $c$ with variable $x$:
%%\[
%%x(R) = Rw(R).
%%\]
%%The optimality conditions for $w(R)$ from the proof
%%of~\Cref{thm:gensimplfreevrble} are:
%%\[
%%	\begin{bmatrix} w - c - A^Ty - z \\ Aw - \frac 1Rb \\ z^Tw \end{bmatrix}
%%= \begin{bmatrix} 0 \\ 0 \\ 0\end{bmatrix}, \quad w,z \in \R^n_+, y \in
%%\R^m.
%%\]
%%We conclude that
%%\[
%%\lim_{R\to \infty} P_{\range(A^T)}w(R) = 0, \, 
%%\lim_{R\to \infty} Rw(R)= x^*, \,\, \text{the optimum of the LP}.
%%\]
%%The optimality conditions are now
%%\begin{equation}
%%\label{eq:optscaleb}
%%w = c+A^Ty + z, \, b = ARw = AR(c+A^Ty)_+, \quad
%%w^Tz = 0, x,z\geq 0.
%%\end{equation}
%%This means that $\|w\|$ is an estimate for the error in dual
%%feasibility, i.e.,~an estimate for the accuracy of $Rw$ as the optimum
%%of the original LP.
%%
%%Note that we have a current approximate optimal $w_c=w(R_c)$ and then increase 
%%$R_c\uparrow R_+$ if we do not yet have the LP optimum. It is appropriate to
%%continue with a \textdef{warm start} for the best approximation problem,
%%i.e.,~we consider finding a nearby $y_+$. Denote the new optimum to be
%%found $w_+ = \frac {R_c}{R_+} w_c$.
%%The new primal-dual feasibility  is
%%\[
%%A w_+ -\frac 1{R_+} b = 0, \quad w_+ -c - A^T y_+ - z_+ = 0.
%%\]
%%%%\begin{noteH}
%%%%???the best warm start would solve
%%%%$\min \|(yc,zc)-(y+,z+)\|$ s.t. $
%%%%\frac {R_c}{R_+} w_c - c = A^Ty_+ + z_+, z_+ \geq 0$.
%%%%fix this up to match \cref{eq:dualfeasB} so $z_+$ is split into two but
%%%%with the $w_c$ included.
%%%%\end{noteH}
%%%%
%%%%We note that this can be divided into positive $w_i>0$, zero, and
%%%%$z_i>0$ variables. ????? best is what????
%%As a heuristic we could use the following for a \textdef{warm start}
%%\[
%%y_+ = \frac {R_c}{R_+} y, \, z_+ = \frac {R_c}{R_+} z.
%%\]
%%
%%
%%\subsubsection{Upper Bound for \LP Maximization Problem}
%%Note that in~\Cref{sect:scalRb} primal feasibility and complementary
%%slackness hold for $x(R) = Rw,z$ and this is identical for the LP
%%problem. We therefore need to find $y_\LPt$ to satisfy the LP dual
%%feasibility
%%\[
%%z_\LPt = A^Ty_\LPt - c \geq 0.
%%\]
%%But, from the projection problem optimality conditions we have
%%\[
%%A^T(-y) = z + c - w, \, 0\preceq z = A^T(-y) -c + w, \, w\geq 0.
%%\]
%%As seen above, this means that in the limit, $w$ is small and we do get
%%dual feasibility $y(R)\to y_\LPt$. But at each iteration we actually have
%%\begin{equation}
%%\label{eq:otpcondR}
%% z-w = A^T(-y) -c, \, z,w\geq 0, z^Tw = 0, \quad y\cong y_R.
%%\end{equation}
%%We can write the required dual feasibility equations using the indices for $w_i>0$.
%%\[
%%A_{:i}^Ty - c_i \in \left\{\begin{array}{rl}  \{0\}, & \text{if  } w_i > 0, \\
%%                                            \R_+, & \text{if  } w_i = 0.
%%\end{array}
%%\right.
%%\]
%%We let 
%%\begin{equation}
%%\label{eq:defB}
%%\textdef{$\cB=\cB(w) = \cI_+(w) = \{i\,:\, w_i > 0\}$}.
%%\end{equation}
%%We let $\cN = \{1:n\}\backslash \cB$.
%%Then for a given $y_R$ from the optimality conditions from the projection
%%problem~\cref{eq:otpcondR},
%%we consider the nearest dual \LP feasible system with unknowns $z\geq
%%0,y_\LPt$. Note that we are using the projection with free
%%variables,~\Cref{sect:freevrbls}.
%%\begin{lemma}
%%\label{lem:upperbndLP}
%%Let $w,y=y_R,z$ be approximate optimal solutions from~\cref{eq:optscaleb}
%%and $\cB$ the support defined in~\cref{eq:defB}. Consider the nearest
%%dual feasibility program
%%\begin{equation}
%%\label{eq:dualfeasB}
%%\begin{array}{rcl}
%%\begin{pmatrix}y^*_\LPt\cr z^*_\LPt\end{pmatrix} \in &\argmin & \frac 12
%%\|(-y_R) - y_\LPt\|^2 
%%+\frac 12 \|0-z_\cB\|^2
%%+ \frac 12 \|(z_R)_\cN - z_\cN\|^2 \quad \left(=\frac 12 \|v-x\|^2\right)\\
%%& \text{s.t.} & 
%%\begin{bmatrix} A_{:\cB}^T &-I & 0\cr
%%A_{:\cN}^T   &0&-I
%%\end{bmatrix}
%%\begin{pmatrix}
%%y_\LPt \cr
%%z_\cB \cr
%%z_\cN
%%\end{pmatrix}
%%=
%%\begin{pmatrix}
%%c_\cB \cr
%%c_\cN
%%\end{pmatrix} \\ 
%%& & y_\LPt \text{ free}, \,
%%z_\LPt=
%%\begin{pmatrix}
%%z_\cB\cr z_\cN
%%\end{pmatrix}\geq 0.
%%\end{array}
%%\end{equation}
%%Then the optimal value of the \LP \cref{eq:PLP} satisfies the upper bound
%%\[
%%p^*_\LPt \leq b^Ty^*_\LPt.
%%\]
%%Moreover, suppose that $z_\cB =0$. Then equality holds and the \LP is
%%solved with primal-dual optimum pair $(w,y_\LPt)$.
%%\end{lemma}
%%\begin{proof}
%%Recall that the optimal value $p^*_\LPt$ is finite.
%%The proof of the bound follows from weak duality in linear programming.
%%Equality follows from the optimality conditions since primal feasibility
%%and complementary slackness hold with $w$.
%%\end{proof}
%%
%%

\end{frame}

\begin{frame}
\frametitle{Warm Start; Stepping Stone External Path Following}

consider scaled problem with:
\[
x(R) = Rw(R).
\]
Recall the optimality conditions for $w = w(R)$:
\[
	\begin{bmatrix} w - c - A^Ty - z \\ Aw - \frac 1Rb \\ z^Tw \end{bmatrix}
= \begin{pmatrix} 0 \\ 0 \\ 0\end{pmatrix}, \quad w,z \in \R^n_+, y \in
\R^m.
\]
We conclude that
\[
\lim_{R\to \infty} \cP_{\range(A^T)}w(R) = 0, \, 
\lim_{R\to \infty} Rw(R)= x^*, \,\, \text{the optimum of the LP}.
\]
The optimality conditions are now
\[
w = c+A^Ty + z, \, b = ARw = AR(c+A^Ty)_+, \quad
w^Tz = 0, x,z\geq 0.
\]


%This means that $\|w\|$ is an estimate for the error in dual
%feasibility, i.e.,~an estimate for the accuracy of $Rw$ as the optimum
%of the original LP.

\end{frame}

\begin{frame}
\frametitle{Warm Start from current $R$: find new $R_n,\, y_n$}
%the projection algorithm for a warm start process. We use sensitivity
%analysis for the projection problem. In the sequel $A^\dagger$ denotes
%the generalized (Moore-Penrose) inverse of a matrix $A$.
\begin{theorem}
%\label{thm:pathfollowR}
Suppose triple $(w,y,z)$ optimal for scaled problem; let
\\$
\begin{array}{c}
\cN =\cN(z)=  \{i\,:\, z_i > 0\}, \quad
\cB=\cB(w) = \{1:n\}\backslash \cN;\\
 b_\cB = A_\cB^T \left(A_\cB A_\cB^T\right)^\dagger b, \quad
 b_\cN = A_\cN^T \left(A_\cB A_\cB^T\right)^\dagger b;\\
e = \begin{pmatrix}
   (b_\cB-Rw_\cB)\cr -(b_\cN+Rz_\cN)
    \end{pmatrix},\quad
f = \begin{pmatrix}
   Rb_\cB\cr -Rb_\cN
    \end{pmatrix}.
\end{array}
$
\\Then max. value $R$ without changing basis is 
\\$
R_n = \min\{{\crb f_i/e_i : e_i > 0, f_i > 0, \, i=1,\ldots |\cB|}\}.
$
\\Moreover, $R_n=\infty$ implies optimal solution found.

\end{theorem}


\begin{block}{$R_n<\infty \implies$ corresponding changes are:}
%$\Delta w,\Delta y,\Delta z$ that result in 
%$w+\Delta w,y+\Delta y,z+\Delta z$ optimal for $R_n$
%are given in the proof that follows.
$\Delta y_p = \left(A_\cB A_\cB^T\right)^\dagger b$;
$\Delta y = \left(\frac {R-R_n}{RR_n}\right) \Delta y_p$.
\\$\Delta w_\cB = A_\cB^T \left(\frac {R-R_n}{RR_n}\right) \Delta y_p$
\\$\Delta z_N = -A_\cN^T \left(\frac {R-R_n}{RR_n}\right) \Delta y_p$

\end{block}


%%\begin{proof}
%%We want to find the maximum increase in $R$ that keeps the current
%%basis $\cB$ optimal for~\ref{eq:LPwR}. We have
%%\linelabel{line:dwB}
%%\label{page:dwB}
%%\[
%%\begin{array}{c}
%%A_\cB (w_\cB+\Delta w_\cB) = \frac 1{R_n} b \implies 
%%         A_\cB \Delta w_\cB =  \left(\frac 1{R_n} - \frac 1{R}\right) b
%%\\ w_B +\Delta w_\cB -c_\cB -A_\cB^T(y+\Delta y)  = 0 \implies
%%                                    \Delta w_\cB  =A_\cB^T(\Delta y)
%%\implies A_\cB A_\cB^T(\Delta y) = 
%%                \left(\frac {R-R_n}{RR_n}\right) b
%%\\  -c_\cN -A_\cN^T(y+\Delta y) - (z_\cN +\Delta z)  = 0 \implies
%%                    \Delta z =  -A_\cN^T(\Delta y).
%%\end{array}
%%\] 
%%We now {\crb define 
%%$\Delta y_p := \left(A_\cB A_\cB^T\right)^\dagger b$ and set
%%$\Delta y = \left(\frac {R-R_n}{RR_n}\right) \Delta y_p$.}
%%We have
%%\[
%%-w_\cB\leq {\crb \Delta w_\cB} 
%%= A_\cB^T \left(\frac {R-R_n}{RR_n}\right) \Delta y_p
%% = -\left(\frac {R_n-R}{RR_n}\right)A_\cB^T 
%% \left(A_\cB A_\cB^T\right)^\dagger b 
%% =: -\left(\frac {R_n-R}{RR_n}\right)b_\cB.
%%\]
%%We get that 
%%\[
%%(R_n-R)b_\cB \leq (RR_n)w_\cB \,\implies \, R_n(b_\cB-Rw_\cB) \leq
%%	Rb_\cB.
%%\]
%%To find the
%%maximum $R_n$ and check that it is not $R_n=\infty$, we use an \LP type
%%ratio test. We set the two vectors to be
%%$e=(b_\cB-Rw_\cB),\, f=  Rb_\cB$.
%%Note that the inequality holds trivially for $R_n=R$. Therefore, we
%%cannot have $e_i > 0, f_i\leq 0$. We choose $R_n$ to be the maximum that
%%satisfies {\crb the ratio test, i.e.,~we get:
%%\[
%%{\crb \left( \right.} 
%%\max_i \{ f_i/e_i,   f_i < 0, e_i <0 , \, i=1,\ldots |\cB|\} \leq
%%{\crb \left. \right)} \quad
%%R_n = \min_i 
%%\{ f_i/e_i,   f_i > 0, e_i >0 , \, i=1,\ldots |\cB|\},
%%\]
%%}
%%where the minimum over the empty set is taken to be $+\infty$. {\crb
%%Note that the inequality on the left
%%in brackets holds since $R_n=R>0$ satisfies the
%%inequality.}
%%
%%We now need to similarly do a ratio test for $z$. We have
%%
%%\[
%%-z_\cN\leq \Delta z = -A_\cN^T \left(\frac {R-R_n}{RR_n}\right) \Delta y_p
%% = \left(\frac {R_n-R}{RR_n}\right)A_\cN^T 
%% \left(A_\cB A_\cB^T\right)^\dagger b 
%% =: \left(\frac {R_n-R}{RR_n}\right)b_\cN.
%%\]
%%We get that 
%%\[
%%(R_n-R)b_\cN \geq -(RR_n)z_\cN \,\implies \, R_n(-b_\cN-Rz_\cN) \leq
%%	-Rb_\cN.
%%\]
%%We again find the maximum $R_n$ and check that we do not have 
%%$R_n=\infty$ using an \LP type
%%ratio test. We set the two vectors to be
%%$e=-(b_\cN+Rz_\cN),\, f=  -Rb_\cN$.
%%Recall that the inequality holds trivially for $R_n=R$. Therefore, we
%%cannot have $e_i > 0, f_i\leq 0$. We choose $R_n$ to be the maximum that
%%satisfies:
%%\[
%%\max_i \{ f_i/e_i, \text{  if  }  f_i < 0, e_i <0 \} \leq
%%R_n = \min_i 
%%\{ f_i/e_i, \text{  if  }  f_i > 0, e_i >0 \}.
%%\]
%%
%%We choose $R_n$ as the minimum of the above two values found.
%%
%%Finally, if $R_m=\infty$, then the basis does not change as $R$
%%increases to infinity, i.e.,~the optimal basis has been found.
%%\end{proof}
%%
%The above~\ref{thm:pathfollowR} illustrates the external path following
%algorithm that we are using. The theorem finds specific values of $R$,
%\emph{stepping stones on the path},
%where the current choice of columns of $A$ changes. Once we find that
%the next {stepping stone} is at infinity, we know that we have
%found the optimal choice of columns of $A$. Thus we have an external
%path following algorithm with parameter $R$ but we only choose specific
%points on this path to \emph{step} on. 
%%
%%
%%
%%
%%
%%
\end{frame}

\begin{frame}
\frametitle{LP Numerical Tests}


%\vspace{-.4in}
\hspace{-.8in}
%\includepdf[pages=-,width=3in]{PerfProfBAP.pdf}
\includegraphics[page=1,width=5in]{LPtests.pdf}


\end{frame}


\begin{frame}
\frametitle{Performance Profile LP}


%\vspace{-.4in}
\hspace{-.8in}
%\includepdf[pages=-,width=3in]{PerfProfBAP.pdf}
\includegraphics[page=1,width=5in]{PerfProfLP.pdf}


\end{frame}


\begin{frame}
\frametitle{Conclusion for BAP and LP Algorithm}
\begin{itemize}
\item
efficient, robust algorithm for projection of a point onto a polyhedral
set.
\item
One of may applications is to solving large scale \LPp s; we get a
finite converging stepping stone
exterior path following algorithm (mixture of simplex/interior-point)
\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}
