This is question 4.35 from Introduction to Linear Optimization by Bertsimas and Tsitsiklis.
The problem
Consider two non-empty polyhedra $P=\{\mathbf{x}\in\mathbb{R}^n\ |\ \mathbf{Ax}\leq\mathbf{b}\}$ and $Q=\{\mathbf{x}\in\mathbb{R}^n\ |\ \mathbf{Dx}\leq\mathbf{d}\}$.
(a) Devise a linear programming problem such that: if $P\cap Q\neq\varnothing$, it returns a point in $P\cap Q$; if $P\cap Q=\varnothing$, the linear programming problem is infeasible.
(b) Suppose that $P\cap Q$ is empty. Use the dual of the problem you have constructed in part (a) to show that there exists a vector $\mathbf{c}$ such that $\mathbf{c}^\text{T}\mathbf{x}<\mathbf{c}^\text{T}\mathbf{y}$ for all $\mathbf{x}\in P$ and $\mathbf{y}\in Q$.
Attempted solution
I think I have an answer for part (a):
$$ \begin{array}{rl} \text{max}\quad&\mathbf{0}^\text{T}\mathbf{x} \\ \text{s.t.}\quad&\mathbf{Ax}\leq\mathbf{b} \\ & \mathbf{Dx}\leq\mathbf{d} \end{array} $$
This seems to accomplish the requirements of part (a). I am stuck on part (b). The dual of the above linear program is
$$ \begin{array}{rl}\text{min}\quad&\mathbf{p}_1^\text{T}\mathbf{b}+\mathbf{p}_2^\text{T}\mathbf{d}\\\text{s.t.}\quad&\mathbf{p}_1^\text{T}\mathbf{A}+\mathbf{p}_2^\text{T}\mathbf{D}=\mathbf{0}^\text{T}\\ & \mathbf{p}_1,\mathbf{p}_2\geq\mathbf{0} \end{array} $$
If we assume the primal is infeasible (i.e. $P\cap Q=\varnothing$), then the dual is either infeasible or unbounded. Since $\mathbf{p}_1=\mathbf{0}$, $\mathbf{p}_2=\mathbf{0}$ is feasible for the dual, it must be unbounded. I think this might be a useful fact, but I can't see exactly how.
Geometrically, this question is very straightforward. But I'm struggling to come up with the algebra to show the existence of this $\mathbf{c}$.
Similar question
The question found here is similar, but I'm not interested in computing the separating hyperplane, just proving its existence.
Best Answer
(a) The linear program
\begin{array}{rl} \max &\mathbf{0}^\text{T}\mathbf{x} \\ \text{s.t.}&\mathbf{Ax}\leq\mathbf{b} \tag{P}\label{P}\\ & \mathbf{Dx}\leq\mathbf{d} \end{array}
suggested by the OP responds to the problem.
(b) Since $P \cap Q = \varnothing$, each of these two points satisfies exactly one of the two constraints in \eqref{P} (from the definition of $P$ and $Q$).
The OP's deduction is correct:
From the unboundedness of \eqref{D}, we deduce that for each $z \in \Bbb R$, there exists $\mathbf{p}_1,\mathbf{p}_2\geq\mathbf{0}$ such that $\mathbf{p}_1^\text{T}\mathbf{b}+\mathbf{p}_2^\text{T}\mathbf{d} \le z$. In particular, we fix $\epsilon > 0$ and take $z = -\epsilon$, so that $$\mathbf{p}_1^\text{T}\mathbf{b}+\mathbf{p}_2^\text{T}\mathbf{d} < 0 \tag{*} \label{*}.$$
For all ${\bf x} \in P$ and ${\bf y} \in Q$, we have (from the definition of $P$ and $Q$)
\begin{align} \mathbf{Ax} &\leq \mathbf{b} \tag{1}\label{1} \\ \mathbf{Dy} &\leq \mathbf{d} \tag{2}\label{2} \end{align}
Multiply $\mathbf{p}_1^\text{T}$ and $\mathbf{p}_2^\text{T}$ on both sides of \eqref{1} and \eqref{2} respectively. (We can do so since $\mathbf{p}_1 \ge {\bf 0}, \mathbf{p}_2 \ge {\bf 0}$.)
\begin{align} \mathbf{p}_1^\text{T}\mathbf{Ax} &\leq \mathbf{p}_1^\text{T}\mathbf{b} \tag{3}\label{3} \\ \mathbf{p}_2^\text{T}\mathbf{Dy} &\leq \mathbf{p}_2^\text{T}\mathbf{d} \tag{4}\label{4} \end{align}
Substitute the constraint in \eqref{D} into \eqref{4}.
$$(-\mathbf{p}_1^\text{T}\mathbf{A}){\bf y} \leq \mathbf{p}_2^\text{T}\mathbf{d} \tag{4'}\label{4'}$$
Add \eqref{3} and \eqref{4'}.
$$\mathbf{p}_1^\text{T}\mathbf{A} ({\bf x} - {\bf y}) \le \mathbf{p}_1^\text{T}\mathbf{b}+\mathbf{p}_2^\text{T}\mathbf{d} \stackrel{\eqref{*}}< 0 \tag{$\star$} \label{fin}$$
It's evident from \eqref{fin} that ${\bf c} = (\mathbf{p}_1^\text{T}\mathbf{A})^\text{T} = \mathbf{A}^\text{T} \mathbf{p}_1$ satisfies $$\mathbf{c}^\text{T}\mathbf{x}<\mathbf{c}^\text{T}\mathbf{y} \quad \forall \mathbf{x} \in P, \forall \mathbf{y} \in Q.$$