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