How to check whether a convex polyhedron is contained in another convex polyhedron?
Clash Royale CLAN TAG#URR8PPP
up vote
5
down vote
favorite
Suppose we have two convex polyhedra
$$P_1=xin mathbbR^n mid A_1 x geq b_1 $$
$$P_2=xin mathbbR^n mid A_2 x geq b_2 $$
Is there a way to check whether $P_1 subseteq P_2$? I was hoping that this can be done by solving some linear program. Is this possible?
convex-analysis convex-optimization linear-programming polyhedra polytopes
edited Jul 25 '17 at 22:52
Rodrigo de Azevedo
12.6k41751
asked Jun 29 '15 at 14:02
Tony
20129
add a comment |Â
up vote
5
down vote
favorite
Suppose we have two convex polyhedra
$$P_1=xin mathbbR^n mid A_1 x geq b_1 $$
$$P_2=xin mathbbR^n mid A_2 x geq b_2 $$
Is there a way to check whether $P_1 subseteq P_2$? I was hoping that this can be done by solving some linear program. Is this possible?
convex-analysis convex-optimization linear-programming polyhedra polytopes
edited Jul 25 '17 at 22:52
Rodrigo de Azevedo
12.6k41751
asked Jun 29 '15 at 14:02
Tony
20129
If you want to show that $P_1 subset P_2$, you have to show that $forall x in P_1 colon A_2 x geq b_2$
– aGer
Jun 29 '15 at 14:21
I wonder if you could do something with minkowski sums and minkowski portal refinement (MPR / Xenocollide) or GJK?
– Alan Wolfe
Jun 29 '15 at 16:39
@aGer I'm trying to do that by coming up with a general method using something like Farkas lemma, but no success so far. :-(
– Tony
Jun 29 '15 at 21:33
1
What's interesting is that there is something called the S-procedure that does something every similar to this for quadratic forms. That suggests it should be possible for affine forms, but I'll be darned if I can figure out how.
– Michael Grant
Jun 30 '15 at 2:04
What @aGer is proposing is possible, see my answer to this question.
– LinAlg
Jan 14 '17 at 15:04
add a comment |Â
up vote
5
down vote
favorite
up vote
5
down vote
favorite
Suppose we have two convex polyhedra
$$P_1=xin mathbbR^n mid A_1 x geq b_1 $$
$$P_2=xin mathbbR^n mid A_2 x geq b_2 $$
Is there a way to check whether $P_1 subseteq P_2$? I was hoping that this can be done by solving some linear program. Is this possible?
convex-analysis convex-optimization linear-programming polyhedra polytopes
edited Jul 25 '17 at 22:52
Rodrigo de Azevedo
12.6k41751
asked Jun 29 '15 at 14:02
Tony
20129
Suppose we have two convex polyhedra
$$P_1=xin mathbbR^n mid A_1 x geq b_1 $$
$$P_2=xin mathbbR^n mid A_2 x geq b_2 $$
Is there a way to check whether $P_1 subseteq P_2$? I was hoping that this can be done by solving some linear program. Is this possible?
convex-analysis convex-optimization linear-programming polyhedra polytopes
edited Jul 25 '17 at 22:52
Rodrigo de Azevedo
12.6k41751
asked Jun 29 '15 at 14:02
Tony
20129
edited Jul 25 '17 at 22:52
Rodrigo de Azevedo
12.6k41751
edited Jul 25 '17 at 22:52
Rodrigo de Azevedo
12.6k41751
edited Jul 25 '17 at 22:52
Rodrigo de Azevedo
12.6k41751
12.6k41751
asked Jun 29 '15 at 14:02
Tony
20129
asked Jun 29 '15 at 14:02
Tony
20129
asked Jun 29 '15 at 14:02
Tony
20129
20129
If you want to show that $P_1 subset P_2$, you have to show that $forall x in P_1 colon A_2 x geq b_2$
– aGer
Jun 29 '15 at 14:21
I wonder if you could do something with minkowski sums and minkowski portal refinement (MPR / Xenocollide) or GJK?
– Alan Wolfe
Jun 29 '15 at 16:39
@aGer I'm trying to do that by coming up with a general method using something like Farkas lemma, but no success so far. :-(
– Tony
Jun 29 '15 at 21:33
1
What's interesting is that there is something called the S-procedure that does something every similar to this for quadratic forms. That suggests it should be possible for affine forms, but I'll be darned if I can figure out how.
– Michael Grant
Jun 30 '15 at 2:04
What @aGer is proposing is possible, see my answer to this question.
– LinAlg
Jan 14 '17 at 15:04
add a comment |Â
If you want to show that $P_1 subset P_2$, you have to show that $forall x in P_1 colon A_2 x geq b_2$
– aGer
Jun 29 '15 at 14:21
I wonder if you could do something with minkowski sums and minkowski portal refinement (MPR / Xenocollide) or GJK?
– Alan Wolfe
Jun 29 '15 at 16:39
@aGer I'm trying to do that by coming up with a general method using something like Farkas lemma, but no success so far. :-(
– Tony
Jun 29 '15 at 21:33
1
What's interesting is that there is something called the S-procedure that does something every similar to this for quadratic forms. That suggests it should be possible for affine forms, but I'll be darned if I can figure out how.
– Michael Grant
Jun 30 '15 at 2:04
What @aGer is proposing is possible, see my answer to this question.
– LinAlg
Jan 14 '17 at 15:04
If you want to show that $P_1 subset P_2$, you have to show that $forall x in P_1 colon A_2 x geq b_2$
– aGer
Jun 29 '15 at 14:21
If you want to show that $P_1 subset P_2$, you have to show that $forall x in P_1 colon A_2 x geq b_2$
– aGer
Jun 29 '15 at 14:21
I wonder if you could do something with minkowski sums and minkowski portal refinement (MPR / Xenocollide) or GJK?
– Alan Wolfe
Jun 29 '15 at 16:39
I wonder if you could do something with minkowski sums and minkowski portal refinement (MPR / Xenocollide) or GJK?
– Alan Wolfe
Jun 29 '15 at 16:39
@aGer I'm trying to do that by coming up with a general method using something like Farkas lemma, but no success so far. :-(
– Tony
Jun 29 '15 at 21:33
@aGer I'm trying to do that by coming up with a general method using something like Farkas lemma, but no success so far. :-(
– Tony
Jun 29 '15 at 21:33
1
1
What's interesting is that there is something called the S-procedure that does something every similar to this for quadratic forms. That suggests it should be possible for affine forms, but I'll be darned if I can figure out how.
– Michael Grant
Jun 30 '15 at 2:04
What's interesting is that there is something called the S-procedure that does something every similar to this for quadratic forms. That suggests it should be possible for affine forms, but I'll be darned if I can figure out how.
– Michael Grant
Jun 30 '15 at 2:04
What @aGer is proposing is possible, see my answer to this question.
– LinAlg
Jan 14 '17 at 15:04
What @aGer is proposing is possible, see my answer to this question.
– LinAlg
Jan 14 '17 at 15:04
add a comment |Â
3 Answers
3
active
oldest
votes
up vote
3
down vote
accepted
Well, here's one way to do it. Let $A_i2$ and $b_i2$ denote the $i$th row of $A_2$ and $i$th element of $b_2$, respectively. Then solve $m$ linear programs:
$$beginarrayll
textminimize & A_i2^T x - b_i2 \
textsubject to & A_1 x geq b_1
endarray qquad i=1,2,dots, m$$
If any of these have a negative objective, including possibly $-infty$, then $P_1notsubseteq P_2$. It's not cheap, I grant, but it works.
answered Jun 30 '15 at 4:02
Michael Grant
14.6k11743
Would the problem be easier if, instead of writing $P_2=x mid A_2 x =b_2, x geq 0 $, I know $P_2$ is a cone with known extreme rays: $P_2= R v mid v geq 0 $?
– Tony
Jun 30 '15 at 14:14
I don't think so, no. Unfortunately I don't think this is a convex problem. We are fortunate that it can be done this way.
– Michael Grant
Jun 30 '15 at 14:17
add a comment |Â
up vote
2
down vote
A not so elegant way would be to determine the vertices of $P_1$ and plug them into the constraints for $P_2$, if each vertex satisfies the $P_2$ constraints, then by convexity, so does the entire polyhedron.
As pointed out by @D.W., this approach will typically be very slow, as the number of vertices increases rapidly with the number of edges. Michael Grant's approach, as stated above and accepted, has faster running time.
That will work, except that finding the vertices given the faces is not straightforward.
– Michael Grant
Jun 30 '15 at 2:01
Simplex doesn't attempt enumerate all the vertices, actually... indeed it would be quite bad if it did!
– Michael Grant
Jun 30 '15 at 2:48
@Tony here's a paper to popular algorithm for vertex enumeration. This general problem is classified as NP-complete, so its not going to come cheap: link.springer.com/article/10.1007%2FBF02293050
– user237392
Jun 30 '15 at 4:09
1
@Bey, well, if we must discuss the prior comments: no, vertex enumeration is not NP-complete. It's not even a NP-problem. NP is a class of decision problems; and NP-complete is a subset of NP. Vertex enumeration is not a decision problem. Moreover, vertex enumeration unconditionally takes exponential time; even if we discover P=NP, vertex enumeration will still take exponential time, as the number of vertices to enumerate can be exponential. The best path forward would be to edit the answer to point out these limitations. Shall I suggest an edit?
– D.W.
Aug 26 '16 at 5:32
1
The more efficient algorithm has already been posted by Michael Grant; its running time is guaranteed to be polynomial if you use the right LP solver, and will typically be efficient in practice. I don't have anything better than that.
– D.W.
Aug 26 '16 at 14:41
 |Â
