Sheng Li (gmachine1729) wrote,
Sheng Li
gmachine1729

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: uncategorized
Subscribe

  • Журавли (песня)

    Эта песня такая красивая эта неделя я наконец понял его слова, и потому это труднее теперь в Китае посетить Ютуб (даже через мой VPN это очень…

  • Журавли

    Originally published at Когда нас в бой пошлёт товарищ Путин и маршал Шойгу в бой нас поведёт!. You can comment here or there. Это такая красная…

  • 我的美好元旦

    Originally published at Inside the Mind of the G Machine. You can comment here or there.…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

  • 0 comments