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

  • $\begingroup$ 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? $\endgroup$
    – copper.hat
    Apr 12 '16 at 6:00
  • $\begingroup$ @copper.hat Thanks for the reply. And yes, that is exactly the statement of the previous theorem proven. $\endgroup$
    – Kevin
    Apr 12 '16 at 12:37
  • $\begingroup$ I added another proof based on that. $\endgroup$
    – copper.hat
    Apr 12 '16 at 15:07
  • $\begingroup$ @copper.hat Thanks! I accepted your answer. (I also upvoted, but my vote will not appear until I have more reputation.) $\endgroup$
    – Kevin
    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.

  • $\begingroup$ Could this be generalized to an arbitrary real normed space? $\endgroup$
    – Kevin
    Apr 10 '16 at 18:31
  • $\begingroup$ @Kevin: I don't have time to investigate thoroughly, but I think the approach in Rockafellar depends on finite dimensions. $\endgroup$
    – copper.hat
    Apr 10 '16 at 18:54
  • $\begingroup$ @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$. $\endgroup$
    – copper.hat
    Apr 10 '16 at 19:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.