How to check whether a convex polyhedron is contained in another convex polyhedron? 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?
 A: 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.
A: 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: 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.   
