# Strong Separation Theorem

This page has been identified as a candidate for refactoring of basic complexity.In particular: Lemma in its own pageUntil this has been finished, please leave
`{{Refactor}}` in the code.
Because of the underlying complexity of the work needed, it is recommended that you do not embark on a refactoring task until you have become familiar with the structural nature of pages of $\mathsf{Pr} \infty \mathsf{fWiki}$.To discuss this page in more detail, feel free to use the talk page.When this work has been completed, you may remove this instance of `{{Refactor}}` from the code. |

This article needs to be linked to other articles.In particular: throughoutYou can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding these links.To discuss this page in more detail, feel free to use the talk page.When this work has been completed, you may remove this instance of `{{MissingLinks}}` from the code. |

## Theorem

Let $C \subset \R^\ell$ be closed and convex.

Let $D = \set {\mathbf v} \subset C^c$.

Then $C$ and $D$ can be strongly separated.

## Proof

### Lemma 1

For any $\mathbf y \ne 0$ and any $\mathbf z \in \map {H_{\mathbf y}^<} r$, $r = \mathbf y \mathbf y$, the line segment joining $\mathbf y$ and $\mathbf z$ contains points with lengths strictly less than $\mathbf y$.

This article, or a section of it, needs explaining.In particular: Because of the loose use of commas to separate clauses, it is unclear what the above is supposed to mean. Is $r = \mathbf y \mathbf y$ part of the premise or conclusion? That is, should it be taken to mean "the line segment joining $\mathbf y$ and $\mathbf z$? (If so, then perhaps it ought to be $r = \mathbf y \mathbf z$.) Or is it one of the conditions on $\mathbf y$ and $\mathbf z$ which needs to be fulfilled in order for the conclusion to follow? (In that case, its meaning needs to be explained.You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by explaining it.To discuss this page in more detail, feel free to use the talk page.When this work has been completed, you may remove this instance of `{{Explain}}` from the code. |

This article, or a section of it, needs explaining.In particular: What is the domain of $\mathbf y$? Presumably it is a vector of some kind, in which case the nature of $0$ also needs to be defined.You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by explaining it.To discuss this page in more detail, feel free to use the talk page.When this work has been completed, you may remove this instance of `{{Explain}}` from the code. |

This article, or a section of it, needs explaining.In particular: $\map {H_{\mathbf y}^<} r$You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by explaining it.To discuss this page in more detail, feel free to use the talk page.When this work has been completed, you may remove this instance of `{{Explain}}` from the code. |

### Proof of Lemma 1

Since $\mathbf z \in \map {H_\mathbf y} r^<$:

- $\mathbf z = \mathbf x - s \mathbf y$

for some $\mathbf x \perp \mathbf y$ and $s > 0$.

This article, or a section of it, needs explaining.In particular: $\mathbf x \perp \mathbf y$You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by explaining it.To discuss this page in more detail, feel free to use the talk page.When this work has been completed, you may remove this instance of `{{Explain}}` from the code. |

Let:

- $\map f \gamma = \norm {\gamma \mathbf y + \paren {1 - \gamma} \mathbf z}^2$

for $\gamma \in \closedint 0 1$.

We show that:

- $\map f \gamma < \norm {\mathbf y}^2$

as $\gamma \to 1$.

Expand $\map f \gamma$:

\(\ds \map f \gamma\) | \(=\) | \(\ds \norm {\gamma \, \mathbf y + \paren {1 - \gamma} \mathbf z}^2\) | Definition of $\map f \gamma$ | |||||||||||

\(\ds \) | \(=\) | \(\ds \paren {\gamma \, \mathbf y + \paren {1 - \gamma} \mathbf z} \cdot \paren {\gamma \mathbf y + \paren {1 - \gamma} \mathbf z}\) | Definition of norm on vector space $\R^\ell$ | |||||||||||

\(\ds \) | \(=\) | \(\ds \paren {\gamma \, \mathbf y + \paren {1 - \gamma} \paren {\mathbf x - s \, \mathbf y} } \cdot \paren {\gamma \, \mathbf y + \paren {1 - \gamma} \paren {\mathbf x - s \, \mathbf y} }\) | as $\mathbf z = \mathbf x - s \, \mathbf y$ | |||||||||||

\(\ds \) | \(=\) | \(\ds \gamma^2 \mathbf y \mathbf y + 2 \gamma \paren {1 - \gamma} \mathbf y \paren {\mathbf x - s \mathbf y} + \paren {1 - \gamma}^2 \paren {\mathbf x - s \, \mathbf y} \paren {\mathbf x - s \, \mathbf y}\) | Distributive property of dot product | |||||||||||

\(\ds \) | \(=\) | \(\ds \gamma^2 \mathbf y \mathbf y - 2 \gamma \paren {1 - \gamma} s \, \mathbf y \mathbf y + \paren {1 - \gamma}^2 s^2 \mathbf y \mathbf y\) | Distributive property of dot product | |||||||||||

