\documentclass{article}
\usepackage{amsmath, amsthm, amssymb}
\usepackage{graphicx}
\usepackage{clrscode}

\author{Nada Amin\\
\texttt{namin@mit.edu}
}
\date{October 17, 2007}

\title{6.854 Problem Set 6}

\begin{document}
\pagestyle{myheadings}
%\markright{Nada Amin (6.854 Problem Set 6) (10/17/07)}

%\maketitle

%\section*{Collaborators}
%\begin{itemize}
%\item Thomas Belulovich (\texttt{thobel@mit.edu})
%\item Thomas Mildorf (\texttt{tmildorf@mit.edu})
%\end{itemize}

\pagebreak

\section*{Problem 1}
\markright{Nada Amin (6.854 Problem 6-1) (10/17/07)} 

\subsection*{Part (a)}

I argue that at any vertex $M$ of the polytope, at least $m - 2n + 1$
of the $x_{ij}$ must be equal to $0$.

Since a vertex is a basic feasible solution, I know that at any
vertex, (i) all equalities are tight and (ii) $m$ linearly independent
constraints are tight. There are $2n$ equalities, but only $2n-1$ of
them are independent, because $\sum_i \sum_{j \in N(i)} x_{ij} =
\sum_j \sum_{i \in N(j)} x_{ij}$. So that leaves $m-2n+1$ tight
inequalities (of the form $x_{ij} \geq 0$). Hence, $m-2n+1$ of the
$x_{ij}$ are 0.

\subsection*{Part (b)}
In $M$, there are potentially $m$ nonzero entries ($x_{ij}$), one for
each edge $ij$. Because of the equality constraint, each row must have
at least one nonzero entry. Suppose that each row has at least $2$
nonzero entries, for a total of at least $2n$ nonzero entries. Then,
there can be at most $m-2n$ zero entries. This contradicts part (a),
in which I showed that at least $m-2n+1$ of the entries are $0$. So at
least one row of $M$ must contain a single nonzero entry. Because of
the equality constraint on this row, this nonzero entry must be $1$
with all other entries $0$. Because of the equality constraint on the
column of this single nonzero entry, all other entries in that column
must be $0$.

\subsection*{Part (c)}
Let the single entry of value $1$ from part (b) be $x_{ij}$, so that
it involves row $i$ and column $j$. Let $M'$ be the matrix obtained by
deleting row $i$ and column $j$. The sum of each remaining row and
column of $M'$ is still $1$, because only zero entries have been
deleted from these rows and columns. Therefore, $M'$ is doubly
stochastic. Suppose I loose $k$ variables when going from $M$ to
$M'$. I lost two equality constraints and $k-1$ tight inequality
constraints, only $k-2$ of which are independent (since I can
determine one entry by the sum constraint from part (a)). Therefore, I
loose as many constraints as I loose variables, so that $M'$ is still
a vertex of the resulting LP. Hence, $M'$ satisfies part (b), so it
has at least one row / column containing a single $1$ with all other
entries $0$, and it can be reduced further. When $n = 1$, the matrix
has a single entry with $1$. I have thus shown that any vertex $M$ is
an integer doubly stochastic matrix (i.e. a perfect matching). Because
any feasible point of the polytope is a convex combination of
vertices, any solution is a convex combination of perfect matchings.

Let $\lambda$ be the maximum of (i) the largest rate at which packets
arrive on an input line and (ii) the maximum rate at which packets
want to depart from an output line. By the result above, the switch
can decompose any demand into a convex combination of matchings, in
which the sum of the weights of the matchings is $\leq \lambda$. So as
long as the switch can deliver matchings at rate $\lambda$, it can
deliver the specified traffic.

\pagebreak

\section*{Problem 2}
\markright{Nada Amin (6.854 Problem 6-2) (10/17/07)}

Farkas' lemma states that {\it exactly one} of the following two systems has a solution:
\begin{enumerate}
\item $Ax = b$ and $x \geq 0$
\item $yA \geq 0$ but $yb < 0$
\end{enumerate}

