Write a linear optimization problem to find a hyperplane that strictly separates two disjoint polyhedra.

Question

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}$.

Answer 1

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$.

Answer 2

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 \}.$$