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

418 Views Asked by At

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 $\text{cone}(d_1,\cdots,d_l) \subseteq C$.

The thing that that I cannot cope with is how to connect the finite number $l$ that can be any natural number with dimension of the matrix $A$.

I tried the following:

Let $z \in \text{cone}(d_1,\cdots,d_l)$, so there exist non-negative $\mu_i$'s such that

$$ z= \sum_{i=1}^l \mu_id_i $$ where $\mu_1,\mu_2,\cdots,\mu_l \geq 0$.

We can write $z$ as the following:

$$ z= \begin{bmatrix} d_1 & d_2 & \cdots & d_l \end{bmatrix} \begin{bmatrix} \mu_1 \\ \mu_2 \\ \cdots \\ \mu_l \end{bmatrix} $$

Now, we should come up with an $m \times n$ matrix $A$ for which we have $Az \geq 0$ and $z \geq 0$ to prove the claim. But the problem is we do not have $z \geq 0$ necessarily.

1

There are 1 best solutions below

2
On BEST ANSWER

We know that $P$ can be written as $$ P=\operatorname{conv}(v_1,\cdots,v_p)+ \operatorname{cone}(d_1,\cdots,d_l)=V+D. $$ The set $D$ is a cone, hence, for every $v\in V$ and $d\in D$ we have that $v+td\in P$, $\forall t\ge 0$. That is $$ A(v+td)\ge b,\quad v+td\ge 0,\quad\forall t\ge 0. $$ Now divide by $t$ and let $t\to +\infty$ \begin{align} \frac{1}{t}Av+Ad\ge\frac{1}{t}b\quad&\Rightarrow\quad Ad\ge 0,\\ \frac{1}{t}v+d\ge 0 \quad&\Rightarrow\quad d\ge 0. \end{align} Therefore, every $d\in D$ belongs to $C$.