[proofplan] We pass from the two-set separation problem to a one-set problem by forming the convex difference set $E = C - D$. The hypothesis on relative interiors implies that $0$ is not in the relative interior of $E$, so a hyperplane through or parallel to the affine hull of $E$ can support $E$ on one side. We treat separately the case where the affine hull of $E$ does not pass through $0$, the case where $0$ is outside the relative closure of $E$, and the case where $0$ lies on the relative boundary. In every case we obtain a nonzero vector $a$ with $a \cdot z \leq 0$ for all $z \in E$, and substituting $z = x - y$ gives the desired separation of $C$ and $D$. [/proofplan]

[step:Pass to the convex difference set and locate the origin outside its relative interior]Define the difference set \begin{align*} E := C - D = \{x - y \in \mathbb{R}^n : x \in C \text{ and } y \in D\}. \end{align*} Since $C$ and $D$ are nonempty and convex, the set $E$ is nonempty and convex. Let $A := \operatorname{aff}(E)$ denote the affine hull of $E$, and let \begin{align*} L := A - A = \{u - v \in \mathbb{R}^n : u \in A \text{ and } v \in A\} \end{align*} be the direction space of $A$. We use the finite-dimensional relative-interior difference formula for nonempty convex subsets of $\mathbb{R}^n$: \begin{align*} \operatorname{relint}(C - D) = \operatorname{relint}(C) - \operatorname{relint}(D). \end{align*} This is the standard relative-interior sum rule applied to $C+(-D)$. The hypotheses of this relative-interior calculus identity are satisfied because $C$ and $D$ are nonempty convex subsets of the finite-dimensional Euclidean space $\mathbb{R}^n$, and $-D$ is again nonempty and convex. If $0 \in \operatorname{relint}(E)$, then there would exist $x_0 \in \operatorname{relint}(C)$ and $y_0 \in \operatorname{relint}(D)$ such that $0 = x_0 - y_0$, hence $x_0 = y_0 \in \operatorname{relint}(C) \cap \operatorname{relint}(D)$, contradicting the hypothesis. Therefore \begin{align*} 0 \notin \operatorname{relint}(E). \end{align*}[/step]

[guided]The reason for introducing $E = C - D$ is that the desired inequality is exactly a one-sided inequality on all differences. Indeed, if we can find $a \in \mathbb{R}^n \setminus \{0\}$ such that \begin{align*} a \cdot z \leq 0 \end{align*} for every $z \in E$, then for each $x \in C$ and $y \in D$ the vector $z = x - y$ belongs to $E$, and hence \begin{align*} a \cdot (x - y) \leq 0. \end{align*} By linearity of the dot product, this is exactly \begin{align*} a \cdot x \leq a \cdot y. \end{align*} We now verify the basic geometry of $E$. The set is nonempty because both $C$ and $D$ are nonempty. It is convex because if $z_1 = x_1 - y_1$ and $z_2 = x_2 - y_2$ with $x_1,x_2 \in C$ and $y_1,y_2 \in D$, then for every $t \in [0,1]$, \begin{align*} t z_1 + (1-t) z_2 = \bigl(t x_1 + (1-t)x_2\bigr) - \bigl(t y_1 + (1-t)y_2\bigr). \end{align*} Convexity of $C$ gives $t x_1 + (1-t)x_2 \in C$, and convexity of $D$ gives $t y_1 + (1-t)y_2 \in D$, so $t z_1 + (1-t)z_2 \in E$. The important point is that the origin cannot lie in the relative interior of $E$. We use the finite-dimensional relative-interior difference formula, namely \begin{align*} \operatorname{relint}(C - D) = \operatorname{relint}(C) - \operatorname{relint}(D), \end{align*} which applies because $C$ and $D$ are nonempty convex subsets of $\mathbb{R}^n$ and because $-D$ is a nonempty convex subset of the same finite-dimensional Euclidean space. If $0 \in \operatorname{relint}(E)$, this formula would give points $x_0 \in \operatorname{relint}(C)$ and $y_0 \in \operatorname{relint}(D)$ with \begin{align*} 0 = x_0 - y_0. \end{align*} Thus $x_0 = y_0$, so the two relative interiors would intersect. This contradicts the hypothesis \begin{align*} \operatorname{relint}(C) \cap \operatorname{relint}(D) = \varnothing. \end{align*} Therefore \begin{align*} 0 \notin \operatorname{relint}(E). \end{align*}[/guided]

