0
$\begingroup$

Let $P=\{x \in \mathbb{R}^n \mid Ax=b, x\geq 0\}$ be a nonempty convex polyhedron (not bounded).

Show that $P$ is bounded (i.e., it is a polytope) if and only if the linear inequality $Ax=0, \,\, x\geq 0$ has trivial solution $x=0$ only.

$\endgroup$

closed as off-topic by Namaste, Shailesh, Brian Borchers, user10354138, Cesareo Dec 9 '18 at 9:15

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Namaste, Shailesh, Brian Borchers, user10354138, Cesareo
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ What does $x \ge 0$ mean? All coordinates $\ge 0$? $\endgroup$ – Paul Frost Dec 8 '18 at 23:13
  • 1
    $\begingroup$ It means each element of $x$ should be greater than zero. $\endgroup$ – Saeed Dec 8 '18 at 23:21
1
$\begingroup$

If there exists some nontrivial solution $d$ to $Ax=0,x\geqslant 0$, then for any $x\in P$ we have for any $\varepsilon>0$ $$A(x+\varepsilon d)=Ax+\varepsilon Ad=Ax+0=Ax=b,$$ so that $x+\varepsilon d\in P$. It follows that $P$ is not bounded.

$\endgroup$
  • $\begingroup$ You have shown that $Ax=0$ has trivial solution, otherwise $P$ is unbounded. Could you help me to show the other way, I mean, show if $P$ is bounded, then $Ax=0$ has trivial solution? $\endgroup$ – Saeed Dec 9 '18 at 1:02
  • $\begingroup$ @Saeed: The above shows that if $P$ is bounded then only trivial solutions exist. What remains to be shown is that if there only trivial solutions then $P$ is bounded. $\endgroup$ – copper.hat Dec 9 '18 at 2:05
1
$\begingroup$

Suppose $P$ is not bounded. Then there are $x_n$ with $\|x_n\| \ge n$ such that $Ax_n =b, x_n \ge 0$.

Let $x'_n = {1 \over \|x_n\|} x_n$, and note that $A x'_n \to 0$ and $x'_n \ge 0$.

For some subsequence we have $x'_{n_k} \to x$ for some unit norm $x$. We see that $Ax = 0$ and $x \ge 0$, and so there is a non trivial solution.

$\endgroup$
  • $\begingroup$ I understand that $x'_n$ is a bounded sequence so it has a convergent subsequence, say $x''_n$ that converges. But I do not understand why you are using $x'_n$ instead of $x''_n$? $\endgroup$ – Saeed Dec 9 '18 at 4:26
  • $\begingroup$ The notation $x_{n_k}$ means a subsequence of $x_n$. (I had a typo.) $\endgroup$ – copper.hat Dec 9 '18 at 4:52

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