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

\newcommand{\Kappa}{\kappa}
\def\RR{{ I\!\!R}}
\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}

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

\begin{document}

\lecture{11}{March 19, 2002}{Dan Spielman}{Jos\'e Correa}

\section*{Linear Programming}

We now start with the study of smoothed analysis for linear
programming. In the forthcoming lectures we shall cover three methods for LP:
\begin{itemize}
\item[1.-] Elementary/Naive/Stupid methods (this lecture).
\item[2.-] Simplex method (part in this lecture).
\item[3.-] Interior point method.
\end{itemize}

\subsection*{Introduction}

Given $a_1,\ldots,a_n \in \RR^d$ and $c\in \RR^d$, Dan's favorite linear program
is the following
\begin{eqnarray*}
\mbox{[LP1] }\max &&\alpha\\
\mbox{s.t. }&& \alpha c \in {\rm ch}(a_1,\ldots,a_n),\\
&& \alpha\ge 0.
\end{eqnarray*}
where ${\rm ch}(a_1,\ldots,a_n)$ denotes the convex hull defined by the
vectors $a_1,\ldots,a_n$. We know that $c\in {\rm ch}(a_1,\ldots,a_n)$ if
and only if there exists $y_1,\ldots,y_n\ge 0$ such that 
$\sum_{i=1}^ny_i=1$ and $c=\sum_{i=1}^ny_ia_i$. Hence we can write [LP1] in an
equivalent form
\begin{eqnarray*}
\mbox{[LP2] }\max &&\alpha\\
\mbox{s.t. }&& \exists y_1\ldots y_n\ge0\\
&& \sum_{i=1}^ny_i=1,\, \sum_{i=1}^ny_ia_i=\alpha c.
\end{eqnarray*}
By letting $y'_i=\frac{y_i}{\alpha}$, we have that $y'_i\ge 0$, 
$\sum_{i=1}^ny'_i=\frac{1}{\alpha}$ and $c=\sum_{i=1}^ny'_ia_i$. Then, 
maximizing $\alpha$ is the same as minimizing $\sum_{i=1}^ny'_i$, and 
hence [LP2] becomes
\begin{eqnarray*}
\mbox{[LP3] }\min &&\sum_{i=1}^ny'_i\\
\mbox{s.t. }&& \sum_{i=1}^ny'_ia_i=c,\\
&& y_i'\ge 0.
\end{eqnarray*}

\subsection*{1.- Von Neumann's algorithm for LP}
We know see an elementary algorithm to solve [LP1]. The algorithm will use 
binary search on $\alpha$. And it will call a subroutine which decides 
whether a given $\alpha c$ belongs to ${\rm ch}(a_1,\ldots,a_n)$, 
this is called the {\em decision problem}.

To solve the decision problem Von Neumann's algorithm proceeds as
follows:\\[-5ex]
\begin{itemize}
\item Take $x_0\in {\rm ch}(a_1,\ldots,a_n)$, say 
$x_0=\frac{1}{n}\sum_{i=1}^n a_i$.\\[-5ex]
\item Choose $i$ maximizing $\langle(\alpha c-x_0),(a_i-x_0)\rangle$ 
($i=2$ in the figure below).\\[-5ex]
\item Find the point $x$ from $x_0$ to $a_i$ (i.e. $x\in{\rm ch}(x_0,a_i)$)
closest to $\alpha c$.\\[-5ex]
\item $x_0=x$ and repeat.\\[-5ex]
\end{itemize}

\begin{figure}[!ht]
\begin{center}
\scalebox{0.9}{\includegraphics{vonneumann.eps}}
\end{center}
\end{figure}

This procedure converges since whenever $\alpha c\in{\rm ch}(a_1,\ldots,a_n)$ we
have $\max_i\{\langle(\alpha c-x_0),(a_i-x_0)\rangle\}\ge 0$ for some $i$.
Otherwise, $\langle (\alpha c-x_0),(a_i-x_0)\rangle < 0$ for all $a_i$. This 
implies that there is an hyperplane separating $x_0$ form 
$\{a_1,\ldots,a_n\}$, from where $\alpha c \not\in{\rm ch}(a_1,\ldots,a_n)$.


\begin{theorem}[Dantzig]
Von Neumann's Algorithm obtains a point $x_0$ such that $||x_0-\alpha
c||<\epsilon$ in $$ \frac{4\max\{||\alpha c||,\max_i||a_i||\}}{\epsilon^2}$$
iterations.
\end{theorem}

\begin{theorem}[Freund-Epelman]
Von Neumann's Algorithm obtains a point $x_0$ such that $||x_0-\alpha
c||<\epsilon$ in $$ \frac{8\max\{||\alpha c||,\max_i||a_i||\}}{r^2} 
\log \left( \frac{||x_0-\alpha c||}{\epsilon}\right)$$
iterations. Where $r={\rm distance}(||\alpha c||, {\rm boundary}({\rm
ch}(a_1,\ldots a_n)))$. $r$ is a condition number of the linear program.
\end{theorem}

\subsection*{2.- The Simplex method}
Consider again the linear program [LP1]. A basic feasible solution of [LP1] is
collection of $d$ points, $B\subset \{a_1,\ldots,a_n\}$ ($|B|=d$) such that 
$\alpha c\in {\rm ch}(B)$ for some $\alpha \ge 0$.

\begin{figure}[!ht]
\begin{center}
\scalebox{0.9}{\includegraphics{simplex.eps}}
\end{center}
\end{figure}

The simplex method proceeds as follows:\\[-5ex]
\begin{itemize}
\item Find a Basic feasible solution $B$.\\[-5ex]
\item Find point, say $a$, in $\{a_1,\ldots,a_n\}$ above 
(with respect to $c$) the hyperplane ${\rm ch}(B)$.\\[-5ex]
\item Remove one point, $b$, from $B\cup\{a\}$ so that $B'=B\cup\{a\}\setminus
\{b\}$ is a basic feasible solution.\\[-5ex] 
\item $B=B\cup\{a\}\setminus\{b\}$ and repeat.\\[-5ex]
\end{itemize}

{\bf Initialization:} Plant a Basic feasible solution. i.e. put $d$ points very
close to the origin (say at distance $\epsilon$), so that they are not 
involved in an optimal solution. This is also known as the big $M$ method since, 
$\min\{\sum_{i=1}^ny_i:\,\sum_{i=1}^ny_ia_i=c,\,y_i\ge 0\}$ can be written as 
\begin{eqnarray*}
\mbox{[LP3] }\min &&\sum_{i=1}^ny_i+M\sum_{j=1}^dz_j\\
\mbox{s.t. }&& \sum_{i=1}^ny_ia_i+\sum z_je_j=c,\\
&& y_i\ge 0.
\end{eqnarray*}
Which again, by letting $M=1/\epsilon$, is equivalent to 
\begin{eqnarray*}
\mbox{[LP3] }\min &&\sum_{i=1}^ny_i+\sum_{j=1}^dz_j\\
\mbox{s.t. }&& \sum_{i=1}^ny_ia_i+\sum z_j(\epsilon e_j)=c,\\
&& y_i\ge 0,
\end{eqnarray*}
and this is exactly the initialization method described above.

{\bf Duality:} Another way of looking at Dan's linear program [LP1] is the
following. Find a plane $H$ and the minimum $\alpha$ such that, 
$\alpha c\in H$ and $\{a_1,\ldots, a_n\}$ are beneath $H$.

\begin{figure}[!ht]
\begin{center}
\scalebox{0.8}{\includegraphics{dual.eps}}
\end{center}
\end{figure}

Since $H_x=\{a:\,\langle a,x \rangle =1\}$ is the plane normal to a given 
vector $x$. The above problem, know as the {\em dual}, can be stated as 
\begin{eqnarray*}
\mbox{[Dual-LP1] }\min &&\alpha \\
\mbox{s.t. }&& \langle \alpha c,x \rangle=1\\
&&\langle a_i,x \rangle\le 1 \mbox{ for all }i.
\end{eqnarray*}
Now $\langle c,x \rangle=1/\alpha$, hence the problem is simply
\begin{eqnarray*}
\mbox{[Dual-LP3] }\max && \langle c,x \rangle\\
\mbox{s.t. }&& \langle a_i,x \rangle\le 1 \mbox{ for all }i.
\end{eqnarray*}

We can conclude the following result.
\begin{theorem}
If primal [LP1] has a solution, then the dual [Dual-LP1] has the same solution.
\end{theorem}
\end{document}