[step:Separate immediately when the affine hull avoids the origin] Assume first that $0 \notin A$. Choose a point $z_0 \in A$. Since $A = z_0 + L$, every $z \in A$ has the form $z = z_0 + v$ for some $v \in L$. Let $P_L: \mathbb{R}^n \to L$ be the [orthogonal projection](/theorems/437) onto the linear subspace $L$, and define \begin{align*} a_0 := z_0 - P_L z_0. \end{align*} Then $a_0 \in L^\perp$. Also $a_0 \neq 0$, because $a_0 = 0$ would imply $z_0 \in L$ and hence $A = z_0 + L = L$, so $0 \in A$, contrary to the present case. For every $z = z_0 + v \in A$ with $v \in L$, \begin{align*} a_0 \cdot z = a_0 \cdot z_0 + a_0 \cdot v. \end{align*} Since $a_0 \in L^\perp$ and $v \in L$, the second term is zero. Since $z_0 = P_L z_0 + a_0$ and $a_0 \perp P_L z_0$, we get \begin{align*} a_0 \cdot z = |a_0|^2. \end{align*} Thus $a_0 \cdot z$ is the positive constant $|a_0|^2$ on $A$. Set $a := -a_0$. Then $a \neq 0$ and, for every $z \in E \subseteq A$, \begin{align*} a \cdot z = -|a_0|^2 \leq 0. \end{align*} [/step]

