\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 { \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 y0 , \ \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 } \ \=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 \ =\ = \ = \ = 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)}{ \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} \ = 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 } \ \ = 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 AVr$ $\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}{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{\}{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 $\ =0$ holds. %%%\item Pick $y \in \Rm$ and set $c = A^T y +s$. We note that $\ =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, \ \=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, \ = \sum_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}