\documentclass[11pt]{article}
\input{../../preamble}
\usepackage{amsmath, latexsym}
\begin{document}
\problemset{10}{November 7, 2014}{10}{November 14, 2014}
\begin{enumerate}
\item (10 points) The ellipsoid method proves that for linear programming, if we have a
polynomial-time separation oracle then we can also solve the linear program in polynomial time. Prove that
this statement is if and only if. More precisely, assume that if you are
given a (possibly very large) set of inequalities $Ax \le b$, and you have a
method to solve $\max(cx: Ax \le b)$ for any objective function $c$ whose
running time is polynomial in the dimension of the vector $x$ (and is
independent of the number of rows of $A$. )
Design a method that separates from $\{x: Ax \le b\}$, i.e., given a vector
$x$, your method should either conclude that $Ax \le b$ or it must find a
hyperplane separating $x$ from the feasible region. If it helps to restrict
the class of linear programs (non-degeneracy, full rank, whatever, ...)
feel free to do so.(Hint: Think about the polar region:
$P^*=\{z: z^T x \le 1 \mbox{ for all } x \mbox{ s.t. } Ax \le b\}$).
\item The standard simplex in $\Re^m$ is the set $S_m \equiv \{ x \in \Re^m: e^T x \leq 1, x \geq 0\}$ where $e \in \Re^m$ is the vector of all ones.
\begin{enumerate}
\item (5 points) Consider the simplex $\{x \in \Re^m: a^T x \leq 1, x \geq 0\}$ where $a \in \Re^m$ is a positive vector. Show that there is a nonsingular linear transformation taking this simplex into $S_m$.
\item (8 points) Consider the hyperplane $\{x \in \Re^m: e^T x = m/(m+1)\}$ through the centroid $\hat{x} \equiv e/(m+1)$ of $S_m$. Show that this hyperplane cuts the simplex into two pieces, with the piece containing the origin having volume $\left(\frac{m}{m+1}\right)^m$ times that of $S_m$. Show that this factor is at most $e^{-1/2}$.
\end{enumerate}
\end{enumerate}
\end{document}