In this problem, I prove Farkas' lemma.

\subsection*{Part (a)}
I give a direct proof that the two systems cannot both be feasible, by
showing that if 1 is feasible then 2 is unfeasible.

Suppose 1 is feasible, so $Ax = b$ and $x \geq 0$. Suppose that $yA
\geq 0$. Then $yb = y(Ax) = (yA)x \geq 0$ since $yA \geq 0$ and $x
\geq 0$. So 1 is feasible implies that 2 is unfeasible.

\subsection*{Part (b)}
I shows that the linear program $\min yb \ | \ yA \geq 0$ can only have
two possible answers: $0$ and $-\infty$.

First, notice that the linear program has the trivial solution $y =
0$, which gives $yb = 0$. So the minimum $yb \leq 0$.

Suppose $\neg\exists y$, s.t. $yb < 0$ and $yA \geq 0$. So the minimum
is $yb = 0$.

Suppose $\exists y$, s.t. $yb < 0$ and $yA \geq 0$. Then, I can
multipliy $y$ by some $\lambda > 0$, $y' = \lambda y$. Then, $y'b <
yb$ and $y'A > yA$. So $y'$ satisfies the linear program constraint
and gives a smaller $y'b$. With $\lambda \rightarrow \infty$,
$y'b = \lambda yb \rightarrow -\infty$. So the minimum is $-\infty$.

\subsection*{Part (c)}
I show that if 1 is unfeasible, then 2 is feasible. Combined with part
(a), this proves Farkas' lemma.

Consider the dual of $\min yb \ | \ yA \geq 0$: $\max 0x \ | \ Ax = b,
x \geq 0$.  If 1 is unfeasible, then the dual is unfeasible. If the
dual is unfeasible, by strong duality, the primal is either unfeasible
or unbounded. By part (b), the primal cannot be unfeasible. Therefore
it is unbounded. Therefore, $\exists y$, s.t. $yA \geq 0$ but $yb <
0$, i.e. 2 is feasible. So 1 is unfeasible implies that 2 is feasible.

\pagebreak

\section*{Problem 3}
\markright{Nada Amin (6.854 Problem 6-3) (10/17/07)} 

I suppose I am given two polyhedra $P = \{ x | Ax \leq b \}$ and $Q = \{ x | Dx \leq e \}$.

\subsection*{Part (a)}
Using duality, I prove that if polyhedra $P$ and $Q$ have empty
intersections, then there are $y, z \geq 0$ s.t. $yA + zD = 0$ but $yb
+ ze < 0$.

Consider $R = \{ x | Ax \leq b, Dx \leq e \}$. If $R = \emptyset$,
then the linear program $\max 0x \ | \ x \in R$ is unfeasible. Its
primal counterpart, $\min yb + ez \ | \ yA + zD = 0, y \geq 0, z \geq
0$, is either unbounded or unfeasible. However, the primal is clearly
not unfeasible since $y=z=0$ is a solution. So it must be
unbounded. Thus, $\exists y, z \geq 0$ s.t. $yA + zD = 0$ but $yb + ze
< 0$.

\subsection*{Part (b)}
I conclude that if polyhedra $P$ and $Q$ have empty intersections,
then there is a separating hyperplane for $P$ and $Q$ (i.e., a vector
$c$ s.t. $cx < cw$ for all $x \in P$ and $w \in Q$).

By part (a), if $P$ and $Q$ have empty intersections, $\exists y, z
\geq 0$ s.t. $yA + zD = 0$ but $yb + ze < 0$.  Consider $c = yA$.
Then, for $x \in P$, $cx = yAx \leq yb$ since $Ax \leq b$. So for $x \in
P$, $cx \leq yb$.  Similarly, for $w \in Q$, $cw = yAw = -zDw$, using
$yA + zD = 0$. Since $Dw \leq e$, $cw = -zDw \geq - ze$. So for $w \in
Q$, $- cw \leq ze$.  Adding the inequalities, $cx - cw \leq yb + ze <
0$. So for $x \in P$ and $w \in Q$, $cx < cw$. In other words, there is
a separating plane between P and Q.

