= Solution
First suppose the stated nonnegative <vectors> $y,z$ exist. If $x\in P\cap Q$, multiply $Ax\leq b$ by $y^T$ and $Cx\leq d$ by $z^T$. Since $x\geq0$ and $y^TA+z^TC\geq0$, this gives the contradiction
$$
0\leq(y^TA+z^TC)x\leq y^Tb+z^Td<0.
$$
Thus the certificate implies $P\cap Q=\varnothing$.
For the converse, put
$$
M=\begin{pmatrix}A\\C\end{pmatrix},\qquad h=\begin{pmatrix}b\\d\end{pmatrix}.
$$
A common <feasible point> exists exactly when $Mx\leq h$, $x\geq0$. Introducing a nonnegative <vector> of <slack variables> $s$ makes this equivalent to
$$
\begin{pmatrix}M&I\end{pmatrix}\begin{pmatrix}x\\s\end{pmatrix}=h,\qquad x,s\geq0.
$$
If this system is infeasible, the nonnegative-equations version of <Farkas' lemma> supplies an unrestricted <vector> $u$ such that
$$
M^Tu\geq0,\qquad I^Tu=u\geq0,\qquad h^Tu<0.
$$
Split $u=(y,z)^T$ according to the original two blocks of inequalities. The three conditions become \b[$y,z\geq0$, $y^TA+z^TC\geq0$ and $y^Tb+z^Td<0$], exactly the desired certificate. Both directions are proved. The role of $x\geq0$ is essential: it is why the combined normal need only be nonnegative rather than zero.<Convex Optimization by Stephen Boyd and Lieven Vandenberghe>[§5.8.3, printed pp. 261–262, linear-inequality alternatives and Farkas' lemma]{ref}
Back to article page
