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 solving a seriesof LPs, and then checking the non-negativity of the objectives, 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$
0

1 Answer 1

10
$\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$
5
  • $\begingroup$ Aha! Nice work. $\endgroup$ Commented Jan 14, 2017 at 14:54
  • $\begingroup$ @MichaelGrant Thanks. I guess I have to frame it now :) $\endgroup$
    – LinAlg
    Commented Jan 14, 2017 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$ Commented Jan 14, 2017 at 15:03
  • $\begingroup$ Thanks a lot! Nice method. $\endgroup$ Commented Jan 26, 2017 at 15:01
  • $\begingroup$ As a reference, unless I misunderstood the paper, the proposed solution corresponds to the Farka's lemma variant proposed in (Eaves & Freund, 1982 doi.org/10.1007/BF01583784). The mapping from this answer to the paper's notation is: for $P_1$: C,d → A,b, then for each facet of $P_2$: $a^i,b_i$ → c,d (only one outer inequality is considered in that paper), and for the dual variable: $y^i$ → λ. $\endgroup$
    – Pierre H.
    Commented Jun 2, 2023 at 14:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .