How to check whether a convex polyhedron is contained in another convex polyhedron?

Question

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?

Answer 1

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.

Answer 2

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.