Why are convex polyhedral cones closed?

Solution 1:

Here is another proof without induction on dimensions.

Let $A$ be the matrix with column vectors $v_1\dots v_s$.

Claim: The cone $$ \sigma:=\{ x: \ Ay = x, \ y\ge 0\} $$ is closed.

Notation: For an index set $I\subset\{1\dots s\}$ define $\| y \|_I^2 := \sum_{i\in I} y_i^2$.

Proof: Let $(x_k)$ in $\sigma$ be given, such that $x_k\to x$.

The set $\tau_k:=\{ y\ge 0: \ Ay = x_k\}$ is non-empty and closed (the mapping $f:y\mapsto Ay$ is continuous, hence $f^{-1}(\{x\})$ is closed). Hence for each $k$ there is $y_k$ satisfying $$ \|y_k\| = \inf_{y\in \tau_k}\|y\|. $$ If $(y_k)$ does contain a bounded subsequence, then we are done.

It remains to consider the case $\|y_k\|\to \infty$. Denote $\tilde v_k:=\frac1{\|y_k\|}y_k$. By compactness, it contains a converging subsequence. W.l.o.g. let $(\tilde v_k)$ be converging to $v$ with $\|v\|=1$, $v\ge 0$. Moreover, $Av =0$.

Denote $I_1:=\{j: v_j>0\}$, $I_2:=\{1\dots n\}\setminus I_1$. Since $\|v\|=\|v\|_{I_1}$, it follows $\frac{\|y_k\|_{I_1}}{\|y_k\|} \to 1$. Hence, the sequence $(v_k)$ defined by $v_k:=\frac1{\|y_k\|_{I_1}}y_k$ converges to $v$, too. Then there is an index $M$ such that $$ v_{k,i}\in \left[ \frac12 v_i, \frac54 v_i\right] $$ for all $k>M$, $i\in I_1$. In the following let $k>M$. The above inclusion is equivalent to $$ 0\le y_{k,i} - \frac{\|y_k\|_{I_1}}2 v_i\le \frac34 \|y_k\|_{I_1} v_i \quad \forall i\in I_1. $$

Define $z_k:= y_k - \frac{\|y_k\|_{I_1}}2 v$. Then it holds $z_k\ge 0$, $Az_k = x_k$, which implies $z_k\in \tau_k$.

Now, let us show that the norm of $z_k$ is strictly less than the norm of $y_k$, which would give a contradiction to the minimum norm property of $y_k$. We have $$ \begin{split} \|z_k\|^2 & = \|z_k\|_{I_1}^2 + \|z_k\|_{I_2}^2 \le \left(\frac34\|y_k\|_{I_1}\cdot \|v\|_{I_1}\right)^2 + \|y_k\|_{I_2}^2\\ &= \frac9{16} \|y_k\|_{I_1}^2 +\|y_k\|_{I_2}^2 \\ &= \|y_k\|^2 - \frac 7{16}\|y_k\|_{I_1}^2 < \|y_k\|^2, \end{split} $$ which is a contradiction to the minimal norm property of $y_k$.

Note: The claim only holds for a finite set of vectors $v_1\dots v_s$. If $A$ is a linear mapping on an infinite-dimensional space, then the proof fails: We cannot prove that $\frac1{\|y_k\|} y_k$ converges strongly, and we cannot prove that $\frac1{\|y_k\|} y_k$ converges weakly to a non-zero element $v$.

Solution 2:

I think this problem has some intrinsic intricacies that you cannot get away from, but a careful induction proof will keep the intricacies down as much as possible.

First, let $W \subset V$ be the unique linear subspace of maximal dimension such that $W \subset \sigma$. Let $q :\mathbb{R}^n \to \mathbb{R}^n / W$ be the quotient by $W$. One checks that $q(\sigma) = \text{Cone}(q(v_1),….,q(v_s))$ and that $\sigma = q^{-1}(q(\sigma))$. This allows one to reduce to the case that $\dim(W)=0$: if this is not true for $\sigma$ in $V$, it is true for $q(\sigma)$ in $V/W$, allowing you to conclude that $q(\sigma)$ is closed, and therefore $\sigma$ is closed by continuity of $q$.

We may therefore assume that $W$ is trivial. It follows that there exists a codimension 1 linear subspace $P$ and a half space $H$ bounded by $P$ such that $\sigma \subset H$ and such that $P \cap \sigma$ is a single point. Let $P'$ be a hyperplane parallel to $P$ that is contained in the interior of $H$. Let $A_i$ be the intersection of $P'$ with the ray $[0,+\infty) \cdot v_i$. Denote the convex hull of the points $A_i$ by $$\text{Hull}(A_1,…,A_s) = \{t_1 A_1 + \cdots + t_s A_s \bigm| t_i \ge 0, t_1 + \cdots + t_s = 1\} \subset P' $$

If we can show that $\text{Hull}(A_1,…,A_s)$ is closed then it is easy to see that $\sigma$ is closed, using that each point of $\sigma$ except for the origin is uniquely represented in the form $r A$ where $r \in (0,+\infty)$ and $A \in \text{Hull}(A_1,….,A_s)$.

In fact the set $\text{Hull}(A_1,…,A_s)$ is compact, so it is closed. Compactness is proved in two steps. First one does one single special case, namely the "standard $s-1$ simplex" which is $$\Delta^{s-1} = \text{Hull}(e_1,…,e_s) = \{(t_1,…,t_s) \in \mathbb{R}^s \bigm| t_i \ge 0, t_1 + \cdots + t_s=1\} $$ where $e_1,…,e_s$ are the standard unit vectors in $\mathbb{R}^s$. Then one uses that to prove compactness of $\text{Hull}(A_1,…,A_s)$ using continuity of the function $\Delta^{s-1} \mapsto \text{Hull}(A_1,…,A_s)$ defined by $(t_1,\ldots,t_s) \mapsto t_1 A_1 + \cdots + t_s A_s$.

