Past exam of the computer science course of the University of Oxford / 2019 / Algorithms / 2 / c

First suppose the stated nonnegative vectors $y,z$ exist. If $x\in P\cap Q$, multiply $Ax\le b$ by $y^T$ and $Cx\le d$ by $z^T$. Since $x\ge 0$ and $y^{T}A+z^{T}C\ge 0$, this gives the contradictionThus the certificate implies $P\cap Q=\varnothing$.

For the converse, putA common feasible point exists exactly when $Mx\le h$, $x\ge 0$. Introducing a nonnegative vector of slack variables $s$ makes this equivalent toIf this system is infeasible, the nonnegative-equations version of Farkas' lemma supplies an unrestricted vector $u$ such thatSplit $u=(y,z{)}^T$ according to the original two blocks of inequalities. The three conditions become $y,z\ge 0$, $y^{T}A+z^{T}C\ge 0$ and $y^{T}b+z^{T}d<0$, exactly the desired certificate. Both directions are proved. The role of $x\ge 0$ is essential: it is why the combined normal need only be nonnegative rather than zero.^[ref]