Separation of polyhedra via Farkas' lemma

90 Views Asked by At

Let $A\in\mathbb{R}^{m_1\times n}$, $B\in\mathbb{R}^{m_2\times n}$, $a\in\mathbb{R}^{m_1}$, and $b\in\mathbb{R}^{m_2}$. Consider the intersection of an "open" polyhedron and another closed one: $$S=\{x\in\mathbb{R}^n:Ax<a\}\cap\{x\in\mathbb{R}^n:Bx\le b\}=\{x\in\mathbb{R}^n:Ax<a,Bx\le b\}.$$ The task is to show $S\ne\varnothing$ (i.e. the two polyhedra A,B intersect or, in other words, cannot be "separated") if and only if the following two statements hold for all $y\in\mathbb{R}^{m_1}_{\ge0}$ and $z\in\mathbb{R}^{m_2}_{\ge0}$:

1). If $y^tA+z^tB=0$, then $y^ta+z^tb\ge0$;

2). If $y^tA+z^tB=0$ and $y\ne0$, then $y^ta+z^tb>0$.

I've solved the "only if" part using Farkas' lemma:

A generalized Farkas' lemma: Let $A\in\mathbb{R}^{m_1\times n_1}$, $B\in\mathbb{R}^{m_1\times n_2}$, $C\in\mathbb{R}^{m_2\times n_1}$, $D\in\mathbb{R}^{m_2\times n_2}$, $a\in\mathbb{R}^{m_1}$, and $b\in\mathbb{R}^{m_2}$. Then precisely one of the following two systems is feasible:
i).\begin{align*} Ax+By&\le a \\ Cx+Dy&=b \\ x&\ge0 \end{align*} and
ii).\begin{align*} u^tA+v^tC&\ge0 \\ u^tB+v^tD&\ge0 \\ u&\ge0 \\ u^ta+v^tb&<0. \end{align*}

But I didn't manage to show the other direction (whose proof should be easy I expect). It seems that both directions shall share similar proofs, i.e. using some kind of "perturbation". And here are the details I've worked out:

Set $T=\{x\in\mathbb{R}^n:Ax\le a,Bx\le b\}$. Using Farkas' lemma, precisely one of the following two systems is feasible: \begin{align*} Ax&\le a \\ I_{m_2}\mathbb{1}_\varepsilon+Bx&=b \\ \mathbb{1}_\varepsilon&\ge0 \end{align*} and \begin{align*} z^tI_{m_2}&\ge0 \\ y^tA+z^tB&=0 \\ y&\ge0 \\ y^ta+z^tb&<0 \end{align*} where $I_{m_2}\in\mathbb{R}^{m_2\times m_2}$ is the identity matrix and $\mathbb{1}_\varepsilon=(\varepsilon,\varepsilon,\dots,\varepsilon)^t\in\mathbb{R}^{m_2}$. So 1) $\Leftrightarrow$ ii) being infeasible $\Leftrightarrow$ i) being feasible, i.e. $T\ne\varnothing$. In short, 1) $\Leftrightarrow$ $T\ne\varnothing$.

If $S\ne\varnothing$, then $\exists$ $\alpha\in\mathbb{R}^{m_2}$ s.t. $\alpha >0$ and $T_\alpha:=\{x\in\mathbb{R}^n:Ax\le a-\alpha,Bx\le b\}\ne\varnothing$. Similar argument (as in the last paragraph) shows $y^tA+z^tB=0\Rightarrow y^t(a-\alpha)+z^tb\ge0$ for all $y,z\ge0$. So it follows that $y^tA+z^tB=0\Rightarrow y^ta+z^tb\ge y^t\alpha>0$ for all $y>0,z\ge0$. This shows $S\ne\varnothing \Rightarrow $ 2). Since $S\subset T$, we have $S\ne\varnothing\Rightarrow T\ne\varnothing\Leftrightarrow 1)$. So $S\ne\varnothing $ implies 1) and 2).

For the converse direction, what I've done is: Assume 1) and 2) are true but $S=\varnothing $. Then $T_\alpha=\varnothing $ for all $\alpha>0$. So for every $\alpha>0$ there exists $y_\alpha,z_\alpha\ge0$ s.t. $y_\alpha^tA+z_\alpha^tB=0$ but $y_\alpha^ta+z_\alpha^tb<y_\alpha^t\alpha$. Due to 1) and 2), we further have $0<y_\alpha^ta+z_\alpha^tb<y_\alpha^t\alpha$.

This is where I got stuck and totally lost. I've expected to see a chance that allows me to conclude the proof by killing the "perturbation" via $\alpha\to0$. But this doesn't seem to be promising now.