[step:Prepare the projection and supporting functionals inside the direction space]Assume from now on that $0 \in A$. Then $A = L$, so $E$ is a nonempty convex subset of the finite-dimensional [inner product space](/page/Inner%20Product%20Space) $L$. Let $\overline{E}^{\,L}$ denote the closure of $E$ in $L$. [claim:Closed convex sets in a finite-dimensional inner product space admit projection inequalities] Let $K \subseteq L$ be a nonempty closed convex set, and let $q \in L \setminus K$. Then there exists $p \in K$ such that \begin{align*} |q-p| = \inf_{w \in K} |q-w|. \end{align*} Here, for $r>0$, $\overline{B}(q,r) := \{u \in L : |u-q| \leq r\}$ denotes the closed ball in the [inner product](/page/Inner%20Product) space $L$. For this point $p$, one has \begin{align*} (q-p) \cdot (w-p) \leq 0 \end{align*} for every $w \in K$. [/claim] [proof] Choose $w_0 \in K$ and define $r := |q-w_0| + 1$. The infimum of $w \mapsto |q-w|$ over $K$ is the same as the infimum over the compact set $K \cap \overline{B}(q,r)$, because every $w \in K$ with $|q-w| > r$ cannot improve on the value at $w_0$. Since $L$ is finite-dimensional, $K \cap \overline{B}(q,r)$ is compact. Define the continuous map \begin{align*} \psi: K \cap \overline{B}(q,r) \to \mathbb{R} \end{align*} by \begin{align*} \psi(w) := |q-w|^2. \end{align*} This map therefore attains its minimum at some $p \in K$. Fix $w \in K$. For every $t \in [0,1]$, convexity gives $p + t(w-p) \in K$. Minimality of $p$ gives \begin{align*} |q-p|^2 \leq |q-p-t(w-p)|^2. \end{align*} Expanding the square in the Euclidean inner product on $L$ gives \begin{align*} 0 \leq -2t(q-p)\cdot(w-p) + t^2 |w-p|^2. \end{align*} For $t > 0$, divide by $t$ and let $t \downarrow 0$. This yields \begin{align*} (q-p)\cdot(w-p) \leq 0. \end{align*} [/proof] [claim:Boundary points of closed convex sets have supporting functionals] Let $K \subseteq L$ be a nonempty closed convex set with $0 \in K$ and $0 \notin \operatorname{relint}(K)$. Then there exists $b \in L \setminus \{0\}$ such that \begin{align*} b \cdot w \leq 0 \end{align*} for every $w \in K$. [/claim] [proof] Since $0 \notin \operatorname{relint}(K)$ and $0 \in K \subseteq L$, the point $0$ is a boundary point of $K$ relative to $L$. Hence for each $m \in \mathbb{N}$ there exists $q_m \in L \setminus K$ such that \begin{align*} |q_m| < \frac{1}{m}. \end{align*} Apply the preceding projection claim to $K$ and $q_m$. Let $p_m \in K$ be a nearest point to $q_m$, and define \begin{align*} v_m := q_m - p_m. \end{align*} Because $q_m \notin K$ and $p_m \in K$, we have $v_m \neq 0$. Define \begin{align*} b_m := \frac{v_m}{|v_m|}. \end{align*} The projection inequality gives, for every $w \in K$, \begin{align*} b_m \cdot (w-p_m) \leq 0. \end{align*} Equivalently, \begin{align*} b_m \cdot w \leq b_m \cdot p_m. \end{align*} Because $0 \in K$ and $p_m$ is a nearest point in $K$ to $q_m$, we have \begin{align*} |q_m-p_m| \leq |q_m-0| = |q_m|. \end{align*} Therefore \begin{align*} |p_m| \leq |p_m-q_m| + |q_m| \leq 2|q_m| < \frac{2}{m}. \end{align*} Thus $p_m \to 0$ in $L$. The unit sphere in the finite-dimensional space $L$ is compact, so a subsequence of $(b_m)$ converges to some $b \in L$ with $|b| = 1$. Passing to the limit along this subsequence in \begin{align*} b_m \cdot w \leq b_m \cdot p_m \end{align*} gives \begin{align*} b \cdot w \leq 0 \end{align*} for every fixed $w \in K$. Since $|b| = 1$, we have $b \neq 0$. [/proof][/step]

