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


\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{\cU}{{\mathcal U}}
\newcommand{\cPN}{{\cP_\cN}}
%\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{\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{\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{\bdry}{bdry}
\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} 
	Regularized Nonsmooth Newton Algorithms\\
	for Best Approximation\\ 
	with Applications

}
\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{
Fri. Nov. 25, 13:00-14:00 EST, 2022
\vspace{.09in}



{
\vspace{.09in}
	{\crb   
 joint work with:  
Yair Censor (Univ. of Haifa);
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 $v$ from $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. 
\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 dimensions applications
extended 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}, 
\cite{QiSun:93nonsmooth,QiSun:06}. 
\item
More recently: applications 
for nearest doubly stochastic and nearest Euclidean distance matrices
in~\cite{HuImLiWo:21,homwolkA:04}.

\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{aligned}
        \frac{\partial}{\partial x} L(x,y,z) &= x - v - A^Ty - z  = 0\quad \text{(dual feasibility)} \\ 
        \frac{\partial}{\partial y} L(x,y,z) &= Ax - b  = 0\quad \text{(primal feasibility)}\\ 
    \frac{\partial}{\partial z} L(x,y,z) &\cong  x  \in (\Rnp-z)^+ \quad
\text{(compl. slackness $z^Tx=0$)}\\ 
    \end{aligned}
\]
\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{Nonlinear Least Squares, Generalized Jacobians}


\begin{block}{minimize squared residual $f(y)$}
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 varying sizes $m,n$} }
\begin{table}[H]
\begin{adjustwidth}{-1.5cm}{}
{\tiny
\caption{\tiny Varying $m=100,600,1100,1600$}
\input{C:/Users/hwolkowi/Dropbox/inprogress.d/21inprogress.d/21Censor-M-Wolkowicz-Tyler/CMWWcodes/semismoothCodesTests/tabletestresultsfiles/ProjTables/nondegVertexTables/sizeM3.tex}
\label{table: nondegenerate sizeM3}
}
\end{adjustwidth}
\end{table}

\begin{table}[H]
\begin{adjustwidth}{-1.5cm}{}
{\tiny
\caption{\tiny Varying $n, m=200$}
\input{C:/Users/hwolkowi/Dropbox/inprogress.d/21inprogress.d/21Censor-M-Wolkowicz-Tyler/CMWWcodes/semismoothCodesTests/tabletestresultsfiles/ProjTables/nondegVertexTables/sizeN3.tex}
\label{table: nondegenerate sizeN3}
}
\end{adjustwidth}
\end{table}


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


\begin{table}[H]
\begin{adjustwidth}{-1.5cm}{}
{\tiny
\caption{\tiny Varying problem density, $m=300$}
\input{C:/Users/hwolkowi/Dropbox/inprogress.d/21inprogress.d/21Censor-M-Wolkowicz-Tyler/CMWWcodes/semismoothCodesTests/tabletestresultsfiles/ProjTables/nondegVertexTables/dense3.tex}
\label{table: nondegeneratedense3}
}
\end{adjustwidth}
\end{table}



\end{frame}
\begin{frame}
\frametitle{Solving (maximization) Linear Programs}


\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}
$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}
\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{Conclusion}

\begin{itemize}
\item
efficient, robust algorithm for projection of a point onto a polyhedral
set.
\item
One of may applications is to solving linear programs - a type of 
exterior path following algorithm.
\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}