show 8 more comments
up vote
1
down vote
This is equivalent to the feasibility of the following linear constraints:
$$
Lambda A_2 = A_1, Lambda b_2 ge b_1,
$$
where $Lambda$ is a matrix with non-negative entries. The proof follows from the dual of linear programs that Michael mentioned.
answered Aug 23 at 2:36
sadra
111
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
accepted
Well, here's one way to do it. Let $A_i2$ and $b_i2$ denote the $i$th row of $A_2$ and $i$th element of $b_2$, respectively. Then solve $m$ linear programs:
$$beginarrayll
textminimize & A_i2^T x - b_i2 \
textsubject to & A_1 x geq b_1
endarray qquad i=1,2,dots, m$$
If any of these have a negative objective, including possibly $-infty$, then $P_1notsubseteq P_2$. It's not cheap, I grant, but it works.
answered Jun 30 '15 at 4:02
Michael Grant
14.6k11743
Would the problem be easier if, instead of writing $P_2=x mid A_2 x =b_2, x geq 0 $, I know $P_2$ is a cone with known extreme rays: $P_2= R v mid v geq 0 $?
– Tony
Jun 30 '15 at 14:14
I don't think so, no. Unfortunately I don't think this is a convex problem. We are fortunate that it can be done this way.
– Michael Grant
Jun 30 '15 at 14:17
add a comment |Â
up vote
3
down vote
accepted
Well, here's one way to do it. Let $A_i2$ and $b_i2$ denote the $i$th row of $A_2$ and $i$th element of $b_2$, respectively. Then solve $m$ linear programs:
$$beginarrayll
textminimize & A_i2^T x - b_i2 \
textsubject to & A_1 x geq b_1
endarray qquad i=1,2,dots, m$$
If any of these have a negative objective, including possibly $-infty$, then $P_1notsubseteq P_2$. It's not cheap, I grant, but it works.
answered Jun 30 '15 at 4:02
Michael Grant
14.6k11743
Would the problem be easier if, instead of writing $P_2=x mid A_2 x =b_2, x geq 0 $, I know $P_2$ is a cone with known extreme rays: $P_2= R v mid v geq 0 $?
– Tony
Jun 30 '15 at 14:14
I don't think so, no. Unfortunately I don't think this is a convex problem. We are fortunate that it can be done this way.
– Michael Grant
Jun 30 '15 at 14:17
add a comment |Â
up vote
3
down vote
accepted
up vote
3
down vote
accepted
Well, here's one way to do it. Let $A_i2$ and $b_i2$ denote the $i$th row of $A_2$ and $i$th element of $b_2$, respectively. Then solve $m$ linear programs:
$$beginarrayll
textminimize & A_i2^T x - b_i2 \
textsubject to & A_1 x geq b_1
endarray qquad i=1,2,dots, m$$
If any of these have a negative objective, including possibly $-infty$, then $P_1notsubseteq P_2$. It's not cheap, I grant, but it works.
answered Jun 30 '15 at 4:02
Michael Grant
14.6k11743
Well, here's one way to do it. Let $A_i2$ and $b_i2$ denote the $i$th row of $A_2$ and $i$th element of $b_2$, respectively. Then solve $m$ linear programs:
$$beginarrayll
textminimize & A_i2^T x - b_i2 \
textsubject to & A_1 x geq b_1
endarray qquad i=1,2,dots, m$$
If any of these have a negative objective, including possibly $-infty$, then $P_1notsubseteq P_2$. It's not cheap, I grant, but it works.
answered Jun 30 '15 at 4:02
Michael Grant
14.6k11743
answered Jun 30 '15 at 4:02
Michael Grant
14.6k11743
answered Jun 30 '15 at 4:02
Michael Grant
14.6k11743
answered Jun 30 '15 at 4:02
Michael Grant
14.6k11743
14.6k11743
Would the problem be easier if, instead of writing $P_2=x mid A_2 x =b_2, x geq 0 $, I know $P_2$ is a cone with known extreme rays: $P_2= R v mid v geq 0 $?
– Tony
Jun 30 '15 at 14:14
I don't think so, no. Unfortunately I don't think this is a convex problem. We are fortunate that it can be done this way.
– Michael Grant
Jun 30 '15 at 14:17
add a comment |Â
Would the problem be easier if, instead of writing $P_2=x mid A_2 x =b_2, x geq 0 $, I know $P_2$ is a cone with known extreme rays: $P_2= R v mid v geq 0 $?
– Tony
Jun 30 '15 at 14:14
I don't think so, no. Unfortunately I don't think this is a convex problem. We are fortunate that it can be done this way.
– Michael Grant
Jun 30 '15 at 14:17
Would the problem be easier if, instead of writing $P_2=x mid A_2 x =b_2, x geq 0 $, I know $P_2$ is a cone with known extreme rays: $P_2= R v mid v geq 0 $?
– Tony
Jun 30 '15 at 14:14
Would the problem be easier if, instead of writing $P_2=x mid A_2 x =b_2, x geq 0 $, I know $P_2$ is a cone with known extreme rays: $P_2= R v mid v geq 0 $?
– Tony
Jun 30 '15 at 14:14
I don't think so, no. Unfortunately I don't think this is a convex problem. We are fortunate that it can be done this way.
– Michael Grant
Jun 30 '15 at 14:17
I don't think so, no. Unfortunately I don't think this is a convex problem. We are fortunate that it can be done this way.
– Michael Grant
Jun 30 '15 at 14:17
add a comment |Â
up vote
2
down vote
A not so elegant way would be to determine the vertices of $P_1$ and plug them into the constraints for $P_2$, if each vertex satisfies the $P_2$ constraints, then by convexity, so does the entire polyhedron.
As pointed out by @D.W., this approach will typically be very slow, as the number of vertices increases rapidly with the number of edges. Michael Grant's approach, as stated above and accepted, has faster running time.
That will work, except that finding the vertices given the faces is not straightforward.
– Michael Grant
Jun 30 '15 at 2:01
Simplex doesn't attempt enumerate all the vertices, actually... indeed it would be quite bad if it did!
– Michael Grant
Jun 30 '15 at 2:48
@Tony here's a paper to popular algorithm for vertex enumeration. This general problem is classified as NP-complete, so its not going to come cheap: link.springer.com/article/10.1007%2FBF02293050
– user237392
Jun 30 '15 at 4:09
1
@Bey, well, if we must discuss the prior comments: no, vertex enumeration is not NP-complete. It's not even a NP-problem. NP is a class of decision problems; and NP-complete is a subset of NP. Vertex enumeration is not a decision problem. Moreover, vertex enumeration unconditionally takes exponential time; even if we discover P=NP, vertex enumeration will still take exponential time, as the number of vertices to enumerate can be exponential. The best path forward would be to edit the answer to point out these limitations. Shall I suggest an edit?
– D.W.
Aug 26 '16 at 5:32
1
The more efficient algorithm has already been posted by Michael Grant; its running time is guaranteed to be polynomial if you use the right LP solver, and will typically be efficient in practice. I don't have anything better than that.
– D.W.
Aug 26 '16 at 14:41
 |Â
