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.
[Math] Polyhedral cone as conic hull of a finite set
convex-analysislinear algebrapolyhedra
Related Solutions
Indeed, all except perhaps property (2) can be proved without functional analysis. It leads to a completely deterministic algorithm to compute a basis for the dual cone (not a very good algorithm though as its complexity is exponential in the initial basis size).
In the sequel RCP is shorthand for “rational convex polyhedral cone”.
Nearly everything reduces to the iteration of the following lemma:
Fundamental lemma. Let $\sigma={\sf Cone}(u_1,\ldots,u_k)$ be a RPC cone. Let $w\in{{\mathbb Z}^d}$, and $\sigma_w=\lbrace x\in\sigma \,|\, \langle x,w\rangle\ \geq 0\rbrace$. Then $\sigma_w$ is again a RPC cone. In fact, a completely explicit generating set can be found, as follows. Let
$$ \begin{array}{lcl} I_{-} &=& \big\lbrace i \ \big|\ \langle u_i,w\rangle \ < 0 \big\rbrace \\ I_{0} &=& \big\lbrace i \ \big|\ \langle u_i,w\rangle \ = 0 \big\rbrace \\ I_{+} &=& \big\lbrace i \ \big|\ \langle u_i,w\rangle \ < 0 \big\rbrace \\ \end{array} $$
Then $\sigma_w={\sf Cone}({\cal F})$ where
$$ {\cal F}=\big\lbrace u_i\ \big|\ i \in I_0 \cup I_{+}\big\rbrace \cup \big\lbrace \langle u_j,w\rangle u_i-\langle u_i,w\rangle u_j\ \big| \ i \in I_{-}, j\in I_{+}\big\rbrace $$
To show this fundamental lemma we need another :
Lemma 1. Let $n,m \geq 1$ be two integers. Let $x_1,x_2,\ldots,x_n$ and $y_1,y_2,y_3, \ldots ,y_m$ be nonnegative numbers. Then the following are equivalent :
(i) $x_1+x_2+ \ldots +x_n \geq y_1+\ldots +y_m$
(ii) There exists nonnegative numbers $\xi_k(1\leq k\leq n)$ and $t_{ij}(1\leq i \leq n,1\leq j \leq n)$ such that $x_i=\xi_i+\sum_{j}t_{ij}$ for every $i$ and $y_j=\sum_{i}t_{ij}$ for every $j$.
Proof of lemma 1. The direction (ii)$\Rightarrow$(i) is easy because under the hypothesis of (ii) we have
$$ \big(\sum_{i} x_i\big)-\big(\sum_{j} y_j\big)= \big(\sum_{i} \xi_i\big) \geq 0 $$
Conversely, we are going to show (i)$\Rightarrow$(ii) by induction on $N=n+m$. The base case $N=2$ is easy : we have $x_1\geq y_1$ and need just take $\xi_1=0,t_{11}=y_1$.
Now suppose the property is true at level $N$ ; we are going to show it still holds at level $N+1$. So suppose $x_1+x_2+ \ldots +x_n \geq y_1+\ldots +y_m$ for some nonnegative numbers $x_1,x_2,\ldots,x_{n},y_1,y_2,\ldots,y_m$, with $n+m=N+1$. There are two cases.
Case 1. $x_n \geq y_m$. Then we can write $x_n=y_m+X_n$ where $X_n$ is nonnegative. We then have an inequality with one variable less : $x_1+x_2+\ldots+x_{n-1}+X_n \geq y_1+y_2+\ldots +y_{m-1}$ and we can apply the induction hypothesis.
Case 2. $y_m \geq x_n$. Then we can write $y_m=x_n+Y_m$ where $Y_m$ is nonnegative. We then have an inequality with one variable less : $x_1+x_2+\ldots+x_{n-1} \geq y_1+y_2+\ldots +y_{m-1}+Y_m$ and we can apply the induction hypothesis.
This concludes the proof of lemma 1.
Proof of fundamental lemma from lemma 1. Let $\tau={\sf Cone}({\cal F})$. As all vectors in $\cal F$ are nonnegative linear combinations of the $u_i$, whose scalar product with $w$ is nonnegative, we have ${\cal F} \subseteq \sigma_w$ and hence $\tau \subseteq \sigma_w$. Conversely, let $v\in\sigma_w$. Let us put $n=|I_+|,m=|I_{-}|,p=I_{0}$. Reordering the $u_i$ if necessary, we may assume without loss that $I_+=[1,n],I_-=[n+1,n+m],I_0=[n+m,d]$. Then, there are nonnegative coefficients $a_1,a_2,\ldots, a_n,b_1,b_2,\ldots, b_m,c_1,c_2, \ldots, c_p$ such that
$$ v=\sum_{i=1}^{n} a_iu_i- \sum_{j=1}^{m} b_ju_{n+j}+ \sum_{k=1}^{p} c_ku_{n+m+k} \tag{1} $$
Then, the condition $\langle v,w\rangle \geq 0$ can be expressed as
$$ \sum_{i=1}^{n} a_i\langle u_i,w\rangle- \sum_{j=1}^{m} b_j\langle u_{n+j},w\rangle \geq 0 \tag{2} $$
Or, if we put $x_i=a_i\langle u_i,w\rangle$ and $y_j=b_j\langle u_{n+j},w\rangle $,
$$ \sum_{i=1}^{n} x_i- \sum_{j=1}^{m} y_j \geq 0 \tag{3} $$
This is the hypothesis of (i) in lemma 1, so let $\xi_k(1\leq k\leq n)$ and $t_{ij}(1\leq i \leq n,1\leq j \leq n)$ as in (ii) of this lemma. We then have
$$ \begin{array}{lcl} a_i&=&\frac{\xi_i+\sum_{j}t_{ij}}{\langle u_i,w\rangle } (1\leq i\leq n),\\ b_j&=&\frac{\xi_i+\sum_{i}t_{ij}}{\langle u_{n+j},w\rangle } (1\leq j\leq m) \end{array} \tag{4} $$
If we put $z_i=\frac{\xi_i}{\langle u_i,w\rangle }$ and $s_{ij}=\frac{t_{ij}}{\langle u_i,w\rangle\,|\langle u_{n+j},w\rangle|}$, we then have
$$ v=\sum_{i=1}^n z_i u_i +\sum_{i=1}^n \sum_{j=1}^m s_{ij}(\langle u_{n+j},w\rangle u_i-\langle u_i,w\rangle u_{n+j})+ \sum_{k=1}^{p} c_ku_k \tag{5} $$
which is plainly an element of $\tau$. This concludes the proof of the fundamental lemma.
Proof of property (1) from fundamental lemma Notice that ${\cal C}_0={\mathbb R}^d$ is itself a RCP cone (it can be written as ${\sf Cone}(e_1,-e_1,e_2,-e_2, \ldots ,e_d,-e_d)$ where $(e_1,e_2,\ldots ,e_d)$) is the canonical basis of ${\mathbb R}^d$). Then, let
$$ {\cal C}_i=\lbrace v\in {\mathbb R}^d \ | \ \langle v,u_j\rangle \ \geq 0 \ (1\leq j \leq i)\rbrace $$
Iterating the fundamental lemma, we see successively that ${\cal C}_0, {\cal C}_1,\ldots,$ are all RCP cones. In the end ${\sigma}^\vee={\cal C}_k$ is a RCP cone.
$\newcommand{\Co}{\operatorname{Co}}$If you want to prove that $$ \Co\left( \bigcup_{i=1}^k X_i \right) \subseteq \left\{\sum_{i=1}^k t_i x_i : x_i \in X_i,t_i\geq 0,\sum_{i=1}^k t_i =1\right\}, \tag 1 $$ you should just assume $x$ is an element of the left side and prove that it follows that it's an element of the right side.
For now I'll take $\Co\left( \bigcup_{i=1}^k X_i \right)$ to be defined as the intersection of all convex sets having $\bigcup_{i=1}^k X_i$ as a subset. To show that if $x$ is a member of the left side of $(1)$, then $x$ is a member of the right side of $(1)$ is to show that if $x$ is a member of every convex set having $\bigcup_{i=1}^k X_i$ as a subset, then $x$ is a member of the right side of $(1)$. For that, it is enough to show that the right side of $(1)$ is a convex set having $\bigcup_{i=1}^k X_i$ as a subset. Then we would have
- $x$ is a member of every convex set having $\bigcup_{i=1}^k X_i$ as a subset.
- The right side of $(1)$ is a convex set having $\bigcup_{i=1}^k X_i$ as a subset.
- Therefore, $x$ is a member of the right side of $(1)$.
So the question is: How do we prove the second statement in the bulleted list above?
Notice that if $t_j=1$ and $t_i=0$ for all $i\ne j$, then $t_i\ge0$ for $i=1,\ldots,k$ and $t_1+\cdots+t_k = 1$, so $t_1 x_1 + \cdots + t_k x_k$ is a member of the right side of $(1)$. But $t_1 x_1 + \cdots + t_k x_k = x_j \in X_j$. Thus $x_j$ is a member of the right side of $(1)$. Since $x_j$ could have been any member of $X_j$ at all, we conclude that every member of $X_j$ is a member of the right side of $(1)$, so $X_j$ is a subset of the right side of $(1)$. Since the index $j$ may be any of $1,\ldots,k$, we must conclude that all of $X_1,\ldots,X_k$ are subsets of the right side of $(1)$. Therefore $\bigcup_{i=1}^k X_i$ is a subset of the right side of $(1)$.
Next we must prove that the right side of $(1)$ is convex. So suppose $x$ and $y$ are members of that set; we must prove that every convex combination $cx+(1-c)y$ is a member of the right side of $(1)$. We have \begin{align} x & = t_1 x_1 + \cdots + t_k x_k \\[5pt] y & = s_1 y_1 + \cdots + s_k y_k \end{align} for some scalars $t_1,\ldots,t_k,s_1,\ldots,s_k$, all $\ge0$ and satisfing $t_1+\cdots+t_k=1=s_1+\cdots+s_k$.
Let
$$ w_i = \frac{ct_i}{ct_i + (1-c)s_i} x_i + \frac{(1-c)s_i }{ct_i + (1-c)s_i} y_i\qquad \text{for }i=1,\ldots,k $$ and $$ r_i = c t_i + (1-c) s_i \qquad \text{for }i=1,\ldots,k. $$
Then $$ cx+(1-c)y = \sum_{i=1}^k r_i w_i. \tag 2 $$ Since it was assumed that $X_i$ is convex, we have $w_i\in X_i$ for $i=1,\ldots,k$. Therefore, $(2)$ is a member of the right side of $(1)$.
Best Answer
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).