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.

  • $\begingroup$ The statement is not true for any choice of $v_i$, so you need to chose them appropriately. $\endgroup$ – LinAlg Dec 14 '18 at 22:27
  • $\begingroup$ @ LinAlg: The statement is true because it says for some $v_i$ and $d_j$. Also, it does not say what $p$ and $l$ are. Maybe I am wrong who am using wrong number for $l$. $\endgroup$ – Sepide Dec 15 '18 at 0:22
  • $\begingroup$ a proof by contradiction is easier here: what if $z$ is not in $C$? $\endgroup$ – LinAlg Dec 15 '18 at 0:59
  • $\begingroup$ @LinAlg: How we can do that? $\endgroup$ – Sepide Dec 15 '18 at 4:13
  • $\begingroup$ if $z$ does not satisfy $Az\geq 0$ or $z\geq 0$, moving in the direction of $z$ will violate a constraint of $P$ $\endgroup$ – LinAlg Dec 15 '18 at 16:19

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

  • $\begingroup$ Could you help me show the reverse? I mean $ C \subseteq \text{cone}(d_1,\cdots,d_l) $. It cannot be immediately observed from your proof to show the reverse, I am having trouble of producing $x \geq 0$? $\endgroup$ – Sepide Dec 15 '18 at 18:32
  • $\begingroup$ I have proved it using different method, but you might be show it differently. I posted it as an another question: math.stackexchange.com/questions/3041877/… $\endgroup$ – Sepide Dec 15 '18 at 19:54

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.