Finally some words about compactness of $\Delta^{s-1}$. It is a bounded set, and it is closed because it is the intersection of $s$ closed half-spaces of the hyperplane $P'$.

Added later: Regarding the existence of the half-space $H$ bounded by the hyperplane $P$, here is a proof by induction on dimension. Start by picking an affine half-space that contains $\sigma$ (any proper convex set is contained in a half-space). Translate that half-space to minimize its distance to $\sigma$. We obtain a half-space $H_1$ bounded by the hyperplane $P_1$ such that $\sigma \subset H_1$ and such that $\sigma$ has distance zero from $P_1$. From this one can argue that the origin is contained in $\sigma \cap P_1$. If $\sigma \cap P_1$ is just the origin, we're done. Otherwise, one can argue that $\sigma \cap P_1$ is a face of $\sigma$, meaning the cone of a proper subset of $v_1,…,v_s$, and therefore by induction on dimension $P_1$ contains a halfspace $H_2$ bounded by a hyperplane $P_2$ such that $H_2$ contains the face $\sigma \cap P_1$. Note that $H_2$ has codimension 2 in $V$. We can now rotate $H_1$ around $H_2$ by an arbitrarily small amount so that those of the points $v_1,…,v_s$ that were in the interior $H_1-P_1$ stay in the interior, and those which were in $P_1$ are now in the interior.

Solution 3:

I think the simplest way is to invoke Caratheodory's lemma, which says that every $v\in\sigma={\rm Cone}(v_1,\dots,v_s)$ lies in some ${\rm Cone}(v_{i_1},\dots,v_{i_t})$ with $v_{i_1},\dots,v_{i_t}$ linearly independent. Since a cone generated by linearly independent vectors can be transformed into $[0,\infty)^t\times\{0\}^{n-t}$ by a linear self-homeomorphism of $\mathbb{R}^n$, it is closed. Since there are only finitely many choices of $1\le i_1,\dots,i_t\le s$, $\sigma$ is the union of finitely many closed cones, hence closed.

The proof is similar to what appears in https://en.wikipedia.org/wiki/Carath%C3%A9odory%27s_theorem_(convex_hull)

Solution 4:

For this we first need a basic fact from linear algebra:

Let $W \subset V$ be a subspace. Then the quotient topology on $V/W$ coincides with the canonical topology on $V/W$ seen as a vector space.

Let $V/W$ denote the space $V/W$ with its canonical topology and let $V/W'$ denote the space $V/W$ with the quotient topology. By the universal property of quotient topology we automatically get that the identity map $V/W' \rightarrow V/W$ is continuous. Take a section of the canonical projection map $V \rightarrow V/W$. Then this section is automatically continuous, and the identity $V/W \rightarrow V/W'$ is by definition the composition of this section (which is continuous) and the canonical projection (which is continuous). This proves the claim

The claim above has as a consequence that if $U$ and $W$ are vector spaces and $F: U \rightarrow W$ is a linear map, then for a subset $A \subset U$, $F(A)$ is closed if and only if $A + \ker (F)$ is closed (use the isomorphism theorem to see this). Now let $v_1,.., v_s$ be generators of $\sigma$. Let $F: \mathbb{R}^s \rightarrow V$ be the unique linear map satisfying $F(e_i)=v_i$. Let $A \subset \mathbb{R}^n$ be the set of elements of $\mathbb{R}^n$ with nonnegative coordinates. By our above claims, we are done if we prove $A+\ker(F) $ is closed in $\mathbb{R}^s$. In fact, we prove this for any subspace $W \subset \mathbb{R}^s$. First assume $W \cap A \neq \{0\}$. Take $x \in \mathbb{R}^s$ arbitrary. Take $w \in W \cap A$ nonzero. Then clearly there exists some $N \in \mathbb{N}$o such that $x+Nw$ has only positive coordinates, i.e. $x+Nw \in A$. This implies immediately that $x \in A+W$, so in this case $$A+W= \mathbb{R}^s$$ which is of course closed. Now suppose $W \cap A = \{0\}$. Take a sequence $(x_n + w_n)$ in $ A+W$, $x_n \in A$, $w_n \in W$, converging to some $\alpha \in \mathbb{R}^s$. We want to show $\alpha \in W+A$. If either $x_n$ or $w_n$ has a convergent subsequence this is immediate. We claim that it cannot be the case that both $x_n$ and $w_n$ go to infinity in norm. We prove this as follows. Since $(x_n/||x_n||)$ is a bounded sequence, we may assume $(x_n/||x_n||)$ converges to some $v \in V$ with norm $1$. Note that $v \notin W$, because $v \neq 0$ and $v \in A$ because $A$ is closed and invariant under multiplication by positive scalars. Let $U$ be some complement of $W$ in $V$ and let $P: V \rightarrow U$ be the associated projection. Then $P(v) \neq 0$. and writing $x_n = u_n +w_n'$, $u_n \in U$, $w_n' \in W$, we see that $$\lim_{n \to \infty} \frac{u_n}{||x_n||} = v \neq 0$$ and since $||x_n||$ goes to infinity, we must have $u_n$ goes to infinity in norm as well. But then, giving $V$ an inner product such that $U$ and $W$ are orthogonal, we see that if $|| \cdot||_0$ denotes the norm induced by this inner product, we have $$|| x_n +w_n||_0^2 \geq ||u_n||_0^2,$$ so $||x_n+w_n||_0$ goes to infinity as well. But $x_n+w_n$ converges to $\alpha$, and any norm on a finite dimensional vector space is continuous (with respect to any other norm), so we get a contradiction. This finishes the proof.