= Strict separation of disjoint linear polyhedra
{title2=$h^Tx\leq a<b\leq h^Ty$}
Nonempty disjoint <linear polyhedra> $P=\{x:Ax\leq b\}$ and $Q=\{y:Cy\leq d\}$ admit $h$ with a strictly positive separation gap. A phase-I <linear program> minimizing common constraint violation has positive attained optimum. Its <Lagrangian dual problem> gives nonnegative $\lambda,\mu$ with $A^T\lambda+C^T\mu=0$ and $\lambda^Tb+\mu^Td<0$. Then $h=A^T\lambda$ satisfies $h^Tx\leq\lambda^Tb<-\mu^Td\leq h^Ty$. The polyhedral hypothesis matters; arbitrary disjoint closed convex sets need not have a positive separation gap.
Back to article page
