\documentclass[11pt]{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}

\newcommand{\norm}[1]{\|#1\|}
\newcommand{\infnorm}[1]{\norm{#1}_\infty}
\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}

\newcommand{\qed}{\ensuremath{\blacksquare}}
\newenvironment{proof}{\noindent{\bf Proof}\hspace*{1em}}{\qed\bigskip}


\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{13}{4/2/2002}{Dan Spielman}{Nitin Thaper}
In today's class, we will:

\begin{itemize}
\item Analyze von Neumann's algorithm in terms of the condition number [this work is due to
Dantzig and Eppelman-Freund]
\item Do a smoothed analysis of the condition number
\end{itemize}

\section{von Neumann's Linear Programming Algorithm}
We consider the following formulation of linear programming: \\
Given $c,a_1,a_2,\ldots,a_n \in \Re^d$ \\
Is $c \in hull\{a_1,a_2,\ldots,a_n\}$ ? \\
In other words, does there exist $x_1,x_2,\ldots,x_n$ such that:
$$ \sum a_i x_i = c $$
$$ \sum x_i = 1 $$
$$ x_i \ge 0 $$

We would like to find either an $x$ s.t $ \norm{c - \sum a_i x_i} < \epsilon $ if
the linear program is feasible or find a hyperplane separating $c $ from $a_1,a_2,
\ldots,a_n$ if it is not.\\
For technical reasons, we'll assume that the origin lies within the hull.\\

Recall von Neumann's algorithm for this program. 

\begin{enumerate}
\item Let $y = Ax$
\item Choose $i$ maximizing $\langle c-y,a_i-y\rangle$
\item If $\langle c-y,a_i-y \rangle /\norm{c - y} < \norm{c-y}$ then return infeasible
\item Otherwise set $x'$ s.t. $y' = Ax'$ is the point on the line $\overline{ya}_i$ closest to $c$. Repeat.
\end{enumerate}

The correctness of the algorithm derives from the following: \\
{\bf Claim:}
If $y,c \in hull\{a_1,a_2,\ldots,a_n\}$  then $\exists i\,$ s.t. 
$$\langle \frac{c-y}{\norm{c-y}},a_i-y \rangle \ge \norm{c-y}$$


\section{Analysis of the algorithm}
Let $r = $dist($c$,bdry(ch$\{a_1,a_2,\ldots,a_n\}$)) 

Let $R = \max_i \norm{a_i}$ 

\begin{theorem}[Eppelman-Freund]  \mbox{} \\
(I) If the linear program is feasible, the algorithm finds $x$ s.t. $\norm{Ax - c} \le \epsilon$
in at most $8 (R/r)^2 ln(2R/\epsilon)$ iterations. \\
(II) If infeasible, the algorithm discovers this in at most $4 (R/r)^2$ iterations.
\end{theorem}

\begin{proof} 
\mbox{} \\
\underline{Part (I)} \\
{\bf Claim:}
If the linear program is feasible then 
$$ \norm{Ax' - c} \le \norm{Ax - c} \sqrt{1 - (\frac{r}{2R})^2} $$

Before proving this claim, let's see why it implies (I). Observe that
$$\sqrt{1 - (\frac{r}{2R})^2} \le \sqrt{e^{-(r/2R)^2}} $$
Initially,
$$ \norm{Ax_0 - c} \le 2R $$
Therefore after $k$ iterations,
$$ \norm{Ax_k - c} \le 2R \sqrt{e^{-k(r/2R)^2}} $$
If we let $ 2R \sqrt{e^{-k(r/2R)^2}} < \epsilon $ we get (I).

{\bf Proof of claim}
\begin{figure}[h]
\centerline{\psfig{figure=fig1.eps,height=4.6in}}
\caption{Getting a bound on $dist(c,y')$}
\end{figure}


>From Fig 1. it is clear that,
$$ \mbox{dist}(c,y') \le \mbox{dist}(c,y^{\perp}) $$

By similarity of triangles,
$$ \frac{\mbox{dist}(c,y^{\perp})}{\mbox{dist}(c,y)} = \frac{h'}{h} $$

Therefore,
\begin{eqnarray*}
\frac{dist(c,y')}{dist(c,y)} & \le & \frac{h'}{h} \\
& = & \frac{\sqrt{l^2 - h^2}}{l} \\
& = & \sqrt{1 - (h/l)^2} 
\end{eqnarray*}

Since, $h \ge r$ and $l \le 2R$, it follows that
$$ \frac{dist(c,y')}{dist(c,y)}  \le  \sqrt{1 - (\frac{r}{2R})^2} $$


\underline{Part (II)} \\
{\bf Claim (Dantzig)}
After $k$ iterations,
$$\norm{Ax - c} \le \frac{2R}{\sqrt{k}}$$


Again it's not hard to show why this implies (II). Since point $y$ cannot go outside the
convex hull, the algorithm will stop once 
$$ \frac{2R}{\sqrt{k}} \le r$$
So the algorithm must terminate after $(2R/r)^2$ iterations.

{\bf Proof of claim}\\
Let $h_k$ be the height (i.e., distance between $c$ and $y$) after $k^{th}$ iteration.
As in the previous case, we can show that, 
$$h_{k+1} \le h_k \sqrt{1 - (h_k/2R)^2}$$

We claim that 
$$h_k \le 2R/\sqrt{k}$$


Proof by induction: \\
Note that $\norm{c} \le R$ since otherwise it would be trivial to decide infeasibility. \\
Therefore, $h_1 \le 2R$ \\
Let $h_k \le 2R/\sqrt{k}$ \\
Then 
\begin{eqnarray*}
h_{k+1} & \le & h_k\sqrt{1-(h_k/2R)^2} \\
 & = & 2R/\sqrt{k}\sqrt{1-1/k} \\
 & = & 2R\sqrt{\frac{k-1}{k^2}} \\
 & \le & 2R/\sqrt{k+1} 
\end{eqnarray*}
\end{proof}

\section{Condition number of a linear program}
Given a linear program, $c,a_1,a_2,\ldots,a_n$, we define it's condition number, $K$, as follows:

If $c \in hull\{a_1,a_2,\ldots,a_n\}$, \\
$K(c,a_1,a_2,\ldots,a_n) = inf\{\norm{\Delta c}+\sum_i\norm{a_i}: 
c+\Delta c \notin hull\{a_1+\Delta a_1,a_2 + \Delta a_2, \ldots,a_n + \Delta a_n\}\}$ 

In other words, $K$ measures the smallest change to infeasibility.
Similarly, 

If $c \notin hull\{a_1,a_2,\ldots,a_n\}$, \\
$K(c,a_1,a_2,\ldots,a_n) = inf\{\norm{\Delta c}+\sum_i\norm{a_i}: 
c+\Delta c \in hull\{a_1+\Delta a_1,a_2 + \Delta a_2, \ldots,a_n + \Delta a_n\}\}$

\begin{claim}
%$K(c,a_1,a_2,\ldots,a_n} = inf\{\norm{\Delta c}+\sum_i\norm{a_i}: c+\Delta c \in bdry(hull(a_1+\Delta a_1,a_2 + \Delta a_2, \ldots,a_n + \Delta a_n))\}$
$K(c,a_1,a_2,\ldots,a_n) = r$
\end{claim}

It is obvious that $K(c,a_1,a_2,\ldots,a_n) \le r$

We'll try to prove $K(c,a_1,a_2,\ldots,a_n) \ge r$

\begin{lemma}
Let $C = hull\{a_1,a_2,\ldots,a_n\}, C' = hull\{a_1+\Delta a_1,a_2 + \Delta a_2, \ldots,a_n + \Delta a_n\}$
\begin{enumerate}
\item $\gamma(C,C') \le \max_i \norm{\Delta a_i}$
\item $\gamma(\bar{C},\bar{C}') \le \max_i \norm{\Delta a_i}$
\item $\gamma(bdry(C),bdry(C')) \le \max_i \norm{\Delta a_i}$
\end{enumerate}
where $\gamma(A,B) = \max_{x \in A} \min_{y \in B} dist(x,y) $
\end{lemma}

\begin{proof}
\begin{enumerate}
\item Let $x \in C$ \\
$\Rightarrow \exists \alpha_1, \alpha_2, \ldots, \alpha_n$ s.t. 
\begin{eqnarray*}
\sum \alpha_i & = & 1 \\
\alpha_i & \ge & 0 \\
x & = & \sum_i \alpha_i a_i 
\end{eqnarray*}

Let $x' = \sum \alpha_i (a_i + \Delta a_i) \in C'$. Then,
\begin{eqnarray*}
dist(x,x') & = & \norm{\sum \alpha_i \Delta a_i} \\
& \le & (\sum \alpha_i) \max_i \norm{\Delta a_i} \\
& = & \max_i \norm{\Delta a_i} 
\end{eqnarray*}

\item This is similar to 1.

\item Let $x \in bdry(C)$ \\
$\exists x_1 \in C' \, s.t. \, dist(x,x_1) \le \max_i \norm{\Delta a_i} $ \\
Similarly,
$\exists x_2 \in \bar{C'} \, s.t. \, dist(x,x_2) \le \max_i \norm{\Delta a_i} $\\
Therefore, on the line from $x_1$ to $x_2$ $\exists$ a point on $bdry(C')$ with distance
from $x$ at most $\max_i \norm{\Delta a_i}$

\end{enumerate}
\end{proof}

It takes a little more work to actually use this lemma to prove the fact that $K \ge r$. 
Intuitively, what it means is that the boundary of the convex hull doesn't move much by 
changing the $a_i$'s. Therefore, it is better to just change $c$.

In the next lecture, John Dunagan will do a smoothed analysis of the condition number. In particular,
we shall prove the following theorem.

\begin{theorem}
For $c,a_1,a_2,\ldots,a_n$ Gaussian random vectors with variance $\sigma^2$ and centered at
$\bar{c},\bar{a}_1,\bar{a}_2,\ldots,\bar{a}_n$, such that each has norm $\le 1$,
$$ Pr[K(c,a_1,a_2,\ldots,a_n) < \epsilon] \le \frac{128d^{1/2}\epsilon}{\sigma} $$
\end{theorem}

This result actually follows trivially from an earlier result, but with a less intuitive
proof.
\begin{theorem}[Keith Ball '93]
For any convex body $K$, and Gaussian random vector $c$,
$$ Pr[dist(c,bdry(K)) < \epsilon] \le \frac{8d^{1/4}\epsilon}{\sigma} $$
\end{theorem}

\end{document}












