\documentclass[12pt]{article} \usepackage{amsfonts,amssymb} \usepackage{amsmath} %\documentstyle[12pt,amsfonts]{article} %\documentstyle{article} \setlength{\topmargin}{-.5in} \setlength{\oddsidemargin}{0 in} \setlength{\evensidemargin}{0 in} \setlength{\textwidth}{6.5truein} \setlength{\textheight}{8.5truein} %\input ../basicmath/basicmathmac.tex % %\input ../adgeomcs/lamacb.tex \input ../adgeomcs/mac.tex \input ../adgeomcs/mathmac.tex \def\fseq#1#2{(#1_{#2})_{#2\geq 1}} \def\fsseq#1#2#3{(#1_{#3(#2)})_{#2\geq 1}} \def\qleq{\sqsubseteq} % \begin{document} \begin{center} \fbox{{\Large\bf Spring, 2006 \hspace*{0.4cm} CIS 610}}\\ \vspace{1cm} {\Large\bf Advanced Geometric Methods in Computer Science\\ Jean Gallier \\ \vspace{0.5cm} Homework 3}\\[10pt] March 29, 2006; Due April 12, 2006\\ \end{center} ``A problems'' are for practice only, and should not be turned in. \vspace {0.5cm}\noindent {\bf Problem A1.} Give an example of a complex such that for some faces, $\sigma$, which is not a vertex, $\mathrm{lk}(\sigma)$ is properly contained in $\overline{\mathrm{st}(\sigma)} - \mathrm{st}(\sigma)$. \vspace {0.5cm} ``B problems'' must be turned in. \vspace {0.5cm}\noindent {\bf Problem B1 (20 pts).} A {\it ray\/}, $R$, of $\eucreal^d$ is any subset of the form \[ R = \{a + t u \mid t\in \reals,\> t \geq 0\}, \] for some point, $a\in \eucreal^d$ and some nonzero vector, $u\in \reals^d$. A subset, $A\subseteq \eucreal^d$, is unbounded iff it is not contained in any ball. \medskip Prove that every closed and unbounded convex set, $A\subseteq \eucreal^d$, contains a ray. \medskip\noindent {\it Hint\/}: Pick some point, $c\in A$, as the origin and consider the sphere, $S(c,r)\subseteq \eucreal^d$, of center $c$ and radius $r > 0$. As $A$ is unbounded and $c\in A$, show that \[ A_{r} = A \cap S(c, r) \not= \emptyset \] for all $r > 0$. As $A$ is closed, each $A_r$ is compact. Consider the radial projection, \\ $\mapdef{\pi_r}{S(c, r)}{S(c,1)}$, from $S(c,r)$ onto the unit sphere, $S(c, 1)$, of center $c$ given by \[ \pi_r(a) = \frac{1}{r} a. \] This map is invertible, the inverse being given by \[ \pi^{-1}_r(b) = r b, \] and clearly, $\pi$ is continuous. Thus, each set, \[ K_r = \pi_r(A_r) \] is a compact subset of $S(c, 1)$. Moreover, check that $K_{r_1} \subseteq K_{r_2}$ whenever $r_2 \leq r_1$. Deduce from this and the fact that the $K_r$ are compact that \[ \bigcap_{r > 0} K_r \not= \emptyset. \] Pick any $d\in \bigcap_{r > 0} K_r$ and prove that $\{c + t\libvecbo{c}{d} \mid t\geq 0\}$ is a ray contained in $A$. \vspace{0.5cm}\noindent {\bf Problem B2 (50 pts)}. A subset, $C\subseteq \eucreal^d$, is a {\it cone\/} iff $C$ is closed under positive linear combinations, that is, iff \[ \lambda_1 u_1 + \cdots + \lambda_k u_k \in C, \] for all $u_1, \ldots, u_k \in C$ and all $\lambda_i\in \reals$, with $\lambda_i \geq 0$ and $1 \leq i \leq k$. Note that we always $0\in C$. \medskip (i) Check that $C$ is convex. \medskip For any subset, $V\subseteq \reals^d$, the {\it positive hull of $C$\/}, $\mathrm{cone}(V)$, is given by \[ \mathrm{cone}(V) = \{\lambda_1 u_1 + \cdots + \lambda_k u_k \mid u_i\in V, \> \lambda_i\geq 0,\> 1\leq i \leq k\}. \] A cone, $C\subseteq \eucreal^d$, is a {\it $\s{V}$-cone\/} or {\it polyhedral cone\/} if $C$ is the positive hull of a finite set of vectors, that is, \[ C = \mathrm{cone}(\{u_1, \ldots, u_p\}), \] for some vectors, $u_1, \ldots, u_p\in \reals^d$. \medskip A cone, $C\subseteq \eucreal^d$, is an {\it $\s{H}$-cone\/} iff it is equal to a finite intersection of closed half spaces cut out by hyperplanes through $0$. \medskip Say that {\it $C$ has $0$ as an apex\/} iff there is a hyperplane, $H$, though $0$, so that $H\cap C = \{0\}$. \medskip (ii) Let $H$ and $H'$ be parallel hyperplanes with $0\in H$. Prove that for any closed cone, $C$, if $C\cap H'\not= \emptyset$, then $C\cap H = \{0\}$ iff $C\cap H'$ is bounded. \medskip\noindent {\it Hint\/}: If $A\cap H'$ is not bounded, use problem B1 to construct a sequence of points, $a_n$, along a ray in $A$ and consider the sequence of unit vectors, $u_n = \frac{a_n}{\norme{a_n}}$. Show that the $u_n$ converge to a vector, $u\in C\cap H$, a contradiction. \medskip (iii) Let $C$ be a polyhedral cone of dimension $d\geq 2$. Prove that the following statements are equivalent: \begin{enumerate} \item[(a)] $C$ has $0$ as an apex. \item[(b)] There is a hyperplane, $H'$, not passing through $0$ such that $C\cap H'$ is a polytope. \item[(c)] There is some polytope, $P$, of dimension $d-1$ such that $C = \mathrm{cone}(P)$. \end{enumerate} \medskip (iv) Prove that every polyhedral cone with $0$ as an apex is an intersection of closed half-spaces, $\bigcap_{i = 1}^p (H_i)_-$, with $\bigcap_{i = 1}^p H_i = \{0\}$. \medskip If $C = \bigcap_{i = 1}^p (H_i)_-$ with $\bigcap_{i = 1}^p H_i = \{0\}$, is $C$ is $\s{V}$-cone with $0$ as an apex? \vspace{0.5cm}\noindent {\bf Problem B3 (40 pts)}. Let $C\subseteq \eucreal^d$ be any $\s{V}$-cone with nonempty interior. Pick any $\Omega$ in the interior of $C$, and consider the polar dual, $C^*$, of $C$ w.r.t. $\Omega$. \medskip (i) Prove that $C^*$ is an $\s{H}$-polytope, namely if $C = \mathrm{cone}(\{u_1, \ldots, u_p\})$, then \[ C^* = (0^{\dagger})_- \cap \bigcap_{i = 1}^p (u_i^{\dagger})_-, \] where $(0^{\dagger})_-$ is the closed half-space containing $\Omega$ determined by the polar hyperplane, $0^{\dagger}$, of $0$ w.r.t. the center $\Omega$ and $(u_i^{\dagger})_-$ is the closed half space defined as follows: \[ (u_i^{\dagger})_- = \{x\in \eucreal^d \mid \libvecbo{\Omega}{x}\cdot u_i \leq 0\}. \] %\left\{x\in \eucreal^d \> \left| \> %(\forall t > 0)\left( %\libvecbo{ \Omega}{x}\cdot u_i < \frac{1}{t}, \right. \right)\right\}\ %\cup \{x\in \eucreal^d \mid \libvecbo{\Omega}{x}\cdot u_i = 0\}. %\] Note that $\{x\in \eucreal^d \mid \libvecbo{\Omega}{x}\cdot u_i = 0\}$ is the hyperplane through $\Omega$ perpendicular to $u_i$, so $(u_i^{\dagger})_-$ is the closed half-space on the side opposite to $u_i$ and bounded by this hyperplane. Draw a few pictures in the case of the plane to understand what's going on. \medskip (ii) Use (i) and the equivalence of $\s{H}$-polytopes and $\s{V}$-polytopes to prove that $C = C^{**}$ is an $\s{H}$-cone. Therefore, any $\s{V}$-cone is an $\s{H}$-cone. \medskip (iii) Use a similar argument to prove that any polyhedral set (i.e., a $\s{V}$-polyhedron) is an $\s{H}$-polyhedron. \vspace {0.5cm}\noindent {\bf Problem B4 (20 pts).} Let $P\subseteq \eucreal^d$ be a $\s{V}$-polyhedron, $P = \mathrm{conv}(Y) + \mathrm{cone}(V)$, where \\ $Y = \{y_1, \ldots, y_p\}$ and $V = \{v_1, \ldots, v_q\}$. Define $\widehat{Y} = \{\widehat{y}_1, \ldots, \widehat{y}_p\} \subseteq \eucreal^{d+1}$, and \\ $\widehat{V} = \{\widehat{v}_1, \ldots, \widehat{v}_q\} \subseteq \eucreal^{d+1}$, by \[ \widehat{y}_i = \binom{y_i}{1}, \qquad \widehat{v}_j = \binom{v_j}{0}. \] \medskip (i) Check that \[ C(P) = \mathrm{cone}(\{\widehat{Y}\cup \widehat{V}\}) \] is a $\s{V}$-cone in $\eucreal^{d+1}$ such that \[ P = C(P) \cap H_{d+1}, \] where $H_{d+1}$ is the hyperplane of equation $x_{d+1} = 1$. \medskip Conversely, prove that if $C = \mathrm{cone}(W)$ is a $\s{V}$-cone in $\eucreal^{d+1}$, with $w_{i d+1} \geq 0$ for every $w_i\in W$, then $P = C\cap H_{d+1}$ is a $\s{V}$-polyhedron. %Conclude that a set $P\subseteq \eucreal^d$ is a $\s{V}$-polyhedron %iff $C(P)$ is a $\s{V}$-cone in $\eucreal^{d+1}$. \medskip (ii) Now, let $P\subseteq \eucreal^d$ be an $\s{H}$-polyhedron. Then, $P$ is cut out by $m$ hyperplanes, $H_i$, and for each $H_i$, there is a nonzero vector, $u_i$, and some $b_i\in \reals$ so that \[ H_i = \{x\in \eucreal^d \mid u_i\cdot x = b_i\} \] and $P$ is given by \[ P = \bigcap_{i = 1}^m\, \{x\in \eucreal^d \mid u_i\cdot x \leq b_i\}. \] If $A$ denotes the $m\times d$ matrix whose $i$-th row is $u_i$ and $b$ is the vector $b = (b_1, \ldots, b_m)$, then we can write \[ P = P(A, b) = \{x\in \eucreal^d \mid Ax \leq b\}. \] \medskip We ``homogenize'' $P(A, b)$ as follows: Let $C(P)$ be the subset of $\eucreal^{d+1}$ defined by \begin{eqnarray*} C(P) & = & \left\{ \binom{x}{x_{d+1}}\in \reals^{d+1} \mid Ax \leq x_{d+1}b,\> x_{d+1} \geq 0 \right\} \\ & = & \left\{ \binom{x}{x_{d+1}}\in \reals^{d+1} \mid Ax - x_{d+1}b\leq 0,\> -x_{d+1} \leq 0 \right\}. \end{eqnarray*} Thus, we see that $C(P)$ is the $\s{H}$-cone given by the system of inequalities \[ \begin{pmatrix} A & -b \\ 0 & -1 \end{pmatrix}\binom{x}{x_{d+1}} \leq \binom{0}{0} \] and that \[ P = C(P)\cap H_{d+1}. \] Conversely, if $Q$ is any $\s{H}$-cone in $\eucreal^{d+1}$ (in fact, any $\s{H}$-polyhedron), it is clear that \\ $P = Q\cap H_{d+1}$ is an $\s{H}$-polyhedron in $\eucreal^d$. \medskip Problem B4 shows that the equivalence of $\s{V}$-polyhedra and $\s{H}$-polyhedra reduces to the equivalence of $\s{V}$-cones and $\s{H}$-cones, constructively (i.e. we can go from cones to polyhedra and back algorithmically). %Conclude that $P$ is an $\s{H}$-polyhedron in $\eucreal^d$ iff %$C(P)$ is an $\s{H}$-cone in $\eucreal^{d+1}$. \vspace{0.5cm}\noindent {\bf Problem B5 (40 pts)}. Let $C\subseteq \eucreal^d$ be an $\s{H}$-cone. Then, $C$ is cut out by $m$ hyperplanes, $H_i$, through $0$. For each $H_i$, there is a nonzero vector, $u_i$, so that \[ H_i = \{x\in \eucreal^d \mid u_i\cdot x = 0\} \] and $C$ is given by \[ C = \bigcap_{i = 1}^m\, \{x\in \eucreal^d \mid u_i\cdot x \leq 0\}. \] If $A$ denotes the $m\times d$ matrix whose $i$-th row is $u_i$, then we can write \[ C = P(A, 0) = \{x\in \eucreal^d \mid Ax \leq 0\}. \] Observe that $C = C_0(A) \cap H_w$, where \[ C_0(A) = \left\{\binom{x}{w}\in \reals^{d + m} \> \left| \> Ax \leq w \right. \right\} \] is an $\s{H}$-cone in $\eucreal^{d + m}$ and \[ H_w = \left\{\binom{x}{w}\in \reals^{d + m} \> \left| \> w = 0 \right. \right\} \] is a hyperplane in $\eucreal^{d + m}$. \medskip (i) Prove that $C_0(A)$ is a $\s{V}$-cone by observing that if we write \[ \binom{x}{w} = \sum_{i = 1}^d |x_i|(\mathrm{sign}(x_i))\binom{e_i}{Ae_i} + \sum_{j = 1}^m (w_j - (Ax)_j)\binom{0}{e_j}, \] then \[ C_0(A) = \mathrm{cone}\left( \left\{ \pm\binom{e_i}{Ae_i} \> \left| \> 1\leq i \leq d \right. \right\} \cup \left\{ \binom{0}{e_j} \> \left| \> 1\leq j \leq m \right. \right\} \right). \] \medskip (ii) Since $C = C_0(A) \cap H_w$ is now the intersection of a $\s{V}$-cone with a hyperplane, to prove that $C$ is a $\s{V}$-cone it is enough to prove that the intersection of a $\s{V}$-cone with a hyperplane is also a $\s{V}$-cone. For this, we use {\it Fourier-Motzkin elimination\/}. It suffices to prove the result for a hyperplane, $H_k$, in $\eucreal^{d + m}$ of equation $y_k = 0$ ($1\leq k \leq d + m$). \medskip Say $C = \mathrm{cone}(Y)\subseteq \eucreal^d$ is a $\s{V}$-cone. Then, the intersection $C\cap H_k$ (where $H_k$ is the hyperplane of equation $y_k = 0$) is a $\s{V}$-cone, $C\cap H_k= \mathrm{cone}(Y^{/k})$, with \[ Y^{/k} = \{y_i \mid y_{i k} = 0\} \cup \{y_{i k}y_j - y_{j k}y_i \mid y_{i k} >0,\, \> y_{j k} < 0\}, \] the set of vectors obtained from $Y$ by ``eliminating the $k$-th coordinate''. Here, each $y_i$ is a vector in $\reals^d$. \medskip\noindent {\it Hint\/}. The only nontrivial direction is to prove that $C\cap H_k \subseteq \mathrm{cone}(Y^{/k}) $. For this, consider any $v = \sum_{i = 1}^d t_i y_i\in C\cap H_k$, with $t_i \geq 0$ and $v_k = 0$. Such a $v$ can be written \[ v = \sum_{i \mid y_{i k} = 0} t_i y_i + \sum_{i \mid y_{i k} > 0} t_i y_i + \sum_{j \mid y_{j k} < 0} t_j y_j \] and as $v_k = 0$, we have \[ \sum_{i \mid y_{i k} > 0} t_i y_{i k} + \sum_{j \mid y_{j k} < 0} t_j y_{j k} = 0. \] If $t_i y_{i k} = 0$ for $i = 1,\ldots, d$, we are done. Otherwise, we can write \[ \Lambda = \sum_{i \mid y_{i k} > 0} t_i y_{i k} = \sum_{j \mid y_{j k} < 0} -t_j y_{j k} > 0. \] Then, \[ v = \sum_{i \mid y_{i k} = 0} t_i y_i + \frac{1}{\Lambda} \sum_{i \mid y_{i k} > 0}\left( \sum_{j \mid y_{j k} < 0} -t_j y_{j k} \right) t_iy_i + \frac{1}{\Lambda} \sum_{j \mid y_{j k} < 0}\left( \sum_{i \mid y_{i k} > 0} t_i y_{i k} \right) t_j y_{j} . \] \medskip Conclude that every $\s{H}$-cone is a $\s{V}$-cone. \medskip (iii) Use Problem B4 to prove that if $P$ is an $\s{H}$-polyhedron then it is a $\s{V}$-polyhedron. \vspace{0.5cm}\noindent {\bf Problem B6 (20 pts)}. Prove that Farkas Lemma, version III implies Farkas Lemma, version II (from the notes). \vspace{0.5cm}\noindent {\bf TOTAL: 190 points.} \end{document}