show 8 more comments
up vote
2
down vote
A not so elegant way would be to determine the vertices of $P_1$ and plug them into the constraints for $P_2$, if each vertex satisfies the $P_2$ constraints, then by convexity, so does the entire polyhedron.
As pointed out by @D.W., this approach will typically be very slow, as the number of vertices increases rapidly with the number of edges. Michael Grant's approach, as stated above and accepted, has faster running time.
That will work, except that finding the vertices given the faces is not straightforward.
– Michael Grant
Jun 30 '15 at 2:01
Simplex doesn't attempt enumerate all the vertices, actually... indeed it would be quite bad if it did!
– Michael Grant
Jun 30 '15 at 2:48
@Tony here's a paper to popular algorithm for vertex enumeration. This general problem is classified as NP-complete, so its not going to come cheap: link.springer.com/article/10.1007%2FBF02293050
– user237392
Jun 30 '15 at 4:09
1
@Bey, well, if we must discuss the prior comments: no, vertex enumeration is not NP-complete. It's not even a NP-problem. NP is a class of decision problems; and NP-complete is a subset of NP. Vertex enumeration is not a decision problem. Moreover, vertex enumeration unconditionally takes exponential time; even if we discover P=NP, vertex enumeration will still take exponential time, as the number of vertices to enumerate can be exponential. The best path forward would be to edit the answer to point out these limitations. Shall I suggest an edit?
– D.W.
Aug 26 '16 at 5:32
1
The more efficient algorithm has already been posted by Michael Grant; its running time is guaranteed to be polynomial if you use the right LP solver, and will typically be efficient in practice. I don't have anything better than that.
– D.W.
Aug 26 '16 at 14:41
 |Â