[guided]We prove both parts of the projection claim directly. The data are a nonempty closed convex set $K \subseteq L$ and a point $q \in L \setminus K$, where $L$ is a finite-dimensional inner product space with Euclidean norm $|\cdot|$. The target is first to construct a nearest point $p \in K$ satisfying \begin{align*} |q-p| = \inf_{w \in K} |q-w|. \end{align*} After that, the same point must satisfy the variational inequality \begin{align*} (q-p) \cdot (w-p) \leq 0 \end{align*} for every $w \in K$. Because $K$ is nonempty, choose $w_0 \in K$. Define the positive radius \begin{align*} r := |q-w_0| + 1. \end{align*} Also define the closed ball in $L$ \begin{align*} \overline{B}(q,r) := \{u \in L : |u-q| \leq r\}. \end{align*} Why is it legitimate to restrict the minimization problem to this ball? If $w \in K$ and $|q-w| > r$, then \begin{align*} |q-w| > |q-w_0| + 1 > |q-w_0|. \end{align*} Such a point cannot improve on the distance already obtained at $w_0$. Therefore \begin{align*} \inf_{w \in K} |q-w| = \inf_{w \in K \cap \overline{B}(q,r)} |q-w|. \end{align*} The set $K \cap \overline{B}(q,r)$ is nonempty because it contains $w_0$. It is closed because $K$ is closed in $L$ and $\overline{B}(q,r)$ is closed in $L$. It is bounded because it is contained in $\overline{B}(q,r)$. Since $L$ is finite-dimensional, the [Heine-Borel theorem](/theorems/309) in finite-dimensional Euclidean spaces gives that $K \cap \overline{B}(q,r)$ is compact. Define the continuous map $\psi: K \cap \overline{B}(q,r) \to \mathbb{R}$ by \begin{align*} \psi(w) := |q-w|^2. \end{align*} The map $\psi$ is continuous because the map $w \mapsto q-w$ is continuous on $L$ and the squared Euclidean norm is continuous. By the extreme value theorem applied on the compact set $K \cap \overline{B}(q,r)$, there exists $p \in K \cap \overline{B}(q,r)$ such that \begin{align*} \psi(p) \leq \psi(w) \end{align*} for every $w \in K \cap \overline{B}(q,r)$. Equivalently, \begin{align*} |q-p|^2 \leq |q-w|^2 \end{align*} for every $w \in K \cap \overline{B}(q,r)$. Since the infimum over $K$ equals the infimum over $K \cap \overline{B}(q,r)$, this same point $p$ satisfies \begin{align*} |q-p| = \inf_{w \in K} |q-w|. \end{align*} Now fix an arbitrary point $w \in K$. The point $p$ is a minimizer, so we test minimality along the line segment from $p$ to $w$. Convexity of $K$ gives \begin{align*} p + t(w-p) \in K \end{align*} for every $t \in [0,1]$. Minimality of $p$ over $K$ gives \begin{align*} |q-p|^2 \leq |q-(p+t(w-p))|^2. \end{align*} Since \begin{align*} q-(p+t(w-p)) = q-p-t(w-p), \end{align*} we have \begin{align*} |q-p|^2 \leq |q-p-t(w-p)|^2. \end{align*} Expanding the square in the Euclidean inner product on $L$ gives \begin{align*} |q-p-t(w-p)|^2 = |q-p|^2 - 2t(q-p)\cdot(w-p) + t^2 |w-p|^2. \end{align*} Substituting this expansion into the previous inequality and subtracting $|q-p|^2$ from both sides yields \begin{align*} 0 \leq -2t(q-p)\cdot(w-p) + t^2 |w-p|^2. \end{align*} For $t>0$, divide by $t$ to obtain \begin{align*} 0 \leq -2(q-p)\cdot(w-p) + t |w-p|^2. \end{align*} Letting $t \downarrow 0$ gives \begin{align*} 0 \leq -2(q-p)\cdot(w-p). \end{align*} Thus \begin{align*} (q-p)\cdot(w-p) \leq 0. \end{align*} Because $w \in K$ was arbitrary, the projection inequality holds for every $w \in K$. The same step will next use this projection inequality for a closed convex set \begin{align*} K \subseteq L, \end{align*} with boundary data \begin{align*} 0 \in K \end{align*} and \begin{align*} 0 \notin \operatorname{relint}(K). \end{align*} For each $m \in \mathbb{N}$ we choose $q_m \in L \setminus K$ with \begin{align*} |q_m| < \frac{1}{m}, \end{align*} then take a nearest point $p_m \in K$ and define \begin{align*} v_m := q_m-p_m, \end{align*} and \begin{align*} b_m := \frac{v_m}{|v_m|}. \end{align*} The projection inequality gives \begin{align*} b_m\cdot(w-p_m)\leq 0, \end{align*} hence \begin{align*} b_m\cdot w\leq b_m\cdot p_m \end{align*} for every $w \in K$.[/guided]

