# Interior of Difference of Convex Sets

I am trying to understand the first sentence of the Eidelheit separation proof (see the picture below).

That is, let $K_1$ and $K_2$ be convex sets such that

1. $K_1$ has non-empty interior
2. $K_2$ is disjoint from the interior of $K_1$

The claim is that $0$ is not an interior point of $K_1 - K_2 = \{x - y: x \in K_1, y \in K_2\}$.

I do not see why this is true. By definition, $0 \notin K_1^\circ - K_2$, but I am having trouble ruling out the possibility that $0$ can be an interior point of $K_1 - K_2$ even though $k_1 = k_2$ (i.e. $k_1 - k_2 = 0$) implies $k_1 \notin K_1^\circ$.

Any help is appreciated.

Image of the proof

• I'm not sure what precedes your proof, is there a previous result that shows that for any boundary point of a convex body, there is a plane passing through the point and the body lies entirely on one side of the plane? Apr 12 '16 at 6:00
• @copper.hat Thanks for the reply. And yes, that is exactly the statement of the previous theorem proven. Apr 12 '16 at 12:37
• I added another proof based on that. Apr 12 '16 at 15:07
• @copper.hat Thanks! I accepted your answer. (I also upvoted, but my vote will not appear until I have more reputation.) Apr 12 '16 at 16:44

If $K_1 \cap K_2 = \emptyset$, there is nothing to do, so suppose $0 \in K_1-K_2$.

By assumption, $0 \notin K_1^\circ - K_2$, so there is some non zero functional $\lambda$ such that $\lambda(x) \ge 0$ for all $x \in K_1^\circ - K_2$. Note that $K_1^\circ - K_2$ is open.

Suppose $\lambda (y) <0$ for some $y \in K_1 - K_2$. Pick any $y_0 \in K_1^\circ - K_2$, and since $t y + (1-t) y_0$ is in $K_1^\circ - K_2$ for all $t \in [0,1)$, we see that $\lambda(t y + (1-t) y_0) <0$ for some $t <1$, which is a contradiction. Hence $\lambda(x) \ge 0$ for all $x \in K_1 - K_2$.

It follows that $0$ cannot be an interior point of $K_1-K_2$, otherwise we could find some $y \in K_1-K_2$ such that $\lambda(y) <0$.

Old proof:

Here is a proof for $\mathbb{R}^n$:

A slight modification of Corollary 6.6.2 in Rockafellar's "Convex Analysis" gives $\operatorname{ri} (C_1-C_2) = \operatorname{ri} C_1 - \operatorname{ri} C_2$ for two convex sets $C_1,C_2$.

Hence $(K_1-K_2)^\circ = \operatorname{ri} (K_1-K_2) = \operatorname{ri} K_1 - \operatorname{ri} K_2 = K_1^\circ - \operatorname{ri} K_2$.

Hence if $0 \in (K_1-K_2)^\circ$, we must have some $k \in K_1^\circ \cap \operatorname{ri} K_2 \subset K_1^\circ \cap K_2$, which is a contradiction.

• Could this be generalized to an arbitrary real normed space? Apr 10 '16 at 18:31
• @Kevin: I don't have time to investigate thoroughly, but I think the approach in Rockafellar depends on finite dimensions. Apr 10 '16 at 18:54
• @Kevin: I haven't worked out the details, but I think the relevant fact here is that if $C$ is convex and $x_0 \in C^\circ$ and $x_1 \in \overline{C}$, then $[x_0,x_1) \subset C^\circ$. Apr 10 '16 at 19:29