\subsection*{Part (c)}
I conclude that given two polyhedra $P$ and $Q$, there is a quickly verifiable
answer as to whether or not the two polyhedra have a point in common.

If the two polyhedra have a point $x$ in common, simply give the point
$x$. It is easy to verify that $x \in P$ by checking $Ax \leq b$ and
that $x \in Q$ by checking $Dx \leq e$.

If the two polyhedra have no point in common, simply give $y$ and $z$,
s.t., $y \geq 0$, $z \geq 0$, $yA + zD = 0$ but $yb + ze < 0$ (these
constraints are all easily verifiable). By part (a), if the two
polyhedra have no point in common, then there exists such a $y$ and
$z$. By part (b), if such a $y$ and $z$ exists, there is a separating
plane between the two polyhedra, so they have no point in common.

\pagebreak

\section*{Problem 4}
\markright{Nada Amin (6.854 Problem 6-4) (10/17/07)}

I argue that weak duality holds for an arbitrary linear program, with
its dual taken by the cookbook method.

Let $A$ be a matrix with rows $a_i'$ and columns $A_j$. 

The arbitrary primal linear program is: minimize $c'x$, subject to
\begin{align*}
a_i'x \geq b_i,\ &  i \in M_1\\
a_i'x \leq b_i,\ &  i \in M_2\\
a_i'x = b_i,\ &     i \in M_3\\
x_j \geq 0,\ &      j \in N_1\\
x_j \leq 0,\ &      j \in N_2\\
x_j \text{ free},\ &j \in N_3
\end{align*}

The dual linear program is: maximize $y'b$, subject to
\begin{align*}
y_i \geq 0,\ &      i \in M_1\\
y_i \leq 0,\ &      i \in M_2\\
y_i \text{ free},\ &i \in M_3\\
y'A_j \leq c_j,\ &  j \in N_1\\
y'A_j \geq c_j,\ &  j \in N_2\\
y'A_j = c_j,\ &     j \in N_3
\end{align*}

\

\begin{center}
\begin{tabular}{|c|c||c|c|}
\hline PRIMAL      & minimize   & maximize   & DUAL\\
\hline      & $\geq b_i$ & $\geq 0$   &            \\
constraints & $\leq b_i$ & $\leq 0$   & variables  \\
            & $= b_i$    & free       &            \\
\hline      & $\geq 0$   & $\leq c_j$ &            \\
variables   & $\leq 0$   & $\geq c_j$ & constraints\\
            & free       & $= c_j$    &            \\
\hline
\end{tabular}
\end{center}

\