[step:Find a nonzero functional on the direction space when the affine hull contains the origin]Assume $0 \in A$, so $A = L$. Set \begin{align*} K := \overline{E}^{\,L}. \end{align*} Then $K$ is a nonempty closed convex subset of $L$. First suppose $0 \notin K$. Applying the projection claim from the previous step to $K$ and $q = 0$, choose $p \in K$ such that \begin{align*} |p| = \inf_{w \in K} |w|. \end{align*} Since $0 \notin K$, $p \neq 0$. The projection inequality gives \begin{align*} (0-p)\cdot(w-p) \leq 0 \end{align*} for every $w \in K$. Equivalently, \begin{align*} p \cdot w \geq |p|^2 \end{align*} for every $w \in K$. Define $b := -p$. Then $b \in L \setminus \{0\}$ and \begin{align*} b \cdot w \leq -|p|^2 \leq 0 \end{align*} for every $w \in K$, hence for every $w \in E$. Now suppose $0 \in K$. Since $K = \overline{E}^{\,L}$ and $E$ is a nonempty convex subset of the finite-dimensional space $L$, we invoke the finite-dimensional closure invariance of relative interiors: a convex set and its closure have the same relative interior when the relative interior is computed in their common affine hull. For any subset $S \subseteq L$, let $\operatorname{aff}_L(S)$ denote the affine hull of $S$ computed inside the ambient affine space $L$. Moreover, because $E \subseteq K \subseteq \overline{E}^{\,L}$, the affine hulls agree inside $L$: \begin{align*} \operatorname{aff}_L(E) = \operatorname{aff}_L(K). \end{align*} Thus the relative interiors are computed in the same affine hull, and \begin{align*} \operatorname{relint}(K) = \operatorname{relint}(E). \end{align*} From the first step, $0 \notin \operatorname{relint}(E)$, hence $0 \notin \operatorname{relint}(K)$. Applying the supporting-functional claim to $K$, there exists $b \in L \setminus \{0\}$ such that \begin{align*} b \cdot w \leq 0 \end{align*} for every $w \in K$, and therefore for every $w \in E$. In both subcases there is $b \in L \setminus \{0\}$ such that \begin{align*} b \cdot z \leq 0 \end{align*} for every $z \in E$.[/step]

[guided]We are now working in the case $0 \in A$. This matters because the affine hull is then already a linear space: \begin{align*} A = L. \end{align*} Thus $E$ can be regarded as a convex subset of the finite-dimensional inner product space $L$, and we may use ordinary Euclidean projection and supporting-hyperplane arguments inside $L$. Let \begin{align*} K := \overline{E}^{\,L} \end{align*} be the closure of $E$ in $L$. The closure is nonempty because $E$ is nonempty, closed by definition, and convex because the closure of a convex set in a finite-dimensional [topological vector space](/page/Topological%20Vector%20Space) is convex. There are two possibilities. First, suppose $0 \notin K$. Then the origin has positive distance from the closed convex set $K$. By the projection claim, there is a point $p \in K$ minimizing the distance from $0$ to $K$: \begin{align*} |p| = \inf_{w \in K} |w|. \end{align*} Since $0 \notin K$, this minimizer is nonzero. The projection inequality with $q = 0$ says \begin{align*} (0-p)\cdot(w-p) \leq 0 \end{align*} for every $w \in K$. Expanding this inequality gives \begin{align*} -p \cdot w + |p|^2 \leq 0, \end{align*} and hence \begin{align*} p \cdot w \geq |p|^2 \end{align*} for every $w \in K$. If we define $b := -p$, then $b \neq 0$ and \begin{align*} b \cdot w \leq -|p|^2 \leq 0 \end{align*} for every $w \in K$. Since $E \subseteq K$, the same inequality holds for every $w \in E$. Second, suppose $0 \in K$. We need a supporting functional at the origin. The first step proved \begin{align*} 0 \notin \operatorname{relint}(E). \end{align*} For convex sets in finite-dimensional spaces, taking closure in the ambient finite-dimensional affine hull does not change the relative interior. Here the closure is taken in $L$. For any subset $S \subseteq L$, the notation $\operatorname{aff}_L(S)$ means the affine hull of $S$ computed inside the ambient affine space $L$. Because $E \subseteq K \subseteq \overline{E}^{\,L}$, the affine hulls agree inside $L$: \begin{align*} \operatorname{aff}_L(E) = \operatorname{aff}_L(K). \end{align*} Thus the two relative interiors are computed in the same affine hull, and \begin{align*} \operatorname{relint}(K) = \operatorname{relint}(E). \end{align*} Therefore \begin{align*} 0 \notin \operatorname{relint}(K). \end{align*} Because $0 \in K$ but $0$ is not in the relative interior of $K$, the origin is a relative boundary point of the closed convex set $K$. The supporting-functional claim applies and gives a vector $b \in L \setminus \{0\}$ such that \begin{align*} b \cdot w \leq 0 \end{align*} for every $w \in K$. Again $E \subseteq K$, so \begin{align*} b \cdot w \leq 0 \end{align*} for every $w \in E$. Thus, in every case with $0 \in A$, we obtain a nonzero vector $b$ inside the direction space $L$ whose dot product is nonpositive on the whole difference set $E$.[/guided]

