# Using the Minkowski functional to prove separation of sets via a hyperplane

Originally published at 狗和留美者不得入内. You can comment here or there.

We shall use n.v.s to refer to normed vector space.

Definition 1 Let be a n.v.s. A set of the form is called a hyperplane.

Definition 2 We call a set of the form a half-space determined by . Replacing with gives the other half-space.

Proposition 1 Any half-space is a convex set.

Proof: Trivial.

Proposition 2 Let be a n.v.s. such that . For any , the hyperplane is closed iff is continuous.

Proof: open iff is closed. Suppose is continuous and that for , . Take some open neighborhood of not containing . Then, is open and disjoint with .

To prove that is continuous, it suffices to prove that is bounded, by Proposition 2 of [1]. To show that is bounded, showing that suffices, where is the unit ball centered at zero. To do so, it suffices to show that every such that has an open neighborhood of the form such that for any , , since if this holds, then for ,

Thus, .

Assume that is open. Then, every such that is contained by a . Suppose that satisfies . Then, there must exist some such that , a contradiction. This completes our proof.

Definition 3 Let be two subsets of and with . If is such that of its two half-planes, one contains and the other contains , then we say that separates and . We say that strictly separates and if there exists some such that

We now wish to prove that for any open convex set containing and any , there exists a hyperplane that separates and . Let denote the linear functional associated with this separation. We prescribe for some . If we can find some sublinear function that is strictly bounded above on by such that on the subspace satisfies , then we can apply the Hahn-Banach theorem to extend to all in order separate from by a hyperplane.

For this desired sublinear function , we try the following.

Definition 4 Let be a subset of n.v.s . Then the gauge or Minkowski functional with respect to is defined by .

Proposition 3 If contains an open ball centered at , the Minkowski functional satisfies the condition that for all , .

Proof: Trivial and left to the reader.

We want that on , , which is satisfied when we let . We let . That is open means there is some open ball centered at the origin . For any , obviously holds. This is a simple stupid way to uniformly upper bound on .

Proposition 4 For any subset , is bounded above by for . If is open, then for all , .

Proof: Trivially proven.

Proposition 5 If is an open convex set containing , then .

Proof: Since we can scale down arbitrarily by Proposition 3, it suffices to prove this triangle inequality on an open ball centered at that is contained by . Moreover it suffices to prove that for any ,

is satisfied. We notice that

with

Let . Obviously . With this in mind, that is convex implies that for any for any , . We use to set the value of noticing that we can multiply by the denominator to derive the desired inequality. We calculate

We notice that if we replace with , we would obtain the desired inequality. Because is convex must be connected. Assuming that , we have . The connectedness hypothesis implies in fact that all such that must be in . We have that

which then implies for . Thus, we are able to make the aforementioned replacement, which then completes our proof.

Proposition 6 If is an open convex set containing , then its associated Minkowski functional is a subadditive function.

Proof: The two requirement of subadditive were proven in and respectively.

Theorem 1 Let be an open convex subset of a n.v.s . For arbitrary , there exists such that for all . In particular, the hyperplane separates and .

Proof: After a translation, we may always assume that . The Minkowski functional by Proposition 6 is a subadditive function. We define on to be linear. We can extend to on all of by the Hahn-Banach theorem (see [2] for details on it). Since by Proposition 4, for any , , we have for all , . Thus, setting gives us what we want to prove.

In [3], propositions of more general separation of sets by hyperplanes were proven. I shall not write them up here because I believe the foundational ideas behind their proofs have already been explained in the propositions above. I had learned of the Minkowski functional this week but initially did not feel like I grasped the motivation behind it. Such difficulty was resolved after reading 1.2 in [3], the title of which is “The Geometric Forms of the Hahn-Banach Theorem: Separation of Convex Sets”. Interestingly, I read about the Minkowski functional on Wikipedia before writing up [2], in the process of which I gained non-trivial understanding of the Hahn-Banach Theorem, which I had learned in 2017 or 2018 but forgotten in 2021 due to more or less superficial understanding. Certainly, the Hahn-Banach theorem can come across as very formal and abstract at first encounter, and it might not be immediate why it’s so significant. However, the geometric interpretation of it via separation of convex sets gives it more concrete meaning.

References

Tags:
• #### 中国姓氏的南北分布

有意思的是分布是很不均匀的，也就是说好多姓是南方比例远高于北方比例或相反。从这一点，你如果知道一个人的父母的姓氏，你就可以对他是北方人还是南方人有个有点统计显著的估计。 读者可以在包含大姓分布图的…

• #### 我反驳斯坦福大学物理教授祁晓亮发表在他脸书上的政治言论

包含其截屏链接： 祁晓亮的脸书政治言论 关于斯坦福反华反g及今年丑闻事件的知乎文章 在以上链接的知乎文章，有评论问为什么我认为祁晓亮是反华反g的。在这里我把他的脸书内容一个一个地分析反驳而解释。…

• #### Why I think Stanford professor James Landay's piece on computing in China in 2011 exposed his idiocy

I dittoed his blog post on my LiveJournal too, see https://gmachine1729.livejournal.com/175023.html. For the original, see…

• Post a new comment

#### Error

Anonymous comments are disabled in this journal

default userpic