\documentclass[11pt]{article}
\input{../../preamble}
\usepackage{amsmath, latexsym}
\begin{document}
\problemset{4}{September 19, 2014}{4}{September 26, 2014}
\begin{enumerate}
\item In class we showed that given a polytope $Q = conv(v_1,\ldots,v_k)$, if 0 is in the interior of $Q$, then $Q$ is a bounded polyhedron.
Now suppose that we only know that there is some point $v$ in the interior of $Q$. Show that $Q$ is bounded polyhedron. (Hint: Think about $Q-v = \{w-v: w \in Q\}$).
\item Consider the set $P=\{x: A x \ge 0\}$ and assume that we have $x \ge 0$
for all $x \in P$, i.e., that $x \ge 0$ is implied by $ A x \ge 0$.
\begin{enumerate}
\item A set $K$ is a cone if $x,y\in K$ implies that $\lambda x + \mu y \in K$
for all $\mu, \lambda \ge 0$. Prove that $P$ is a cone.
\item An {\em extreme ray} of a cone $K$ is a nonzero vector $x \in K$ such
that $x+y \in K$ and $x-y \in K$ implies that $y=\lambda x$ for some
$\lambda$.
Give another characterization of the extreme rays of the polyhedral cone $P$,
using the rank of a submatrix of $A$. (Hint: think about the positive orthant
as the canonical example of a cone, in order to get some intuition here.)
\item Two extreme rays $x$ and $y$ of a cone $K$ are said to be the same if
$x=\lambda y$ for some $\lambda >0$. Prove that the number of different
extreme rays of our polyhedral cone $P$ is finite. Give a finite bound on
the maximum number of extreme rays possible assuming that $A$ is has $m$ rows
and $n$ columns.
\item Let $r^1$, \ldots, $r^k$ denote the finite set of extreme rays of
$P$. Let
$$Q= cone(r^1,\ldots,r^k)=
\{x=\sum_i \lambda_i r^i: \lambda_i \ge 0 \mbox{ for all $i$}\}.
$$
Prove that $P=Q$. (Hint: consider $P'=\{x \in P: \sum x_i=1\}$. )
It might help to visualize this as moving from the description of
$P$ by the faces of the cone that bound it ($Ax \ge 0$) to a
description of $P$ by the outside rays ($r^1, \ldots, r^k$) that
bound it.
\end{enumerate}
\item Fun with polars.
\begin{enumerate}
\item Given a convex cone $K \subseteq \Re^n$, prove that the polar of
$K$ is the set $\{z \in \Re^n: x^Tz \leq 0 \mbox{ for all } x \in
K\}$.
\item Give the polar of the non-negative orthant $\{x \in \Re^n: x
\geq 0\}$.
\item Show that if $A \subseteq B$, then $B^\circ \subseteq A^\circ$.
\end{enumerate}
\end{enumerate}
\end{document}