1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ It is just the usual separation theorem you can find in Rudin's FA. A simple transformation can be used to get $-1$ and $+1$. $\endgroup$ Oct 4, 2021 at 11:34
  • $\begingroup$ Thanks. Could you explain more about the 'simple transformation' to get -1 and +1, which I'm still confused about? $\endgroup$
    – Harry556
    Oct 4, 2021 at 12:06

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thanks a lot. But I have two more questions. First, when applying the map to both sides, $a^{T}x-b$ is also changed, so that it is not the original inequality. Second, the standard version of separation theorem is about two convex sets, while here $A$, $B$ are arbitrary compact sets and we are talking about their convex hulls. Sorry to bother but I'm fresh in this area. It would be appreciated if you could reply. $\endgroup$
    – Harry556
    Oct 4, 2021 at 13:29
  • $\begingroup$ When you apply $f$ to $a^{T}x-b$ you get $a'^{T}x-b'$ for some $a',b'$. Can you figure out what $a'$ and $b'$ are ? I am using the fact that convex hulls of compact sets in $\mathbb R^{n}$ are themselves compact. This is proved in Rudin's book. Once you know this you can apply the separation theorem to the convex hulls of $A$ and $B$. @Arthur556 $\endgroup$ Oct 4, 2021 at 23:15
  • $\begingroup$ Thank you very much. $\endgroup$
    – Harry556
    Oct 5, 2021 at 2:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .