# Polyhedral cone as conic hull of a finite set

I am reading notes on optimization and it was claimed that all polyhedral cones in $K\subseteq \mathbb{R}^n$ can be written Cone(R) where $R\subseteq \mathbb{R}^n$ is a finite set. That is, if K is a polyhedral cone, then $K=\{\sum_{i=1}^k a_i h_i: a_i\geq 0 \}$ for some finite set $R:=\{h_1,...,h_k\}\subseteq \mathbb{R}^n$.
I would like to convince myself this is true. It seems intuitively obvious, but I don't know how to go about showing it. I already know that all bounded, polyhedral sets can be expressed as the convex hull of a finite # of pts. One direction I am considering is how to use that result here.

The polyhedral cone $K$ is defined as an intersection of a finite number of half-spaces, i.e. $K=\{x\in\mathbb{R}^n\colon Ax\ge 0\}$, where $A\in\mathbb{R}^{m\times n}$. Since $\text{Im}\,A$ is a subspace, it can be represented as a kernel of some matrix $M$, that is $\ker M=\text{Im} A$. Hence, we have $$y=Ax,\ x\in K\qquad\Leftrightarrow\qquad y\in Y=\{y\in\mathbb{R}^m\colon\ My=0,\ y\ge 0\}.\tag1$$ Introduce the set $$P=\{z\in Y\colon\ (\matrix{1 & 1 & \ldots & 1})z=1\}.$$ It is a bounded polyhedral set, thus, finitely generated (according to what you know) $$\exists z_1,z_2,\ldots,z_N\in P\colon\ P=\text{conv}\{z_1,z_2,\ldots,z_N\}.$$ Therefore, even $Y$ is a finitely generated (positive) cone $$Y=\text{cone}\{z_1,z_2,\ldots,z_N\}$$ since any $y\in Y$ is a non-negative scaling of some $z\in P$.
Now by $(1)$ we can pick $x_k\in K$ such that $z_k=Ax_k$, and we are almost done finding a finite generating set for $K$. The minor trouble left is $\ker A$. Actually, it is quite easy to see that $$K=\ker A+\text{cone}\{x_1,x_2,\ldots,x_N\}.$$ I leave it as an exercise (together with the fact that $\ker A$ is a finitely generated cone).
• There must be something wrong here, consider following example: $A=\left[\begin{smallmatrix}1&2\\2&1\end{smallmatrix}\right]$. $\text{Im}A=\mathbb R^2$, thus $M=0$ suffices $\ker M=\text{Im}A$, so we have $Y=\mathbb R_+^2$ and $P=\left\{z_1, z_2\right\}$ with $z_1=\left[\begin{smallmatrix}1\\0\end{smallmatrix}\right]$ and $z_2=\left[\begin{smallmatrix}0\\1\end{smallmatrix}\right]$. For $z_1$ the linear system $z_k=Ax_k$ yields $x_1=\left[\begin{smallmatrix}-1/3\\2/3\end{smallmatrix}\right]$, but $x_1 \not\in K$ (which it should be since $\ker A=\left\{0\right\}$). – theV0ID Sep 4 '18 at 15:35
• @theV0ID $K$ is defined as $Ax\ge 0$. Since $Ax_1=z_1=\left[\begin{smallmatrix}1\\0\end{smallmatrix}\right]\ge 0$ it follows that $x_1\in K$. Did you expect $x_1\ge 0$? (This is no how $K$ is defined.) – A.Γ. Sep 4 '18 at 16:07
• @theV0ID The cone $K$ in your example looks like this (blue area). The vector $3x_1=\left[\begin{smallmatrix}-1\\2\end{smallmatrix}\right]$ is one of the extreme directions of the cone (the left top one on the picture). – A.Γ. Sep 4 '18 at 16:24
• Any idea on how to determine $z_1, \dots, z_N$ algorithmically? – theV0ID Sep 6 '18 at 17:06