[step:Extend the direction-space functional to all of $\mathbb{R}^n$] In the remaining case $0 \in A$, let $b \in L \setminus \{0\}$ be the vector constructed in the previous step. Define \begin{align*} a := b \in \mathbb{R}^n. \end{align*} This is a nonzero vector in the ambient Euclidean space. Since every $z \in E$ lies in $A = L$, the inequality from the previous step gives \begin{align*} a \cdot z = b \cdot z \leq 0 \end{align*} for every $z \in E$. [/step]

[step:Translate the one-sided inequality on differences into separation of the original sets] Combining the two cases, we have constructed a vector $a \in \mathbb{R}^n \setminus \{0\}$ such that \begin{align*} a \cdot z \leq 0 \end{align*} for every $z \in E$. Let $x \in C$ and $y \in D$ be arbitrary. By definition of $E$, the vector $x-y$ belongs to $E$. Therefore \begin{align*} a \cdot (x-y) \leq 0. \end{align*} Using linearity of the dot product, \begin{align*} a \cdot x - a \cdot y \leq 0. \end{align*} Hence \begin{align*} a \cdot x \leq a \cdot y. \end{align*} Since $x \in C$ and $y \in D$ were arbitrary, the separation inequality holds for every $x \in C$ and every $y \in D$. [/step]

[step:Verify that the separating functional is not constant on $C \cup D$] Define the [linear map](/page/Linear%20Map) $\ell: \mathbb{R}^n \to \mathbb{R}$ by \begin{align*} \ell(u) := a \cdot u. \end{align*} First consider the case $0 \notin A$. In that case we constructed $a = -a_0$ and proved that \begin{align*} a \cdot z = -|a_0|^2 \end{align*} for every $z \in E$. Suppose, for contradiction, that $\ell$ is constant on $C \cup D$. Then there exists $\gamma \in \mathbb{R}$ such that $\ell(u) = \gamma$ for every $u \in C \cup D$. For every $x \in C$ and $y \in D$, \begin{align*} a \cdot (x-y) = \ell(x) - \ell(y) = \gamma - \gamma = 0. \end{align*} This contradicts $a \cdot (x-y) = -|a_0|^2 < 0$ for every $x-y \in E$. Therefore $\ell$ is not constant on $C \cup D$. Now consider the case $0 \in A$. Then $A = L$, and the vector $a$ lies in $L$ with $a \neq 0$. Suppose, for contradiction, that $\ell$ is constant on $C \cup D$. As above, for every $x \in C$ and $y \in D$, \begin{align*} a \cdot (x-y) = 0. \end{align*} Thus $E \subseteq \ker \ell$. Since $\ker \ell$ is a linear subspace of $\mathbb{R}^n$, it is convex and affine; hence it contains the affine hull of $E$: \begin{align*} A = \operatorname{aff}(E) \subseteq \ker \ell. \end{align*} Because $A = L$, this gives $L \subseteq \ker \ell$. In particular $a \in L \subseteq \ker \ell$, so \begin{align*} 0 = \ell(a) = a \cdot a = |a|^2. \end{align*} This contradicts $a \neq 0$. Therefore $\ell$ is not constant on $C \cup D$. The constructed vector $a$ gives the required separating inequality, and the associated linear functional is proper. This completes the proof. [/step]