An equivalent condition of the intersection of convex hulls of two compact sets being empty

205 Views Asked by At

I came across the following problem where $A$ and $B$ are two compact sets in $\mathbb{R}^n$ ('compact' here means 'closed and bounded'). We need to show that there exists a nonzero vector $\mathbf{a}\in \mathbb{R}^n$ and a scalar $b\in \mathbb{R}$ such that: $$\mathbf{a}^{\top}\mathbf{x}-b \leq -1 ~ \forall \mathbf{x} \in A \text{ and } \mathbf{a}^{\top}\mathbf{x}-b \geq 1 ~ \forall \mathbf{x} \in B,$$ if and only if the intersection of the convex hull of $A$ and the convex hull of $B$ is empty.

I think it is similar to the Separating hyperplane theorem of convex sets. However, I cannot figure out where the $-1$ and $1$ comes from. Maybe the proof of this statement is far from the Separating hyperplane theorem? Any useful suggestions are appreciated.

1

There are 1 best solutions below

3
On BEST ANSWER

To prove this from standard version of a separation theorem you can do the following: If $a^{T}x-b \leq \alpha$ on $A$ and $a^{T}x-b \geq \beta$ on $B$ with $\beta >\alpha$ apply the map $f(t)=\frac 2 {\beta-\alpha} t-1-\frac {2\alpha} {\beta-\alpha}$ to these inequalities. Since $f$ is increasing the inequalities remain valid after aplying $f$ to both sides.