Hyperplane Separation Theorem

[This article was first published on Pachá, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

A bit of context to put this on my stats blog: I’m reading Real Analysis books again as a part of my studies. I used to visit Kim C. Border site from time to time to read his excellent materials, and now I read that he passed away. I never audited one of his courses nor studied at Caltech, but we exchanged several emails from 2012 to 2019, mostly about Linear Algebra, and lately also about Arrow’s Impossibility Theorem and social debates in a moment when Chile entered a political crisis that we still haven’t solved. The proof of this theorem, heavily inspired from his style, is a way to tribute him as a very positive influence during my economics studies.

Theorem (Hyperplane Separation Theorem). Let A and B two convex, disjoint, non-empty subsets of Rn. If A is closed and B is compact, exists pRn{0} such that pa<pb(a,b)A×B.

Proof. Shall be made under a “divide and conquer” approach.

If A is closed, define the function f:BRbminaAba.

This function returns the distance from bB to aA and is a continuous function.

If B is compact, exists b0B such that f(b0)f(b)bB.

Let yA such that f(b0)=b0y. The vector p=b0yb0y

is well defined and is such that p=1.

From pp>0, it follows that pb0yb0y>0,

from which we conclude that py<pb0.

From (*) we need to prove that pb0pb and pa<py.

Fix aA and define the function g:[0,1]Rλb0+yλ(ay)2.

Provided that A is convex, g reaches a minimum at λ=0, then g(λ)=(b0yλ(ay),b0yλ(ay))2=(b0y,b0y2λb0y,ay+λ2ay,ay)2gλ=2b0y,ay+2λay,ay.
Hence, gλ|λ=0=(b0y)(ya)0.
Dividing by b0y we conclude that papy.

Fix bB and define the function h:[0,1]Rλb0yλ(by)2.

By the same argument that leads to (**), we conclude that pb0pb.

Finally, (*), (**) and (***) lead to conclude that pa<pb.

To leave a comment for the author, please follow the link and comment on their blog: Pachá.

R-bloggers.com offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)