Let $x$ and $y$ be vectors for the primal and dual feasible. Define,
\begin{align*}
u_i = y_i (a_i'x - b_i)\\
v_j = (c_j - y'A_j) x_j
\end{align*}

The definition of the dual requires that the sign of $y_i$ equals the
sign of $a_i'x - b_i$ and that the sign of $c_j - y'A_j$ equals the
sign of $x_j$. Thus, the primal and dual feasibility imply that:
\begin{align*}
u_i \geq 0,\ \forall i\\
v_j \geq 0,\ \forall j\\
\end{align*}

Notice: 
\begin{align*}
\sum_i u_i = y'Ax - y'b\\
\sum_j v_j = c'x - y'Ax
\end{align*}

Adding these two equalities and using non-negativity of $u_i, v_j$:
$$0 \leq \sum_i u_i + \sum_j v_j = c'x - y'b$$

Thus $yb \leq cx$ or OPT(dual) $\leq$ OPT(primal). So I have just
shown that weak duality holds for an arbitrary linear program.

\pagebreak

\section*{Problem 5}
\markright{Nada Amin (6.854 Problem 6-5) (10/17/07)} 
I consider this linear program formulation of the max-flow problem as the dual:
\begin{align*}
z = \max\sum f_P\\
\sum_{P \ni e} f_P \leq u_e\\
f_P \geq 0
\end{align*}

I derive the primal of the dual using the cookbook method:
\begin{align*}
z = \min\sum u_e x_e\\
\sum_{e \in P} x_e \geq 1\\
x_e \geq 0
\end{align*}

I interpret the variable $x_e$ as representing the saturation of an
edge ($0$ for unsaturated, $1$ for saturated, though the linear
program allows arbitrary non-negative values). Using this interpretation, an
English explanation of the objective and constraints is: minimize
the sum of the capacities of saturated edges subject to the constraint
that there is at least one saturated edge per path.

Still in other words, using network flow concepts, the linear program
is looking for the $s$-$t$ cut of minimum value: the objective
function defines the value of an $s$-$t$ cut as the sum of the
capacities of cross-cut edges and the constraints require that, in an
$s$-$t$ cut, at least one edge in each $s$-$t$ path is across the
cut. In this interpretation, $x_e$ is $1$ for cross-cut edges and $0$
for other edges (though, again, the linear program doesn't constrain
the values to be $0$ or $1$).

\pagebreak

\section*{Problem 6}
\markright{Nada Amin (6.854 Problem 6-6) (10/17/07)} 

\subsection*{Part (a)}
I argue that any LP optimization problem can be transformed into a
problem of the form $\min 0x | Ax = b, x \leq 0$, i.e., the objective
is to minimize $0x$ and the constraint on $x$ is in standard
form. This form is only concerned with the feasibility of the LP, as
it has optimium value $0$ if it is feasible, and $\infty$ if it is
unfeasible.

Let's start with a LP optimization problem in standard form: $\min cx
| Ax = b, x \geq 0$.  Its dual is $\max yb | yA \leq c$. By strong
duality, if the problem is feasible and bounded, then $cx = yb$. So
here are the constraints on a LP program that decides whether the
optimization problem is feasible and bounded:
\begin{align*}
Ax = b\\
x \geq 0\\
yA \leq c\\
cx = yb\\
\end{align*}

I can put these constraints in standard form and use the objective $0x
+ 0y$ to end up with a problem of the required form. The program
returns $0$ if the original program is feasible and bounded and
$\infty$ if it is unfeasible or unbounded.

\subsection*{Part (b)}
The dual of the linear program $\min 0 x | Ax = b, x \leq 0$ is $\max
yb | yA \leq 0$.

\subsection*{Part (c)}
If the primal is feasible, then its solution is $0$. By strong
duality, $0$ is also the optimum of the dual. In the dual, I can
obviously get $yb = 0$ by letting $y = 0$. So if the primal is
feasible, the dual has the obvious optimum solution $y = 0$.

\subsection*{Part (d)}
Given an algorithm that could optimize an LP with an $m \times n$
constraint matrix in $O((m+n)^k)$ time given an optimal solution to
the dual LP, I can build an LP algorithm that will solve any LP
without knowing a dual solution, in the same asymptotic time bounds. I
assume that, if given a wrong optimal solution to the dual, the given
algorithm might not return a correct answer, but will stop
nevertheless (I can always stop it after it runs for more than
$c(m+n)^k$ steps where $c$ is the constant in its running time).

I call the algorithm on the same LP with the objective function
modified to $0$ and use an obvious dual solution similar to that of
part (b). If the algorithm returns with a feasible solution, then I
know that the LP is feasible. Otheriwse, it is unfeasible.

If the LP is feasible, I transform the LP into the form of part (a),
call it LP'. I call the algorithm on LP' using the obvious optimum
solution $y = 0$ for the dual. If LP' is feasible, the algorithm
should return an $x$ that satisfies the constraints of LP'. If it
doesn't, I can assume LP' is unfeasible, which means that the original
LP is unbounded (since I know it is feasible). If the LP is feasible
and bounded, I can easily transform the solution of LP' into a
solution to the original LP.

The asymptotic time bounds remain $O((m+n)^k)$ because, LP' has a
$O(m+n)\times O(m+n)$ constraint matrix. Transforming the LP' solution
back into LP is straightforward, as it just involves reading the
variables of interest.

\end{document}
