Write a linear optimization problem to find a hyperplane that strictly separates two disjoint polyhedra. 
Let $P_{1}=\left\{x\:|\: Ax\leq b\right\}$ and $P_{2}=\left\{x\:|\: Cx\leq d\right\}$ be two disjoint polyhedra. Write a linear optimization problem to find a hyperplane that strictly separates $P_{1}$ of $P_{2}$.

 A: We consider the functions 
$$p^{*}_{1}(a):=\inf_{x\in P_{1}}a^{T}x \: \:\:\:\:  \mbox{ and } \: \:\:\:\: p^{*}_{2}(a):=\sup_{x\in P_{2}}a^{T}x.$$
If hyper-plane $a^{T}x=\alpha $ separates $P_{1}$ of $P_{2}$ then we should have $p^{*}_{1}(a)<\alpha < p^{*}_{2}(a)$, or what is the same, $0<\alpha -p^{*}_{2}(a)<p^{*}_{1}(a)-p^{*}_{2}(a)$.
Therefore, note that 
$$
 \begin{array}{rcl}
p^{*}_{1}(a)-p^{*}_{2}(a) &=& {\displaystyle \inf_{x\in P_{1}}a^{T}x-\sup_{x\in P_{2}}a^{T}x }= {\displaystyle \inf_{x\in P_{1}}a^{T}x+\inf_{x\in P_{2}}(-a^{T}x). }
\end{array}
$$
In addition, we note that $p^{*}_{1}(a)-p^{*}_{2}(a)$ is homogeneous, i.e., for all $t\geq 0$ we have 
$$p^{*}_{1}(ta)-p^{*}_{2}(ta)=t\left(p^{*}_{1}(a)-p^{*}_{2}(a)\right),$$ 
so $p^{*}_{1}(a)-p^{*}_{2}(a)$ could not be bounded unless  we restrict $a$ to a bounded set, in that sense, we assume $\left\|a\right\|_{1}\leq 1$. 
So, the objective is find $a$ and $\alpha$ such that it satisfies the initially described, finding $a$ can be formulated as:
$$
\begin{array}{ll}
\mbox{Maximize} & p^{*}_{1}(a)-p^{*}_{2}(a) \\
\mbox{subject to} & \left\|a\right\|_{1}\leq 1
\end{array}
$$
In this case $ a $ will be any of the values that allow reaching that maximum and $ \alpha $ can be taken as $\alpha=\left(p^{*}_{1}(a)+p^{*}_{2}(a)\right)/2$.
An equivalent formulation of the above problem is:
\begin{equation} \tag{1}
\begin{array}{ll}
\mbox{Minimize} & p^{*}_{2}(a)-p^{*}_{1}(a) \\
\mbox{subject to} & \left\|a\right\|_{1}\leq 1
\end{array}
\end{equation}
This last formulation is more convenient since it can be observed that 
$$p^{*}_{2}(a)-p^{*}_{1}(a)={\displaystyle \sup_{x\in P_{2}}a^{T}x-\inf_{x\in P_{1}}a^{T}x }={\displaystyle \sup_{x\in P_{2}}a^{T}x+\sup_{x\in P_{1}}(-a^{T}x) }$$
Which allows to infer that $p^{*}_{2}-p^{*}_{1}$ Is a convex function with respect to $ a $. Therefore, (1) is a convex optimization problem.
The idea is to formulate (1) linearly, for this purpose note that the functions $ p ^ {*} _ {1} $ and $ p ^ {*} _ {2} $ can be written as follows:
$$
\begin{array}{rll} p^{*}_{1}(a)=&\mbox{Minimize} & a^{T}x \\ & \mbox{Subject to } & Ax\leq b \end{array} \:\:\: \mbox{ and } \:\:\: \begin{array}{rll} p^{*}_{2}(a)=&\mbox{Minimize} & -a^{T}x \\ & \mbox{Subject to } & Cx\leq d \end{array}
$$
This is, $p^{*}_{1}(a)$ and $p_{2}^{*}(a)$ represent problems of linear optimization which in this case satisfies strong duality, the dual formulations of such problems are well known, therefore we get:
$$
\begin{array}{rll} p^{*}_{1}(a)=&\mbox{Maximize} & -b^{T}z_{1} \\ & \mbox{Subject to } & A^{T}z_{1}+a=0 \\ & & z_{1}\succcurlyeq 0 \end{array} \:\:\: \mbox{ and } \:\:\: \begin{array}{rll} p^{*}_{2}(a)=&\mbox{Maximize} & -d^{T}z_{2} \\ & \mbox{Subject to } & C^{T}z_{2}-a=0 \\ & & z_{2} \succcurlyeq 0 \end{array}.
$$
Therefore, (1) can be formulated as the following linear problem
\begin{equation}
\begin{array}{ll}
\mbox{Minimize} & -b^{T}z_{1}-d^{T}z_{2} \\
\mbox{subject to} & A^{T}z_{1}+a=0 \\ &  C^{T}z_{2}-a=0 \\ & z_{1}\succcurlyeq 0 \:\mbox{ y }\: z_{2}\succcurlyeq 0 \\ & \left\|a\right\|_{1}\leq 1
\end{array}
\end{equation}
Where we are minimizing with respect to $z_{1},z_{2}$ and $a$.
A: I prefer short, elegant solutions. Consider the hyperplane parameterized by $v \in \mathbb{R}^n$ and $w\in \mathbb{R}$. The problem of finding the maximally seperating hyperplane can be formulated as elegantly as
$$\max\{ t : v^T x \geq 1+t \; \forall x :Ax\leq b, \; v^T x  \leq 1-t \; \forall x:Cx\leq d\}.$$
Note that $w$ is fixed at $1$. With standard techniques from Robust Optimization, this can be reformulated as:
$$\max\{ t : -b^Ty \geq 1+t, \; A^Ty + v = 0, \; d^T z \leq 1-t, \; C^Tz = v, \; y \geq 0, z \geq 0 \}.$$