show 8 more comments
up vote
2
down vote
up vote
2
down vote
A not so elegant way would be to determine the vertices of $P_1$ and plug them into the constraints for $P_2$, if each vertex satisfies the $P_2$ constraints, then by convexity, so does the entire polyhedron.
As pointed out by @D.W., this approach will typically be very slow, as the number of vertices increases rapidly with the number of edges. Michael Grant's approach, as stated above and accepted, has faster running time.
A not so elegant way would be to determine the vertices of $P_1$ and plug them into the constraints for $P_2$, if each vertex satisfies the $P_2$ constraints, then by convexity, so does the entire polyhedron.
As pointed out by @D.W., this approach will typically be very slow, as the number of vertices increases rapidly with the number of edges. Michael Grant's approach, as stated above and accepted, has faster running time.
edited Aug 26 '16 at 16:53
answered Jun 29 '15 at 16:29
user237392
That will work, except that finding the vertices given the faces is not straightforward.
– Michael Grant
Jun 30 '15 at 2:01
Simplex doesn't attempt enumerate all the vertices, actually... indeed it would be quite bad if it did!
– Michael Grant
Jun 30 '15 at 2:48
@Tony here's a paper to popular algorithm for vertex enumeration. This general problem is classified as NP-complete, so its not going to come cheap: link.springer.com/article/10.1007%2FBF02293050
– user237392
Jun 30 '15 at 4:09
1
@Bey, well, if we must discuss the prior comments: no, vertex enumeration is not NP-complete. It's not even a NP-problem. NP is a class of decision problems; and NP-complete is a subset of NP. Vertex enumeration is not a decision problem. Moreover, vertex enumeration unconditionally takes exponential time; even if we discover P=NP, vertex enumeration will still take exponential time, as the number of vertices to enumerate can be exponential. The best path forward would be to edit the answer to point out these limitations. Shall I suggest an edit?
– D.W.
Aug 26 '16 at 5:32
1
The more efficient algorithm has already been posted by Michael Grant; its running time is guaranteed to be polynomial if you use the right LP solver, and will typically be efficient in practice. I don't have anything better than that.
– D.W.
Aug 26 '16 at 14:41
 |Â
