Finding containment between convex polytopes

Question

Given 2 polytopes, either by their H-representations: $p_1: Ax\le b, p_2: Cx\le d$, where $b,d$ are real-valued vectors, $A,C$ are real-valued matrices, or by their V-representations: $p_1 = conv(p_{11}, p_{12}, ..., p_{1n}), p_2 = conv(p_{21}, p_{22}, ..., p_{2m})$, I want to find out if $p_1 \subseteq p_2$. What would be the best approach to go about it? Currently, the best solution I've managed to come up with myself, is given V-representation, check if every vertex of $p_1$ is in the convex hull of $p_2$, and that takes $n$ linear programs.

I can decide if I want it the polytopes to be in V-representation or H-representation, but if the solution will take around the same running time - I'd rather it be in V-representation. If not, that's not a big deal.

I've found solutions such as Is it possible to check polytope containment by only checking the feasibility of an LP? which claim to succeed doing so, while using only one linear program, given H-representation. I couldn't understand this solution though: I've tried proving it myself, but I can't understand some important things about it:

1. Why is it using equality in $C^Ty^i = a^i$, instead of $C^Ty^i \geq a^i$? Is it because according to strong duality, the solution to the maximization problem is equal to the solution of the minimization problem, if a solution exists?
2. How is it one linear program, if I need to check the existence of at least one $i$ which would give a none empty result? Isn't the amount of linear programs dependent on the amount of $i$s needed to be checked?
3. Why did they add the constraint of $y^i \geq 0$? I think I understand the intuition behind it, they wanted to make it a bounded problem, but doesn't it mess with the strong duality theorem, by adding another constraint?

Answer 1

Managed to solve it, if anyone comes across this and needs the solution: Let $P_1$ be a polytope defined by the constraints $Cx≤d$, where $C$ is a $m_1×n$ real-valued matrix, $x$ is our real-valued variable vector, and $d$ is a $m_1$-dimensional real-valued column vector.

Let $P_2$ be a polytope defined by the constraints $Ax≤b$, where $A$ is a $m_2×n$ real-valued matrix, $x$ is our real-valued variable vector, and $b$ is a $m_2$-dimensional real-valued column vector. We want to check if $P_1⊆P_2$.

$↔ ∀x∈P_1 (x∈P_2 )$

$↔ ∀x∈P_1 (∀_{1≤i≤m_2} (∑_{j=1}^{n}A_{ij}x_{j}≤b_{i} ))$ where $A_i$ is the $i$th row vector in $A$, and $b_{i}$ is the $i$th element in $b$.

$↔∀_{1≤i≤m_2} ([max⁡∑_{j=1}^{n}A_{ij}x_{j},s.t. ∀_{1≤k≤m_1}(∑_{j=1}^{n}C_{kj}x_{j}≤d_{k})]≤b_{i})$

Using the strong duality theorem, if the solution to the maximization problem exists, then it is equal to the solution of the dual problem. Hence, if the solution exists:

$↔∀_{1≤i≤m_2} ([min⁡∑_{k=1}^{m_1}d_{k}y_{k},s.t. ∀_{1≤j≤n}(∑_{a=1}^{n}C_{ak} y_{a}≥A_{ij})]≤b_i)$

This inequality holds for the minimum value $\iff$ there exists a value it holds for. Hence:

$↔∀_{1≤i≤m_2} (∃y(∀_{1≤j≤n} (∑_{a=1}^{n}C_{ak}y_{a}≥A_{ij}) ∧ ∑_{k=1}^{m_1}d_{k}y_{k}≤b_{i}))$

Now this problem can be solved via one large LP, where the solution vector of the problem will be of size $m_{2}n$, and every $n$ variables will represent one $i$ that we are checking. It's possible because we need to check if every $i$ has a feasible solution, and since for every $i$, the check needs to be done is independent from other $i$s, it's possible to either be done parallelly or in a single large LP.

Hope it can serve someone else well too :)

Answer 2

Also managed to solve it in V-representation if anyone needs it:

Let $P_1$ be a polytope defined by his vertices $p_{11},p_{12},…,p_{1n}$.

Let $P_2$ be a polytope defined by his vertices $p_{21},p_{22},…,p_{2m}$.

We want to check if $P_1 \subseteq P_2$. Note, that due to convexity, $(\{p_{11}, p_{12}, ..., p_{1n}\} \subseteq P_2) \rightarrow P_1 \subseteq P_2$. So, we'll check that instead: $\forall_{v\in\{p_{11}, p_{12}, ..., p_{1n}\}}(\exists \alpha ((\sum^{m}_{j=1} \alpha_{j} = 1)\wedge(\forall_{1<=j<=m}(\alpha_j>=0))\wedge(\sum^{m}_{j=1}\alpha_jp_{2j}=v)))$

This is due the definition of a convex combination.

This can be done in a single LP, with $nm$ decision variables, where every $m$ variables will represent feasibility for a single vertex in $\{p_{11}, p_{12}, ..., p_{1n}\}$. We need to check that there exists $\alpha$ for every $v\in\{p_{11}, p_{12}, ..., p_{1n}\}$ independently, so it is able to be either done parallelly in $n$ different LPs, or a single large one.