2
$\begingroup$

This is NOT a question about whether or not we can use LP to check polytope containment, which is already answered by existing posts on this website.

Suppose we have two convex polytopes in their H-representatations

$P_1=\{x\in \mathbb{R}^n \mid A_1 x \leq b_1 \}$ and $P_2=\{x\in \mathbb{R}^n \mid A_2 x \leq b_2 \}$

The answer to a previous post requires first solving an LP, and then checking the non-negativity of the decision variables, which is a two-step process.

I am wondering if there is a way to check whether $P_1 \subseteq P_2$ by only checking the feasibility of a single linear program (without rewriting $P_1$ into its V-representation)? If the answer is negative, is there an explanation using complexity theory?

$\endgroup$
8
$\begingroup$

The answer is affirmative. You want to verify $x \in P_2 \; \forall x \in P_1$. This is much like Robust Optimization, and the solution technique is the same. Let me write the constraints for $P_1$ as $Cx \leq d$ and for $P_2$ as $Ax \leq b$ for convenience. For each constraint in $P_2$, $(a^i)^T x \leq b_i$, we want to know if it is satisfied for all $x \in P_1$. This is equivalent to: $$ \left[ \max_{x : Cx \leq d} (a^i)^T x \right]\leq b_i \quad \forall i$$ Take the dual: $$ \left[ \min_{y^i \geq 0} \{ d^T y^i : C^T y^i = a^i \} \right]\leq b_i \quad \forall i$$ This inequality holds for the minimum iff it holds for at least one $y^i$: $$ d^T y^i \leq b_i, \; y^i \geq 0, \; C^T y^i = a^i \quad \forall i$$ Now $P_1 \subseteq P_2$ iff this polyhedron is non-empty. Note that you can check emptiness for each $i$ separately, which is perfectly parallelizable.

$\endgroup$
  • $\begingroup$ Aha! Nice work. $\endgroup$ – Michael Grant Jan 14 '17 at 14:54
  • $\begingroup$ @MichaelGrant Thanks. I guess I have to frame it now :) $\endgroup$ – LinAlg Jan 14 '17 at 14:56
  • $\begingroup$ Should you perhaps attach a comment to my other answer to point people to this? Obviously you commented on the question, but you didn't make it clear that this was a true alternative. $\endgroup$ – Michael Grant Jan 14 '17 at 15:03
  • $\begingroup$ Thanks a lot! Nice method. $\endgroup$ – Willem Hagemann Jan 26 '17 at 15:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.