show 8 more comments
That will work, except that finding the vertices given the faces is not straightforward.
– Michael Grant
Jun 30 '15 at 2:01
Simplex doesn't attempt enumerate all the vertices, actually... indeed it would be quite bad if it did!
– Michael Grant
Jun 30 '15 at 2:48
@Tony here's a paper to popular algorithm for vertex enumeration. This general problem is classified as NP-complete, so its not going to come cheap: link.springer.com/article/10.1007%2FBF02293050
– user237392
Jun 30 '15 at 4:09
1
@Bey, well, if we must discuss the prior comments: no, vertex enumeration is not NP-complete. It's not even a NP-problem. NP is a class of decision problems; and NP-complete is a subset of NP. Vertex enumeration is not a decision problem. Moreover, vertex enumeration unconditionally takes exponential time; even if we discover P=NP, vertex enumeration will still take exponential time, as the number of vertices to enumerate can be exponential. The best path forward would be to edit the answer to point out these limitations. Shall I suggest an edit?
– D.W.
Aug 26 '16 at 5:32
1
The more efficient algorithm has already been posted by Michael Grant; its running time is guaranteed to be polynomial if you use the right LP solver, and will typically be efficient in practice. I don't have anything better than that.
– D.W.
Aug 26 '16 at 14:41
That will work, except that finding the vertices given the faces is not straightforward.
– Michael Grant
Jun 30 '15 at 2:01
That will work, except that finding the vertices given the faces is not straightforward.
– Michael Grant
Jun 30 '15 at 2:01
Simplex doesn't attempt enumerate all the vertices, actually... indeed it would be quite bad if it did!
– Michael Grant
Jun 30 '15 at 2:48
Simplex doesn't attempt enumerate all the vertices, actually... indeed it would be quite bad if it did!
– Michael Grant
Jun 30 '15 at 2:48
@Tony here's a paper to popular algorithm for vertex enumeration. This general problem is classified as NP-complete, so its not going to come cheap: link.springer.com/article/10.1007%2FBF02293050
– user237392
Jun 30 '15 at 4:09
@Tony here's a paper to popular algorithm for vertex enumeration. This general problem is classified as NP-complete, so its not going to come cheap: link.springer.com/article/10.1007%2FBF02293050
– user237392
Jun 30 '15 at 4:09
1
1
@Bey, well, if we must discuss the prior comments: no, vertex enumeration is not NP-complete. It's not even a NP-problem. NP is a class of decision problems; and NP-complete is a subset of NP. Vertex enumeration is not a decision problem. Moreover, vertex enumeration unconditionally takes exponential time; even if we discover P=NP, vertex enumeration will still take exponential time, as the number of vertices to enumerate can be exponential. The best path forward would be to edit the answer to point out these limitations. Shall I suggest an edit?
– D.W.
Aug 26 '16 at 5:32
@Bey, well, if we must discuss the prior comments: no, vertex enumeration is not NP-complete. It's not even a NP-problem. NP is a class of decision problems; and NP-complete is a subset of NP. Vertex enumeration is not a decision problem. Moreover, vertex enumeration unconditionally takes exponential time; even if we discover P=NP, vertex enumeration will still take exponential time, as the number of vertices to enumerate can be exponential. The best path forward would be to edit the answer to point out these limitations. Shall I suggest an edit?
– D.W.
Aug 26 '16 at 5:32
1
1
The more efficient algorithm has already been posted by Michael Grant; its running time is guaranteed to be polynomial if you use the right LP solver, and will typically be efficient in practice. I don't have anything better than that.
– D.W.
Aug 26 '16 at 14:41
The more efficient algorithm has already been posted by Michael Grant; its running time is guaranteed to be polynomial if you use the right LP solver, and will typically be efficient in practice. I don't have anything better than that.
– D.W.
Aug 26 '16 at 14:41
 |Â