\(\ds \) | \(\) | \(\, \ds + \, \) | \(\ds 2 \gamma \paren {1 - \gamma} \mathbf x \mathbf y - 2 \paren {1 - \gamma}^2 s \, \mathbf x \mathbf y + \paren {1 - \gamma}^2 \mathbf x \mathbf x\) | |||||||||||

\(\ds \) | \(=\) | \(\ds \mathbf y \mathbf y \paren {\gamma^2 - 2 \gamma \paren {1 - \gamma} s + \paren {1 - \gamma}^2 s^2} + \paren {1 - \gamma}^2 \mathbf x \mathbf x\) | Definition of orthogonal vectors | |||||||||||

\(\ds \) | \(=\) | \(\ds \mathbf y \mathbf y \paren {\gamma - s \paren {1 - \gamma} }^2 + \paren {1 - \gamma}^2 \mathbf x \mathbf x\) | Binomial Theorem |

Since $\map {f'} 1 = 2 \paren {1 + s} > 0$:

- $\map f \gamma < \map f 1$

as $\gamma \to 1$.

Since $\map f 1 = \mathbf y \mathbf y = \norm {\mathbf y}^2$:

- $\map f \gamma < \norm {\mathbf y}^2$

as $\gamma \to 1$.

$\Box$

### Proof of Theorem

Translating $C$ and $D = \set {\mathbf v}$ by $-\mathbf v$:

We show that the theorem holds for $\mathbf v = 0$.

Pick $n > 0$ such that:

- $K = \map \cl {\map {B_n} {\mathbf v} } \cap C \ne \O$

Since $C$ is closed, $K$ is closed.

Since $\map {B_n} {\mathbf v}$ is bounded, $K$ is bounded.

Since $K$ is closed and bounded, $K$ is compact.

Let $\map f {\mathbf x} = \norm {\mathbf x}$.

Since $\norm {\mathbf x}^2$ and $\sqrt x: \R_+ \to \R_+$ are both continuous, $\map f {\mathbf x}$ is continuous.

Since $K$ is compact and $\map f {\mathbf x}$ is continuous, $\map f {\mathbf x}$ achieves its minimum at $\mathbf y \in C$ by the Weierstrass Theorem.

Let $\map L {\mathbf x} = \mathbf y \mathbf x$ and $r = \mathbf y \mathbf y$.

We show that:

- $C \subset \map {L^{-1} } {\hointr r \to}$

Suppose $C$ is not a subset of $\map {L^{-1} } {\hointr r \to}$.

There exists $\mathbf z \in C \cap \map {L^{-1} } {\closedint {-\infty} r}$

So:

- $\mathbf z \in \map {H_\mathbf y} r$

As $\gamma \to 1$, there exists a $0 < \gamma < 1$ such that:

- $\norm {\mathbf y \, \gamma \, \mathbf z} < \norm {\mathbf y}$

by Lemma 1.

Since $C$ is convex, $\mathbf y \in C$ and $\mathbf z \in C$, convex combination $\mathbf y \, \gamma \, \mathbf z \in C$.

This article, or a section of it, needs explaining.In particular: It is not clear which parts of the above compound "sentence" are in the premise and which in the conclusion.You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by explaining it.To discuss this page in more detail, feel free to use the talk page.When this work has been completed, you may remove this instance of `{{Explain}}` from the code. |

Since $\mathbf y $ is a minimmizer of $\norm {\mathbf x}$:

- $\norm {\mathbf y} \le \norm {\mathbf y \, \gamma \, \mathbf z}$

which is a contradiction.

This article, or a section of it, needs explaining.In particular: Make it plain what it contradicts, and what the conclusion is of that Proof by Contradiction.You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by explaining it.To discuss this page in more detail, feel free to use the talk page.When this work has been completed, you may remove this instance of `{{Explain}}` from the code. |

For strong separation, let $\epsilon < r / 2$.

We have:

- $C \subset \map {L^{-1} } {\hointr r \to} \subset \map {L^{-1} } {\hointr {r/2 + \epsilon} \infty}$

Since:

- $\map L {\mathbf 0} = \mathbf y \mathbf 0 = 0$

and:

- $r/2 - \epsilon > 0$

it follows that:

- $\mathbf v = \mathbf 0 \subset \map {L^{-1} } {\hointl {-\infty} {r/2 - \epsilon} }$

This article, or a section of it, needs explaining.In particular: Explain how the conclusion of the proof follows from that.You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by explaining it.To discuss this page in more detail, feel free to use the talk page.When this work has been completed, you may remove this instance of `{{Explain}}` from the code. |

$\blacksquare$

## Sources

- 2009: Dean Corbae, Maxwell B. Stinchcombe and Juraj Zeman:
*An Introduction to Mathematical Analysis for Economic Theory and Econometrics*: $\S 5.4.a$ Theorem $5.4.1$