88,89d87 < \newcommand{\notimplies}{% < \mathrel{{\ooalign{\hidewidth$\not\phantom{=}$\hidewidth\cr$\implies$}}}} 91d88 < 160a158,161 > \newcommand{\LSF}{{\bf{\rm LSF\,}}} > \newcommand{\LSFp}{{\bf{\rm LSF}}} > \newcommand{\BFS}{{\bf{\rm BFS\,}}} > \newcommand{\BFSp}{{\bf{\rm BFS}}} 333a335,336 > > 336c339,343 < Strict Feasibility and Degeneracy in Linear Programming --- > Linear Programming: > \begin{flushleft} > Part (i): Strict Feasibility and Degeneracy > \\Part (ii): Exterior Point Path Following Algorithm > \end{flushleft} 371,372c378 < \tiny Fri. Nov. 4, 09:00-10:00 EDT < 2022 --- > \tiny Monday April 10, 2023 378,382c384,441 < \\ < %At: {\crr < %\href{https://caims.ca/annual-meeting-2022/}{ < %Frontiers in Mathematics < % Changchun, China\\ Sept. 26-29, 2022. --- > %\\ > %At: > %{\crr > %\href{https://www.informs.org/Meetings-Conferences/INFORMS-Conference-Calendar/2022-INFORMS-Annual-Meeting}{ > %2022 INFORMS Annual Meeting > %}} > %\\ Thursday 19th and Friday 20th May 2022 > %Workshop on Numerical Linear Algebra and Optimization > \begin{figure}[htb] > \epsfxsize=105pt > \centerline{at: \hspace{.4in} \epsfbox{logo-mathstat-orng-dip.pdf}} > %\centerline{\epsfbox{CAIMSubc.jpg}} > %\centerline{\epsfbox{ttl-western-logo-trans.eps}} > %\centerline{\epsfbox{Mallardjpg.pdf}} > %\centerline{\epsfbox{ttl-western-logo-trans.pdf}} > %\vspace{-.12in} > \end{figure} > %\vspace{.09in} > % {\crb > % joint work with: Jiyoung Im, Univ. of Waterloo > % } > } > } > > > \subject{Talks} > > \def\defn#1{{\color{red} #1}} > > %\input{ainput} > %---------------------------------------------------------- > \begin{frame} > \titlepage > \end{frame} > %---------------------------------------------------------- > > > \title{ > \color{blue} > LP Part (i): Strict Feasibility and Degeneracy > } > \author[Wolkowicz] > { > Henry Wolkowicz > \\{\tiny Dept. Comb. and Opt., University of Waterloo, Canada} > \vspace{-.35in} > } > \vspace{-3in} > %\vspace{-.23in} > > %\institute{ > %\begin{small} > %%\vspace{1em} > %\end{small} > %%(Parts of this talk represent work based on Refs: > %%\cite{bw2,bw1,KrislockWolk:10,ScTuWonumeric:07,ForbesVrisWolk:11} > %%)\\ > 384c443,458 < %} --- > > \date{ > %\vspace{-.48in} > %\begin{figure}[htb] > %\includegraphics[width=0.5\textwidth]{SNLfig.eps} > %\includegraphics[width=0.75\textwidth]{fig300.eps} > %\includegraphics[angle=270,width=1.00\textwidth]{CMSpic.pdf} > %\includegraphics[width=.5]{CMSpic.pdf} > %\includegraphics[width=0.25\textwidth]{18-fall-Campus.pdf} > %\includegraphics[width=2.8cm,height=2.8cm,keepaspectratio]{ospreyTHREEjul2520.pdf} > %\epsfxsize=180pt > %\centerline{\epsfbox{fig300.eps}} > %\centerline{\epsfbox{SNLfig.eps}} > %\end{figure} > %\vspace{.09in} > \tiny Monday April 10, 2023 386,388c460,470 < {\crb < joint work with: Jiyoung (Haesol) Im, University of Waterloo < } --- > \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 390,391c472,474 < %\begin{figure}[htb] < %\epsfxsize=185pt --- > \begin{figure}[htb] > \epsfxsize=105pt > \centerline{at: \hspace{.4in} \epsfbox{logo-mathstat-orng-dip.pdf}} 397c480,484 < %\end{figure} --- > \end{figure} > %\vspace{.09in} > {\crb > joint work with: Jiyoung Im, Univ. of Waterloo > } 443c530 < \begin{block}{We show that lack of strict feasibility:} --- > \begin{block}{We show that lack of strict feasibility, \LSF:} 450c537,538 < and {\crr $\implies$ all} basic feasible solutions, BFS, are degenerate --- > and {\crr \LSF $\implies$ all} basic feasible solutions, {\crr \BFSp}, > are \\ \qquad \qquad \qquad \qquad {\crr degenerate} 461c549 < \frametitle{Background and Notation} --- > \frametitle{Standard Background and Notation for \LPp} 465c553 < \begin{block}{Feasible \LPp s; standard form (with \underline{FINITE} --- > \begin{block}{Feasible \LPp s; {\crr standard form} (with \underline{FINITE} 475c563 < assume wlog $\rank(A) = m$; --- > $\rank(A) = m$; with {\crr feasible set} 477d564 < \text{with feasible set: }\quad 494d580 < 497,525d582 < \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} 535c592 < \min & c^Tx\\ --- > \min_x & c^Tx\\ 540c597 < there exists $\hat x$ with $A\hat x=b, \hat x>0$ \qquad (MFCQ) --- > there exists $\hat x$ with $A\hat x=b, x>0$ \qquad ({\crr MFCQ}) 552c609 < there exists $\hat y$ with $A^T\hat y there exists $\hat y$ with $A^T\hat y \begin{block}{Stability} > MFCQ/Slater is equivalent to stability wrt RHS perturbations 577c620 < \frametitle{ Basic (Feasible/Degenerate) Solutions } --- > \frametitle{ Basic (Feasible) Solutions, \BFS } 580c623 < \begin{definition}[basic (feasible) solution] --- > \begin{definition}[basic (feasible) solution, \BFSp; basis $\cB$] 586,587c629,630 < \\Then $x$ is a {\crb basic solution} if < \\\quad \fbox{\crr $A(:,\cB)$ is nonsingular --- > \\Then $x$ is a {\crr basic solution} with {\crr basis $\cB$} if > \\\quad \fbox{ $A(:,\cB)$ is nonsingular 590,592c633 < $x$ is a basic \underline{\crr feasible} solution, {\crr BFS}, < if in addition $\crr x\geq 0$. It is {\crr degenerate}, if $\exists i\in\cB, < x_i=0$ --- > $x$ is a basic \underline{feasible} solution, \BFSp, if in addition $x\geq 0$. 596,597c637,638 < \begin{block}{Equivalently, if $Ax=b, x\geq 0$ (feasible):} < $x$ is {\crr basic} if there exists $\cN\subset\{1,\ldots,n\}, |\cN|=n-m, --- > \begin{block}{Equivalently, with $Ax=b$; lin. indep. active set:} > $x$ is basic if there exists $\cN\subset\{1,\ldots,n\}, |\cN|=n-m, 599c640 < \\and the corresponding matrix of {\crr active constraints} --- > \\and the matrix of {\crr active} constraints 606d646 < It is {\crr degenerate} if there are redundant active constraints. 616c656 < \begin{definition}[Degenerate BFS] --- > \begin{definition}[Degenerate \BFSp] 619c659 < x \text{ BFS is}\quad --- > x \text{ \BFS is}\quad 638c678 < \begin{block}{$\bar x$ a degenerate BFS with basis $\cB$ is of type:} --- > \begin{block}{$\bar x$ a degenerate \BFS with basis $\cB$ is of type:} 641c681 < if: $i \in \cB, \bar x_i=0 \implies i \in \cI^<$ --- > $i \in \cB, \bar x_i=0 \implies i \in \cI^<$ 644c684 < if: there exists $i\in \cB \cap \cI^=$ --- > there exists $i\in \cB \cap \cI^=$ 646,650c686 < < ~\\ < Below we see that: < \\if Type \ref{item:bfs2} exists, then {\crr ALL BFS are of Type < \ref{item:bfs2}}. --- > Below: if type two exists, then ALL \BFS are of type 2. 656,657c692 < \frametitle{{\crr Facial Reduction, \FRp}, for \LPp s that fail Strict < Feasibility} --- > \frametitle{Facial Reduction for \LPp s without Strict Feas.} 663c698 < \\ \quad(always needed for MFCQ) --- > (always needed) 668,669c703,705 < \begin{definition}[Face of a convex set $K$] < A convex set $F \subseteq K\subseteq\Rn$ is a face of $K$, --- > \begin{definition}[Face] > A convex set $F \subseteq K\subseteq\Rn$ is called a face of the > convex set $K$, 672c708 < \crb y,z \in K, x = \frac{1}{2}(y +z) \in F \implies y,z \in F. --- > \crb y,z \in K, x = \frac{1}{2}(y +z) \in F \implies y,z \in F 674,675c710,711 < \\ The {\crr minimal face} for $F, \face(F)$, < is the intersection of all faces of $K$ containing $C$. --- > \\Given a convex set $\cC\subseteq K$, the {\crr minimal face} for $\cC$ > is the intersection of all faces of $K$ containing the set $\cC$. 695c731 < {\crr (*)} \quad 0\neq {\crr z} := A^Ty \in \Rm_+, \ \text{ and } \ \=0, --- > {\crr (*)} \quad 0\neq z := A^Ty \in \Rm_+, \ \text{ and } \ \=0, 700c736 < \begin{block}{exposing vector ${\crr z}\in \Rnp$} --- > \begin{block}{exposing vector $z\in \Rnp$} 702c738 < \\{\crr exposing vector} $0\neq {\crr z}\geq 0$ exists for the --- > \\{\crr exposing vector} $0\neq z\geq 0$ exists for the 710c746 < \langle {\crr z},x \rangle = --- > \langle z,x \rangle = 721c757 < \frametitle{Facial Reduction two steps; Outline} --- > \frametitle{Facial Reduction; Outline} 723,724c759,760 < \begin{block}{suppose strict feasibility fails; i.e.,~get {\crr exposing < vector $z$}} --- > \begin{block}{suppose strict feasibility fails; get {\crr exposing > vector} $z$} 728c764 < Thm of Alternative implies: $\exists 0\lneq {\crr z}=A^T y\in \Rm$: --- > Thm of Alternative implies: $\exists 0\lneq z=A^T y\in \Rm$: 731,734c767,768 < 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$} --- > x \in \cF & \implies & 0\leq \ =\ = \ = \ = 0 > \\ & \implies & 0 = x \circ z 737,738c771 < {\crb cardinality of support of ${\crr z}$}: $s_{\crr z} = \left| \{i : < {\crr z}_i > 0\}\right|$ --- > {\crb cardinality of support of $z$}: $s_z = \left| \{i : z_i > 0\}\right|$ 741c774 < ${\crr z} = \sum\limits_{j=1}^{s_{\crr z}} {\crr z}_{t_j} e_{t_j}$, $t_j$ nondecreasing order --- > $z = \sum\limits_{j=1}^{s_z} z_{t_j} e_{t_j}$, $t_j$ nondecreasing order 744c777 < $x = \sum\limits_{j=1}^{n-s_{\crr z}} x_{s_j} e_{s_j}$, $s_j$ nondecreasing order. --- > $x = \sum\limits_{j=1}^{n-s_z} x_{s_j} e_{s_j}$, $s_j$ nondecreasing order. 747,749c780,782 < 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}$. --- > V =\begin{bmatrix}e_{s_1} & e_{s_2} & \ldots & e_{s_{n-s_z}} > \end{bmatrix} \in \R^{n\times (n-s_z)}$ > \quad ($\cong x_{s_j} >0$) 752c785 < \{x = Vv \in \Rn : AVv = b, v \in \R^{n-s_{\crr z}}_+\}$} --- > \{x = Vv \in \Rn : AVv = b, v \in \R^{n-s_z}_+\}$} 767c800 < Every facial reduction step yields at least one redundant constraint, --- > Every facial reduction step yields at least one constraint is redundant, 776c809 < Then at least one linear constraint of the \LP is {\crr redundant}. --- > Then at least one linear constraint of the \LP is redundant. 778c811 < Let: $0\neq {\crr z}=A^Ty\geq 0$ exposing vector; $V$ corresponding --- > Let: $0\neq z=A^Ty\geq 0$ exposing vector; $V$ corresponding 794c827 < $ --- > \[ 799,800c832 < \{x = Vv \in \Rn : \bar Av:=(P_{\bar m} AV)v = (P_{\bar m} b)=:\bar b, < \\&& \qquad v \in \R^{n-s_z}_+\} --- > \{x = Vv \in \Rn : (P_{\bar m} AV)v = (P_{\bar m} b), \ v \in \R^{n-s_z}_+\}, 802c834 < $ --- > \] 805,806c837 < {\crr after substit: } $\min (V^Tc)^Tv$ s.t. $\bar A v = \bar v, \, v < \in \R^{n-s_z}_+$ --- > $\exists {\crr \hat v>0}, (P_{\bar m} AV)v = (P_{\bar m} b)$ 808,812c839,840 < $\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)} {\crr full rank $P_{\bar m}AV$:} $P_{\bar m} : \Rm \to \R^{\bar m}$, > {$\bar m ={\rank(AV)} This emphasizes the ill-conditioning of problems where strict feasibility 829c857,858 < \frametitle{Singularity Degree $sd(\cF)$, Sturm '20 \cite{S98lmi}} --- > \frametitle{Singularity Degree Sturm: \cite{S98lmi}, > $sd(\cF)$: min \# FR steps} 833,834d861 < \begin{definition}[${\crr d}=sd(\cF) = \min |FR~steps|$] < \end{definition} 837,839c864,865 < the pair of closed, convex subsets $A, B$ is $\gamma${\em-H\"{o}lder regular} < if < \ $\forall U$ compact, $\exists c> 0$ with:\\ --- > pair closed, convex subsets $A, B$. is $\gamma${\em-H\"{o}lder regular} if > $\forall U$ compact, $\exists c> 0:$\\ 848,852c874,875 < \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) --- > \begin{block}{Sturm \cite{S98lmi} error bound for SDP:} $d=sd(\cF)$ > $\cF = \cL\cap \Snp$, $(\cL,\Snp)$ is $\frac 1{2^d}$-H\"older regular. 864,867c887,892 < $\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$ for {\crr \LPp s}, it is known that > \FR can be done in {\crr \emph{one} iteration}, > i.e., > \[ > \sd(\cF) \le 1 > \] % see~\cite[Theorem 4.4.1]{DrusWolk:16}. 869,871c894,896 < $\bullet$ \FR for \LPp s does not alter < sparsity pattern of $A$. < (only involves discarding columns of $A$; rows of $A,b$) --- > $\bullet$ \FR performed on the \LPp s does not alter the > sparsity pattern of the data matrix $A$. > (only involves discarding rows and columns of $A$) 879,881c904 < \frametitle{A Theoretical Result on degenerate BFS $\leftrightarrow$ < MFCQ < } --- > \frametitle{Main Theoretical Result} 884,885d906 < \footnote{Contrapositive found in < Bertsimas-Tsitsiklis book~\cite[Exer. 2.19]{BT97}.} 887c908 < Then every basic feasible solution, BFS, $x\in \cF$ with basis $\cB$ --- > Then every basic feasible solution, \BFSp, $x\in \cF$ with basis $\cB$ 909c930 < $\bullet$ BFS implies $\rank A(:,\cB)=m$; implies $\exists i\in\cB, i>r$ --- > $\bullet$ \BFS implies $\rank A(:,\cB)=m$; implies $\exists i\in\cB, i>r$ 920c941 < \begin{corollary}[contrapositive motivates phase I part 2] --- > \begin{corollary}[motivates phase I part 2] 928,929c949 < \begin{example}[converse fails; all BFS degenerate $\notimplies$ MFCQ < fails] --- > \begin{example}[converse fails] 948,969d967 < \frametitle{Empirics for \FR Preprocessing} < < \begin{block}{We want to {\crr avoid implicit singularity}} < $\bullet$ improve conditioning, number of iterations < \end{block} < < < \begin{block}{interior point methods} < $\bullet$ Condition number of {\crr normal equation system} < \\$\bullet$ stopping criteria < \[ < \text{KKT} = \left( \frac{\|Ax^*-b\|}{1+ \|b\|}, \ \frac{\|A^T y^*+s^*-c\|}{1+ \|c\|} , \ \frac{\}{n} \right) . < \] < < \end{block} < \begin{block}{simplex methods (NETLIB data set)} < $\bullet$ percentage of {\crr degenerate iterations} < \end{block} < < < \end{frame} < \begin{frame} 1046c1044,1045 < %\includegraphics[height=5.5cm]{condnumplotPerformanceProfile.eps} --- > %\includegraphics[height=6cm]{condnumplot.eps} > \includegraphics[height=5.5cm]{condnumplotPerformanceProfile.eps} 1301c1300 < {\crr smaller value $(r/n)\%$} --- > smaller value $(r/n)\%$ 1329c1328 < 60\% & 70\% & 80\% & 90\% & 100\% --- > 60 & 70 & 80 & 90 & 100 1337c1336 < \caption{Average of ratio of degenerate iterations {\crr DEGITER($\%$)}} --- > \caption{Average of the ratio of degenerate iterations} 1351c1350 < $\bar x,\cB$ degenerate BFS/basis; --- > $\bar x,\cB$ degenerate \BFSp/basis; 1386,1387c1385,1386 < loss of strict feasibility has {\crr many applications} < recent survey Drusvyatskiy-W.\cite{DrusWolk:16}. --- > The loss of strict feasibility arises in many applications in > convex optimization, e.g.,recent survey Drusvyatskiy-W.\cite{DrusWolk:16}. 1389,1390c1388,1392 < though not needed theoretically in \LPp, < loss of MFCQ results in stability/numerical issues. --- > Strict feasibility is not needed theoretically in linear programming, > however, we have shown that loss of strict feasibility results in > stability/numerical issues. \LPp. > In fact, loss of strict feasibility implies that \underline{every} BFS > is degenerate. 1392,1396c1394,1396 < 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. --- > In the paper, we have introduced a new concept of singularity degree related to > stability of problems. It uses the notion of Implicit > Singularity Degree and the \underline{max}imum number of \FR steps. 1398,1402c1398,1399 < Final Theorem: it is {\crr `dangerous-but-fun'} to work on {\crr \LPp}: < \\$\bullet$ INFORMS talk: contrapositive in < B-T book~\cite[Exer. 2.19]{BT97}; < \\$\bullet$ this talk, yesterday email from Coralia Cartis: < C. with Gould \cite{CartisGould:09}; C. with Yan \cite{MR3465452}. --- > We have presented an algorithm, phase I (b), that regularizes an \LPp, > i.e.,~results in strict feasibility holding.