show 8 more comments
up vote
1
down vote
This is equivalent to the feasibility of the following linear constraints:
$$
Lambda A_2 = A_1, Lambda b_2 ge b_1,
$$
where $Lambda$ is a matrix with non-negative entries. The proof follows from the dual of linear programs that Michael mentioned.
answered Aug 23 at 2:36
sadra
111
add a comment |Â
up vote
1
down vote
This is equivalent to the feasibility of the following linear constraints:
$$
Lambda A_2 = A_1, Lambda b_2 ge b_1,
$$
where $Lambda$ is a matrix with non-negative entries. The proof follows from the dual of linear programs that Michael mentioned.
answered Aug 23 at 2:36
sadra
111
add a comment |Â
up vote
1
down vote
up vote
1
down vote
This is equivalent to the feasibility of the following linear constraints:
$$
Lambda A_2 = A_1, Lambda b_2 ge b_1,
$$
where $Lambda$ is a matrix with non-negative entries. The proof follows from the dual of linear programs that Michael mentioned.
answered Aug 23 at 2:36
sadra
111
This is equivalent to the feasibility of the following linear constraints:
$$
Lambda A_2 = A_1, Lambda b_2 ge b_1,
$$
where $Lambda$ is a matrix with non-negative entries. The proof follows from the dual of linear programs that Michael mentioned.
answered Aug 23 at 2:36
sadra
111
answered Aug 23 at 2:36
sadra
111
answered Aug 23 at 2:36
sadra
111
answered Aug 23 at 2:36
sadra
111
111
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1343280%2fhow-to-check-whether-a-convex-polyhedron-is-contained-in-another-convex-polyhedr%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
If you want to show that $P_1 subset P_2$, you have to show that $forall x in P_1 colon A_2 x geq b_2$
– aGer
Jun 29 '15 at 14:21
I wonder if you could do something with minkowski sums and minkowski portal refinement (MPR / Xenocollide) or GJK?
– Alan Wolfe
Jun 29 '15 at 16:39
@aGer I'm trying to do that by coming up with a general method using something like Farkas lemma, but no success so far. :-(
– Tony
Jun 29 '15 at 21:33
1
What's interesting is that there is something called the S-procedure that does something every similar to this for quadratic forms. That suggests it should be possible for affine forms, but I'll be darned if I can figure out how.
– Michael Grant
Jun 30 '15 at 2:04
What @aGer is proposing is possible, see my answer to this question.
– LinAlg
Jan 14 '17 at 15:04