Strong Separation Theorem

From ProofWiki
Jump to navigation Jump to search


This page has been identified as a candidate for refactoring of basic complexity.
In particular: Lemma in its own page
Until this has been finished, please leave {{Refactor}} in the code.

New contributors: Refactoring is a task which is expected to be undertaken by experienced editors only.

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: throughout
You 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

Retrieved from "https://proofwiki.org/w/index.php?title=Strong_Separation_Theorem&oldid=570960"