2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ 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\}$). $\endgroup$ – theV0ID Sep 4 '18 at 15:35
  • $\begingroup$ @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.) $\endgroup$ – A.Γ. Sep 4 '18 at 16:07
  • $\begingroup$ @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). $\endgroup$ – A.Γ. Sep 4 '18 at 16:24
  • $\begingroup$ You are right, thanks for the clarification (seems I lost focus at the end of a long day). However, your geogebra link does not work, it says "failed to open file". $\endgroup$ – theV0ID Sep 5 '18 at 9:02
  • $\begingroup$ Any idea on how to determine $z_1, \dots, z_N$ algorithmically? $\endgroup$ – theV0ID Sep 6 '18 at 17:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.