# How to show directly that finitely generated cone contains polyhedral cone of nonnegative vectors?

Let $$P=\{x \in \mathbb{R}^n \mid Ax \geq b, x \geq 0 \}$$ be a nonempty polyhedron for matrix $$A \in \mathbb{R}^{m \times n}$$ and $$b \in \mathbb{R}^m$$.

According to Minkowski-Weyl theorem $$P$$ can be written as

$$P=\text{conv}(v_1,\cdots,v_p)+ \text{cone}(d_1,\cdots,d_l)$$ for some $$v_i \in \mathbb{R}^n$$ and $$d_j \in \mathbb{R}^n$$.

Let $$C=\{x \in \mathbb{R}^n \mid Ax \geq 0, x \geq 0 \}$$.

Show that $$C \subseteq \text{cone}(d_1,\cdots,d_l)$$.

The reverse has been proven in How to show polyhedral cone of nonnegative vectors contains finitely generated cone?

My try:

$$C$$ can be written as the following:

$$Ax \geq 0, x \geq 0 \,\,\, \Rightarrow A' = \begin{bmatrix} A \\ I \end{bmatrix} x \geq 0$$

Hence, $$C=\{x' \in \mathbb{R}^{2n} \mid A'x' \geq 0 \}$$ which is a polyhedral cone and using the theorem saying that every polyhedral cone is a finitely generated cone we are done.

I want to show this using rigorous prove, and not using that theorem.

We know that $$P=\text{conv}(v_1,\cdots,v_p)+ \text{cone}(d_1,\cdots,d_l)=V+D.$$ Take $$x\in C$$ $$\Leftrightarrow$$ $$Ax\ge 0$$, $$x\ge 0$$, and $$p\in P$$ then $$A(p+tx)=Ap+tAx\ge b,\quad p+tx\ge 0,\quad\forall t\ge 0,$$ hence $$p+tx\in P$$, $$\forall t\ge 0$$. From the representation above $$p+tx=v_t+d_t\quad\Leftrightarrow\quad \frac{1}{t}p+x=\frac{1}{t}v_t+\frac{1}{t}d_t.$$ Let $$t\to+\infty$$ then $$\frac{p}{t}\to 0$$ and $$\frac{v_t}{t}\to 0$$ ($$V$$ is bounded), hence $$\frac{1}{t}d_t\to x.$$ Since $$\frac{d_t}{t}\in D$$ and $$D$$ is closed, we must have $$x\in D$$.

• If we assume that $V$ is bounded, then $v_t/t \rightarrow 0$ makes sence. But what is the reason $p_t/t \rightarrow 0$? Because $p_t$ already contains $d_t$ which is not bounded. – Sepide Dec 16 '18 at 23:13
• @Sepide $V$ is bounded as a convex hull of finitely many points, it is a fact, not an assumption. $p$ is a fixed point, it does not depend on $t$. – A.Γ. Dec 17 '18 at 5:52