An algorithm to decide whether a polyhedron is a subset of another polyhedron

Question

I've encountered the following question which I am unable to solve:

Given

$$P = \{\vec x \mid A\vec x \geq \vec a\}$$

$$Q = \{\vec x \mid B\vec x \geq \vec b\}$$

where $P, Q \subseteq \mathbb R^n$, find an algorithm to determine whether $P \subseteq Q$.

This question has showed up under the "duality theorem" section, but I am unable to see how the dual programs helps here. Thanks in advance!

Answer 1

Well, I've solved it and apparently it really has nothing to do with the duality theorem.

The answer is as follows:

let $v_i'$ be i'th row in the matrix B, $i = 1, ..., n$.
for each i solve the linear program:

min $v_i'\vec x$
for $A\vec x \geq \vec a$

and check if the optimum for this program is $\geq b_i $. if the optimum is smaller than $b_i$ than the optimal solution $\vec x^*$ satisfies $A\vec x^*\geq a$, and also $B \vec x^* \ngeq \vec b$ and than $P \nsubseteq Q$.

If for every i the optimum is bigger than the corresponding $b_i$, than $A \vec x \geq \vec a$ $\to$ $B \vec x \geq \vec b$ and $P \subseteq Q$.

Answer 2

Just for completeness: the question is actually related with duality because can be solved using the Farkas lemma.

Indeed, $P\subseteq Q$ if and only for each $i$ here is no solution to the linear system of inequalities

$$Aa\geq a , B_i x<b_i,$$

otherwise said, if none of these system can be satisfied then the inclusion holds. By the Farkas lemma this is equivalent to show that the system

$A^T x= B_i, x\geq 0$

is feasible for each $i$, which can be done solving a single large LP. You may need some adjustements but the idea is that.