\documentclass[11pt,epsf]{article}
\parindent 0in
\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{epsfig}

\newcommand{\handout}[5]{
   \noindent
   \begin{center}
   \framebox{
      \vbox{
    \hbox to 5.78in { {\bf 18.409 The Behavior of Algorithms in Practice} \hfill #2 }
       \vspace{4mm}
       \hbox to 5.78in { {\Large \hfill #5  \hfill} }
       \vspace{2mm}
       \hbox to 5.78in { {\it #3 \hfill #4} }
      }
   }
   \end{center}
   \vspace*{4mm}
}

\newcommand{\lecture}[4]{\handout{#1}{#2}{Lecturer: #3}{Scribe: #4}{Lecture #1}}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{assumption}[theorem]{Assumption}
\newtheorem{conjecture}[theorem]{Conjecture}

\setlength{\topmargin}{-0.50in}
\setlength{\textheight}{8.5in}
\setlength{\oddsidemargin}{0.0in}
\setlength{\evensidemargin}{-0.0in}
\setlength{\textwidth}{6in}
\addtolength{\parskip}{2pt}
\addtolength{\itemsep}{0.1in}
\parskip 1.5ex

\renewcommand{\baselinestretch}{1.25}

%\input{/home/brian/latex/bds}

%\usepackage{amsmath}
%\newtheorem{Defn}{Definition}
%\newtheorem{Thm}{Theorem}
%\newtheorem{Conj}{Conjecture}
\newcommand{\defn}{\emph}

\newcommand{\st}{\text{s.t. }}
\DeclareMathOperator{\opt}{opt}



\begin{document}



\lecture{14}{9 Apr. 2002}{Dan Spielman}{Brian Sutton}



In this lecture, we study the worst-case complexity of the simplex
method. We conclude by stating, without proof, one of the major theorems
in the smoothed analysis of the simplex method.



\section{More common geometric view of the simplex method}

The animation that we saw in an earlier lecture is not the most common
way of viewing the simplex method geometrically. Here we give a more
common interpretation.

Start with the LP formulation
\begin{align*}
\max\; & \mathbf{c}^T \mathbf{x} \\
\st & \mathbf{a_i}^T \mathbf{x} \leq b_i.
\end{align*}
Each constraint $\mathbf{a_i}^T \mathbf{x} \leq \mathbf{b_i}$ defines
a halfspace, so the complete set of constraints defines a polytope $P$
(assuming that the LP is feasible and finite).
%or
%a cone. We will assume that the feasible set is a polytope $P$.
Solving the LP is equivalent to finding the vertex of this polytope
that lies farthest in the direction of $\mathbf{c}$.

The simplex method is
\begin{enumerate}
\item Find some vertex of $P$.
\item Move to an adjacent vertex in the direction of $\mathbf{c}$,
i.e. which improves the objective function, and iterate.
\end{enumerate}

\begin{definition}
A \defn{basic feasible solution} of an LP is a feasible $\mathbf{x}$
for which exactly $d$ constraints are tight. Equivalently $\mathbf{x}$
is a vertex of the feasible polytope.
\end{definition}
Note that this definition is equivalent to the definition given in an
earlier lecture.

\begin{observation}
If the $\mathbf{a_i}$'s and $b_i$'s
are in general position, then
\begin{enumerate}
\item No $\mathbf{x}$ satisfies $d + 1$ constraints with equality.
\item The feasible polytope $P$ is simple.
\item Exactly $d$ planes meet at any vertex.
\item Every vertex has exactly $d$ neighbors.
\end{enumerate}
One can show that under a perturbation of the $b_i$'s, the
feasible polytope is simple with high probability.
\end{observation}



\section{Worst-case complexity of the simplex method}

We will assume that $P$ is a simple polytope. Our definition of the
simplex method,
\begin{enumerate}
\item Find some vertex of $P$,
\item Move to one of the $d$ neighbors improving the objective
function, and iterate,
\end{enumerate}
is incomplete. It does not specify how to find the initial vertex, nor
how to choose the next neighbor in the sequence. Finding the initial
vertex will be addressed in a later lecture. Now we look at
\defn{pivot rules}, which specify which neighbor to choose in step (2)
of the algorithm. Chvatl's book is a good reference on pivot rules.

\subsection{Pivot rules}

\begin{enumerate}

\item Greedy: Choose the vertex giving the maximal improvement in the
objective function.

\item Bland's rule: Index the constraints. The current vertex
$\mathbf{v}$ satisfies exactly $d$ constraints with equality, i.e. it
lies at the intersection of $d$ faces of the polytope. Any adjacent
vertex $\mathbf{w}$ lies on $d - 1$ of these faces. So when moving
from $\mathbf{v}$ to $\mathbf{w}$, exactly one constraint is loosened
from tightness. Choose $\mathbf{w}$ so that the constraint that is
loosened has least index.

\item Dantzig's largest coefficient: Similar to Bland's.

\item Steepest edge: Make the most progress per distance travelled.

\item Random.

\end{enumerate}

\subsection{Time complexity of deterministic pivot rules}

The simplex method with any of the above four deterministic pivot
rules takes exponential time in worst-case. There are no known
polynomial time pivot rules. We have the belief, ``Almost all
deterministic pivot rules take exponential time in the worst case.''

A powerful tool for generating polytopes that produce slow behavior
for a particular pivot rule was provided by Amenta and Ziegler.

The following question came from the audience: Is the performance bad
because the polytope has large diameter, or because the algorithm
chooses a poor path?

It seems that the polytope of an LP in $d$ dimensions with $n$
constraints has polynomial diameter in $n$ and $d$. Our best
proven result is

\begin{theorem}[Kalai-Kleitman]
The diameter of the polytope is $\leq n^{\log_2 n}$.
\end{theorem}

But we have the conjecture

\begin{conjecture}[Hirsch]
The diameter of the polytope is $\leq n - d + 1$. (Actually, the
conjecture might be $n - d - 1$. We don't remember.)
\end{conjecture}

\subsection{Time complexity of random pivot rules}

We know very little about the time complexity of random pivot
rules. We do know that there exist random pivot rules that take
$n^{O(\sqrt{d})}$ steps. This result was proved independently by Kalai and
Matou\v{s}ek-Sharir-Welzl.

\subsection{Worst-case complexity of Bland's rule}

The initial paper on constructing worst-case inputs for a pivot rule
was by Klee-Minty.

We will construct a deformed hypercube that will cause Bland's rule to
visit every vertex when started at a particular vertex.

In $d$ dimensions, a hypercube is defined by the $2d$ constraints
\begin{align*}
0 &\leq x_1 \leq 1 \\
0 &\leq x_2 \leq 1 \\
& \dots \\
0 &\leq x_i \leq 1 \\
& \dots
\end{align*}

Our feasible set is
%\begin{align*}
%\max \; & x_d \\
%\st & \\
\[
P :=
\begin{array}{r c c c l}
0 &\leq& x_1 &\leq& 1 \\
\varepsilon x_1 &\leq& x_2 &\leq& 1 - \varepsilon x_i \\
& & \dots & & \\
\varepsilon x_{i-1} &\leq& x_i &\leq& 1 - \varepsilon x_{i-1} \\
& & \dots, & &
\end{array}
%0 &\leq x_1 &\leq 1 &\\
%& \varepsilon x_1 &\leq x_2 &\leq 1 - \varepsilon x_i &\\
%& & \dots & &\\
%%& \varepsilon x_{i-1} &\leq x_i &\leq 1 - \varepsilon x_{i-1} &\\
%& & \dots, & &
%\end{align*}
\]
with $\varepsilon = 1/3$. We will index the constraints as follows:
\[
\begin{array}{r c c c l}
0 &\overset{1}{\leq}& x_1 &\overset{2}{\leq}& 1 \\
&& \dots && \\
\varepsilon x_{i-1} &\overset{2i - 1}{\leq}& x_i &\overset{2i}{\leq}& 1 -
\varepsilon x_{i-1} \\
&& \dots &&
\end{array}
\]

\textbf{Claim:} $\mathbf{x}$ is a vertex of $P$ if and only if
inequality $2i - 1$ or $2i$ is tight for each $i$.
%Making one inequality from each pair $(2i - 1, 2i)$
%tight for every $i$ produces a vertex. Further, every vertex can be
%constructed this way.
To prove the claim, observe that it is impossible to satisfy
inequalities $2i - 1$ and $2i$ simultaneously. Thus,
in order to make $d$ inequalities tight, we must choose one inequality
from each pair.

\begin{theorem}
Bland's rule visits every vertex of $P$ when solving
\begin{enumerate}
\item $\max x_d \; \st \mathbf{x} \in P$ if started at $(0,0,\dots,0)$.
\item $\min x_d \; \st \mathbf{x} \in P$ if started at $(0,\dots,0,1)$.
\end{enumerate}
\end{theorem}
\begin{proof}
The proof is by induction. Assume that the theorem is true for $d - 1$
dimensions. We will prove part (1) of the theorem. The proof of part
(2) is very similar.

The walk around the polytope begins with a sequence of points
satisfying $x_d = \varepsilon x_{d-1}$. Because Bland's rule will not
loosen this equality until it is impossible to loosen any equality of
lower index (without decreasing the objective function), the walk
starts by maximizing $x_{d-1}$ over the polytope in $d - 1$ dimensions
that is the projection of $P$ to coordinates $x_1, \dots,
x_{d-1}$. Thus, by induction (part (1)), the walk visits every vertex
of $P$ satisfying $x_d = \varepsilon x_{d-1}$.
% visits every vertex of the polytope in $d - 1$
%dimensions that is the projection of $P$ to coordinates $x_1, \dots,
%x_{d-1}$.

The next step is to $(0,0,\dots,0,1,1-\varepsilon)$. Now, $x_d$ gets
larger as $x_{d-1}$ gets smaller, so that the walk visits every vertex
satisfying $x_d = 1 - \varepsilon x_{d-1}$ by induction (part (2)).
\end{proof}

\subsection{Pivot rules under perturbation}

There are two types of perturbations one might consider:

\begin{enumerate}

\item Absolute perturbations: Write the feasible set as $A\mathbf{x}
\leq \mathbf{b}$, and suppose $A$ is subject to absolute
perturbations. This model seems strange, since $A$ can be so
sparse. (In our worst-case instance for Bland's rule, $A$ contained
only one nonzero entry in any row.)

\item Zero-preserving perturbations: Our proof for the exponential
running time of Bland's rule holds up under zero-preserving
perturbations. What about problem instances for the greedy pivot rule?
The first worst-case instance, provided by Jeroslow, does not hold up
under perturbation. It is not known whether the instance provided by
Amenta and Ziegler holds up under perturbation.

\end{enumerate}



\section{Smoothed analysis of the simplex method}



Our smoothed analysis of the simplex method will take advantage of
some nice properties of the shadow-vertex pivot rule.



\subsection{Definition of the shadow-vertex pivot rule}

%The shadow-vertex pivot rule is particularly nice for analysis. Its
The inspiration for this rule comes from the fact that linear
programming is easy in two dimensions. The idea is to project the
feasible polytope to a convex polygon, i.e. ``take a shadow,'' that
satisfies
\begin{enumerate}
\item The optimal vertex maps to the exterior,
\item The start vertex maps to the exterior,
\end{enumerate}
and then optimize over the shadow.  To construct such a shadow, find a
linear function $\mathbf{t}$ that is optimized by the current vertex
and map each vertex $\mathbf{v}$ of the polytope to $(\left<
\mathbf{v}, \mathbf{c} \right>, \left< \mathbf{v}, \mathbf{t}
\right>)$.

\textbf{Claim:} If a vertex $\mathbf{v}$ of the polytope projects to
the exterior of the shadow, then one can compute which neighbor of
$\mathbf{v}$ will be visited next on the shadow.

Thus, algorithmically, the shadow-vertex pivot rule is reasonable. The
rule's major analytical advantage is the fact that we
can succinctly describe the vertices that are visited as follows. Let
$\opt_\mathbf{z}(A, \mathbf{b})$ denote the vertex optimizing
$\mathbf{z}^T\mathbf{x} \; \st A \mathbf{x} \leq \mathbf{b}$. Then the
vertices encountered when optimizing $\mathbf{c}$ are
\[ \bigcup_{0 \leq \lambda \leq 1} \opt_{(1-\lambda)\mathbf{t} + \lambda \mathbf{c}} (A,
\mathbf{b}). \]




\subsection{Worst-case complexity of the shadow-vertex pivot rule}

The shadow-vertex pivot rule has exponential worst-case
complexity. The following instance induces exponential running time:
\[
\begin{array}{r c c c l}
0 &\leq& x_1 &\leq& 1 \\
\varepsilon x_1 &\leq& x_2 &\leq& 1 - \varepsilon x_i \\
& & \dots & & \\
\varepsilon (x_{i-1} - \gamma x_{i-2}) &\leq& x_i &\leq& 1 -
\varepsilon (x_{i-1} - \gamma x_{i-2}) \\
& & \dots, & &
\end{array}
\]
where $\varepsilon = 1/3$ and $\gamma = 1/12$.



\subsection{Smoothed analysis of the shadow-vertex pivot rule}

We will prove the following theorem in upcoming lectures.

\begin{theorem}
Let $\mathbf{t}$ and $\mathbf{c}$ be arbitrary vectors, $b_i \in \{1,
-1\}$, and $\mathbf{\hat{a}_1}, \dots, \mathbf{\hat{a}_n}$
vectors of norm at most 1. If $\mathbf{a_1}, \dots, \mathbf{a_n}$ are
Gaussian random vectors of variance $\sigma^2$ centered at
$\mathbf{\hat{a}_i}$, then
\[ E\left[\left| \bigcup_{0 \leq \lambda \leq 1}
\opt_{(1-\lambda)\mathbf{t} + \lambda\mathbf{c}} (\mathbf{a_1}, \dots,
\mathbf{a_n}, b_1, \dots, b_n) \right| \right] \leq \text{poly}(n, d,
\frac{1}{\sigma}). \]
\end{theorem}

It is an open problem to prove a similar result for perturbations that
preserve feasibility (or unfeasibility).



\end{document}

