Conditions on boundedness of a polyhedron which makes it polytope. [closed]
$begingroup$
Let $P={x in mathbb{R}^n mid Ax=b, xgeq 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, ,, xgeq 0$ has trivial solution $x=0$ only.
convex-analysis polyhedra
asked Dec 8 '18 at 22:56
SaeedSaeed
1,036310
$endgroup$
closed as off-topic by amWhy, 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." – amWhy, Shailesh, Brian Borchers, user10354138, Cesareo
If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
$begingroup$
Let $P={x in mathbb{R}^n mid Ax=b, xgeq 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, ,, xgeq 0$ has trivial solution $x=0$ only.
convex-analysis polyhedra
asked Dec 8 '18 at 22:56
SaeedSaeed
1,036310
$endgroup$
closed as off-topic by amWhy, 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." – amWhy, 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
add a comment |
$begingroup$
Let $P={x in mathbb{R}^n mid Ax=b, xgeq 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, ,, xgeq 0$ has trivial solution $x=0$ only.
convex-analysis polyhedra
asked Dec 8 '18 at 22:56
SaeedSaeed
1,036310
$endgroup$
Let $P={x in mathbb{R}^n mid Ax=b, xgeq 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, ,, xgeq 0$ has trivial solution $x=0$ only.
convex-analysis polyhedra
convex-analysis polyhedra
asked Dec 8 '18 at 22:56
SaeedSaeed
1,036310
asked Dec 8 '18 at 22:56
SaeedSaeed
1,036310
asked Dec 8 '18 at 22:56
SaeedSaeed
1,036310
asked Dec 8 '18 at 22:56
SaeedSaeed
1,036310
asked Dec 8 '18 at 22:56
SaeedSaeed
1,036310
1,036310
closed as off-topic by amWhy, 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." – amWhy, Shailesh, Brian Borchers, user10354138, Cesareo
If this question can be reworded to fit the rules in the help center, please edit the question.
closed as off-topic by amWhy, 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." – amWhy, 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
add a comment |
$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
$begingroup$
What does $x ge 0$ mean? All coordinates $ge 0$?
$endgroup$
– Paul Frost
Dec 8 '18 at 23:13
$begingroup$
What does $x ge 0$ mean? All coordinates $ge 0$?
$endgroup$
– Paul Frost
Dec 8 '18 at 23:13
1
1
$begingroup$
It means each element of $x$ should be greater than zero.
$endgroup$
– Saeed
Dec 8 '18 at 23:21
$begingroup$
It means each element of $x$ should be greater than zero.
$endgroup$
– Saeed
Dec 8 '18 at 23:21
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
If there exists some nontrivial solution $d$ to $Ax=0,xgeqslant 0$, then for any $xin P$ we have for any $varepsilon>0$ $$A(x+varepsilon d)=Ax+varepsilon Ad=Ax+0=Ax=b,$$ so that $x+varepsilon din P$. It follows that $P$ is not bounded.
answered Dec 9 '18 at 0:17
Math1000Math1000
19.1k31745
$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
add a comment |
$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.
answered Dec 9 '18 at 2:12
copper.hatcopper.hat
127k559160
$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
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
If there exists some nontrivial solution $d$ to $Ax=0,xgeqslant 0$, then for any $xin P$ we have for any $varepsilon>0$ $$A(x+varepsilon d)=Ax+varepsilon Ad=Ax+0=Ax=b,$$ so that $x+varepsilon din P$. It follows that $P$ is not bounded.
answered Dec 9 '18 at 0:17
Math1000Math1000
19.1k31745
$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
add a comment |
$begingroup$
If there exists some nontrivial solution $d$ to $Ax=0,xgeqslant 0$, then for any $xin P$ we have for any $varepsilon>0$ $$A(x+varepsilon d)=Ax+varepsilon Ad=Ax+0=Ax=b,$$ so that $x+varepsilon din P$. It follows that $P$ is not bounded.
answered Dec 9 '18 at 0:17
Math1000Math1000
19.1k31745
$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
add a comment |
$begingroup$
If there exists some nontrivial solution $d$ to $Ax=0,xgeqslant 0$, then for any $xin P$ we have for any $varepsilon>0$ $$A(x+varepsilon d)=Ax+varepsilon Ad=Ax+0=Ax=b,$$ so that $x+varepsilon din P$. It follows that $P$ is not bounded.
answered Dec 9 '18 at 0:17
Math1000Math1000
19.1k31745
$endgroup$
If there exists some nontrivial solution $d$ to $Ax=0,xgeqslant 0$, then for any $xin P$ we have for any $varepsilon>0$ $$A(x+varepsilon d)=Ax+varepsilon Ad=Ax+0=Ax=b,$$ so that $x+varepsilon din P$. It follows that $P$ is not bounded.
answered Dec 9 '18 at 0:17
Math1000Math1000
19.1k31745
answered Dec 9 '18 at 0:17
Math1000Math1000
19.1k31745
answered Dec 9 '18 at 0:17
Math1000Math1000
19.1k31745
answered Dec 9 '18 at 0:17
Math1000Math1000
19.1k31745
19.1k31745
$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
add a comment |
$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
$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$
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
$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
add a comment |
$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.
answered Dec 9 '18 at 2:12
copper.hatcopper.hat
127k559160
$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
add a comment |
$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.
answered Dec 9 '18 at 2:12
copper.hatcopper.hat
127k559160
$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
add a comment |
$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.
answered Dec 9 '18 at 2:12
copper.hatcopper.hat
127k559160
$endgroup$
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.
answered Dec 9 '18 at 2:12
copper.hatcopper.hat
127k559160
edited Dec 9 '18 at 4:51
answered Dec 9 '18 at 2:12
copper.hatcopper.hat
127k559160
answered Dec 9 '18 at 2:12
copper.hatcopper.hat
127k559160
answered Dec 9 '18 at 2:12
copper.hatcopper.hat
127k559160
127k559160
$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
add a comment |
$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
$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$
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
$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
add a comment |
$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