Exposed Extreme Rays Of The Nonnegative Cone

An extreme ray of a cone $C$ is a $1$-dimensional face of $C$. A point $x \in C$ spans an extreme ray if and only if whenever $x=\alpha_1 y_1+\alpha_2 y_2$ with $y_1,y_2 \in C$ and $\alpha_1,\alpha_2 \in \mathbb{R}_+$ then $y_1$ and $y_2$ lie on the ray spanned by $x$: $x=\lambda_1 y_1=\lambda_2 y_2$ with $\lambda_1,\lambda_2 \in \mathbb{R}_+$.

Show that $p \in P_{n,2d}$ spans an exposed extreme ray of $P_{n,2d}$ if and only if for all $q \in P_{n,2d}$ with $V_{\mathbb{R}}(p) \subseteq V_{\mathbb{R}}(q)$ it follows that $q=\lambda p$ for some $\lambda \in \mathbb{R}$.


Solution:

Suppose that $p\in P_{n,2d}$ spans an exposed extreme ray and take $q \in P_{n,2d}$ with $V_{\mathbb{R}}(p) \subseteq V_{\mathbb{R}}(q)$. Since the span $F$ of $p$ is exposed, we can write $F = \{f \in P_{n,2d} : \lambda_1f(v_1) + \ldots + \lambda_mf(v_m) = 0\}$, where the $\lambda_j$ are positive (here using the description of $P_{n,2d}^\ast$ proved in another exercise). This implies that $v_1,\ldots,v_m \in V_{\mathbb{R}}(p) \subseteq V_{\mathbb{R}}(q)$. So we must have that $q \in F$

Conversely, suppose that whenever $V_{\mathbb{R}}(p) \subseteq V_{\mathbb{R}}(q)$ it follows that $q\in F$. Then $F$ is a face because $p = \alpha_1 y_1+\alpha_2 y_2$ with $\alpha_1,\alpha_2 \in \mathbb{R}_+$ and $y_1,y_2 \in P_{n,2d}$ implies that $V_{\mathbb{R}}(y_1),V_{\mathbb{R}}(y_2)$ both contain $V_{\mathbb{R}}(p)$. To see that $F$ is also exposed, notice that $F$ is equal to the dual face of its dual face:

In general, we have $F \subset (F^\Delta)^\Delta$. If $q \in (F^\Delta)^\Delta$, then $V_{\mathbb{R}}(p) \subseteq V_{\mathbb{R}}(q)$ and we conclude that $q \in F$. Since dual faces are exposed, we are done.-MH

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License