5
$\begingroup$

Suppose we have two convex polyhedra

$$P_1=\{x\in \mathbb{R}^n \mid A_1 x \geq b_1 \}$$

$$P_2=\{x\in \mathbb{R}^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?

$\endgroup$
  • $\begingroup$ 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$ $\endgroup$ – aGer Jun 29 '15 at 14:21
  • $\begingroup$ I wonder if you could do something with minkowski sums and minkowski portal refinement (MPR / Xenocollide) or GJK? $\endgroup$ – Alan Wolfe Jun 29 '15 at 16:39
  • $\begingroup$ @aGer I'm trying to do that by coming up with a general method using something like Farkas lemma, but no success so far. :-( $\endgroup$ – Tony Jun 29 '15 at 21:33
  • 1
    $\begingroup$ 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. $\endgroup$ – Michael Grant Jun 30 '15 at 2:04
  • $\begingroup$ What @aGer is proposing is possible, see my answer to this question. $\endgroup$ – LinAlg Jan 14 '17 at 15:04
4
$\begingroup$

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: $$\begin{array}{ll} \text{minimize} & A_{i2}^T x - b_{i2} \\ \text{subject to} & A_1 x \geq b_1 \end{array} \qquad i=1,2,\dots, m$$ If any of these have a negative objective, including possibly $-\infty$, then $P_1\not\subseteq P_2$. It's not cheap, I grant, but it works.

$\endgroup$
  • $\begingroup$ 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 \}$? $\endgroup$ – Tony Jun 30 '15 at 14:14
  • $\begingroup$ 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. $\endgroup$ – Michael Grant Jun 30 '15 at 14:17
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ That will work, except that finding the vertices given the faces is not straightforward. $\endgroup$ – Michael Grant Jun 30 '15 at 2:01
  • $\begingroup$ Simplex doesn't attempt enumerate all the vertices, actually... indeed it would be quite bad if it did! $\endgroup$ – Michael Grant Jun 30 '15 at 2:48
  • $\begingroup$ @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 $\endgroup$ – user237392 Jun 30 '15 at 4:09
  • 1
    $\begingroup$ @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? $\endgroup$ – D.W. Aug 26 '16 at 5:32
  • 1
    $\begingroup$ 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. $\endgroup$ – D.W. Aug 26 '16 at 14:41
1
$\begingroup$

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.

$\endgroup$

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.