How to determine whether a given convex polytope is contained in another given convex polytope?

Question

Given a tall matrix $A \in \mathbb{R}^{m \times n}$ (where $m > n$) and a vector $b\in\mathbb{R}^{m}$, we say that they define the set $$\mathcal{S} = \left\{x\in\mathbb{R}^n: Ax\le b\right\}$$ where the inequality is element-wise. We may also assume that this set is bounded. Suppose that I am given two pairs, $(A_1, b_1)$ and $(A_2, b_2)$. How can I check whether the set $\mathcal{S}_2$ is a subset of $\mathcal{S}_1$?

If it helps, we may assume that both $A_1$ and $A_2$ are lower triangular.

Answer 1

4. POLYTOPE CONTAINMENT
   
   Input: Polytope $P$ given in $\mathcal H$-description, polytope $Q$ given in $\mathcal V$-description
   
   Output: "Yes" if $P \subseteq Q$, "No" otherwise
   
   Status (general): co$\mathcal NP$-complete
   
   Status (fixed dim.): Polynomial time
   
   Freund and Orlin [20] proved that this problem is co$\mathcal NP$-complete. Note that the reverse question whether $Q \subseteq P$ is trivial. The questions where either both $P$ and $Q$ are given in $\mathcal H$-description or both in $\mathcal V$-description can be solved by linear programming (Problem 1), see Eaves and Freund [17]. For fixed dimension, one can enumerate all vertices of $\mathcal P$ in polynomial time (see Problem 1) and compare the descriptions of $P$ and $Q$ (after removing redundant points).

---

_{Source: Volker Kaibel, Marc E. Pfetsch, Some algorithmic problems in polytope theory, 2002.}