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

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!

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$.

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.

• I think the equivalent system should be $A^Tx = B_i$, $a^Tx \geq b_i$, $x\geq 0$. And I would call this rather an application of Motzkins Transposition Theorem than Farkas' lemma. – Willem Hagemann Apr 10 '15 at 6:14