Chapter 07 — Support Functions and Polar Sets

Proofs omitted. Hover over highlighted terms to see their Lean types.

Definition 7.1

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Definition 7.1: the support points of C are the points of C at which some nonzero normal vector attains the support functional of C; the textbook denotes this set by spts C, and its closure is closure (spts C).

universe u open scoped InnerProductSpace namespace Set variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] noncomputable def supportPoints (C : Set H) : Set H := {x : H | x ∈ C ∧ ∃ u : H, u ≠ 0 ∧ innerSupremumOn C u ≤ (⟪x, u⟫_ℝ : EReal)}

Exercise 7.1

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Exercise 7.1 (1): composing the support function of C with scalar multiplication by ρ on the ambient Hilbert space yields the support function of the dilated set ρ • C.

universe u open scoped InnerProductSpace Pointwise variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] local notation "σ[" C "]" => fun u ↦ sSup ((fun x ↦ (⟪x, u⟫_ℝ : EReal)) '' C) theorem supportFunction_comp_smul_eq_supportFunction_smul_set (C : Set 𝓗) (ρ : ℝ) : σ[C] ∘ (fun u : 𝓗 ↦ ρ • u) = σ[ρ • C]

Exercise 7.2

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Exercise 7.2: the support function of the Minkowski sum of two subsets of a real Hilbert space is the pointwise sum of their support functions.

universe u open scoped InnerProductSpace Pointwise variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] local notation "σ[" C "]" => fun u ↦ sSup ((fun x : 𝓗 ↦ (⟪x, u⟫_ℝ : EReal)) '' C) theorem supportFunction_minkowski_sum_eq_add (C D : Set 𝓗) : σ[C + D] = σ[C] + σ[D]

Proposition 7.2

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 7.2 (1): if C ⊆ D, then every support point of D that lies in C is a support point of C, expressed using the textbook spts notation.

open Set open scoped InnerProductSpace universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] theorem inter_exposedPoints_subset_of_subset (C D : Set E) (hCD : C ⊆ D) : C ∩ spts D ⊆ spts C

Proposition 7.3

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 7.3: the support points of C are exactly the points of C whose normal cone contains a nonzero vector.

open scoped InnerProductSpace Pointwise universe u namespace Set variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] theorem supportPoints_eq_setOf_mem_and_nontrivial_normalCone (C : Set 𝓗) : spts C = {x ∈ C | N[C] x \ ({0} : Set 𝓗) ≠ ∅}

Exercise 7.4

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Exercise 7.4: for a positive scalar γ, the polar set of the dilation γ • C is the dilation of the polar set by the reciprocal scalar γ⁻¹.

universe u open scoped InnerProductSpace Pointwise variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] local postfix:100 "ᵒ⊙" => polarSet theorem polarSet_smul_eq_inv_smul_polarSet (C : Set 𝓗) {γ : ℝ} (hγ : 0 < γ) : (γ • C)ᵒ⊙ = γ⁻¹ • Cᵒ⊙

Theorem 7.4

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Theorem 7.4 (1): Bishop--Phelps. For a nonempty closed convex subset C of a real Hilbert space, the support points of C are exactly the metric projections of points outside C, formalized as supportPoints C = P '' Cᶜ.

universe u open scoped InnerProductSpace variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] [CompleteSpace 𝓗] namespace Set variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] [CompleteSpace 𝓗] variable {C : Set 𝓗} (hC_nonempty : C.Nonempty) (hC_closed : IsClosed C) (hC_convex : Convex ℝ C) local notation "P" => projectionPoint C (isChebyshev_of_nonempty_isClosed_convex hC_nonempty hC_closed hC_convex) theorem supportPoints_eq_projectionPoint_image_compl : supportPoints C = P '' Cᶜ

Exercise 7.5

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Exercise 7.5: the polar set of the union of two subsets of a real Hilbert space is the intersection of their polar sets.

universe u open scoped InnerProductSpace namespace Set variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] -- Proof sketch: rewrite membership in each polar set using -- `mem_polarSet_iff_forall_inner_le_one`; the condition for `u ∈ (C ∪ D)ᵒ⊙` -- is exactly the conjunction of the conditions for `u ∈ Cᵒ⊙` and `u ∈ Dᵒ⊙`. theorem polarSet_union_eq_inter (C D : Set 𝓗) : (C ∪ D)ᵒ⊙ = Cᵒ⊙ ∩ Dᵒ⊙

Proposition 7.5

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 7.5 (1): if C is convex with nonempty interior, then every boundary point of C is a support point of closure C, formalized as membership in spts (closure C).

universe u open scoped InnerProductSpace Pointwise namespace Set variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] [CompleteSpace 𝓗] -- Proof sketch: a boundary point of `C` belongs to `closure C` but not to `interior (closure C)` -- because `interior (closure C) = interior C` for convex sets with nonempty interior. -- Proposition 6.45 then gives a nontrivial normal cone at that point, and Proposition 7.3 turns -- that canonical normal-cone criterion directly into `x ∈ spts (closure C)`. theorem frontier_subset_supportPoints_closure_of_convex_nonempty_interior {C : Set 𝓗} (hC_convex : Convex ℝ C) (hC_int_nonempty : (interior C).Nonempty) : frontier C ⊆ spts (closure C)

Corollary 7.6

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Corollary 7.6: if C is a closed convex subset of a real Hilbert space and either (i) interior C is nonempty, (ii) C is an affine subspace, or (iii) the ambient space is finite-dimensional, then the support points of C are exactly the boundary of C.

universe u open scoped InnerProductSpace namespace Set variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] [CompleteSpace 𝓗] theorem supportPoints_eq_frontier_of_closed_convex_of_interior_or_affine_or_finiteDimensional {C : Set 𝓗} (hC_closed : IsClosed C) (hC_convex : Convex ℝ C) (h : (interior C).Nonempty ∨ (∃ A : AffineSubspace ℝ 𝓗, C = (A : Set 𝓗)) ∨ FiniteDimensional ℝ 𝓗) : spts C = frontier C

Exercise 7.7

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Exercise 7.7: the polar set of the closed unit ball B(0;1) is the closed unit ball itself.

universe u open scoped InnerProductSpace namespace Set variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] theorem polarSet_closedUnitBall_eq_closedUnitBall : ((Metric.closedBall (0 : 𝓗) 1 : Set 𝓗)ᵒ⊙ : Set 𝓗) = Metric.closedBall (0 : 𝓗) 1

Definition 7.8

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Definition 7.8: for a subset C of a real Hilbert space, the support function σ_C is the canonical EReal-valued functional u ↦ sup ⟪C | u⟫, formalized in this project by innerSupremumOn C.

universe u open scoped InnerProductSpace variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] recall innerSupremumOn {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] (C : Set 𝓗) (u : 𝓗) : EReal

Exercise 7.8

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Exercise 7.8: if a subset of a real inner-product space is equal to its polar set, then it is the closed unit ball centered at the origin.

universe u open scoped InnerProductSpace namespace Set variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] theorem eq_closedBall_zero_one_of_polarSet_eq_self (C : Set 𝓗) (hC : Cᵒ⊙ = C) : C = Metric.closedBall (0 : 𝓗) 1

Exercise 7.9

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Exercise 7.9: the polar set of the ℓ^p closed unit ball in ℝ^N is the conjugate ℓ^q closed unit ball, not the singleton {0}.

open scoped BigOperators ENNReal InnerProductSpace namespace Set theorem polarSet_lpClosedUnitBall_eq_conj_unitBall (N : ℕ) (p : ℝ≥0∞) [Fact (1 ≤ p)] : (lpClosedUnitBall N p)ᵒ⊙ = lpClosedUnitBall N p.conjExponent

Exercise 7.10

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Exercise 7.10: if C is a cone, then its polar cone and its polar set coincide.

universe u open scoped InnerProductSpace Pointwise namespace Set variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] theorem polarCone_eq_polarSet_of_isCone {C : Set 𝓗} (hC : IsCone C) : Cᵒ⊖ = Cᵒ⊙

Proposition 7.11

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 7.11: the closed convex hull of C is the intersection of the support halfspaces cut out by the support function σ[C].

universe u open scoped InnerProductSpace variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] [CompleteSpace 𝓗] theorem closure_convexHull_eq_iInter_supportFunctionHalfspace (C : Set 𝓗) : closure (convexHull ℝ C) = ⋂ u : 𝓗, supportFunctionHalfspace C u

Corollary 7.12

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Corollary 7.12: a closed convex subset C of a real Hilbert space is the intersection of all closed half-spaces containing it, encoded here as the sets {x | ⟪x, u⟫_ℝ ≤ η} that contain C.

universe u open scoped InnerProductSpace variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] [CompleteSpace 𝓗] -- Proof sketch: if `x ∉ C`, then the geometric Hahn-Banach theorem gives a continuous linear -- functional that is strictly smaller on `C` than at `x`. The Riesz representation theorem turns -- that functional into an inner-product normal vector, producing a closed halfspace that contains -- `C` but excludes `x`. theorem eq_iInter_closed_halfspaces_of_isClosed_of_convex {C : Set 𝓗} (hC_closed : IsClosed C) (hC_convex : Convex ℝ C) : C = ⋂ (u : 𝓗) (η : ℝ) (_ : C ⊆ {x : 𝓗 | ⟪x, u⟫_ℝ ≤ η}), {x : 𝓗 | ⟪x, u⟫_ℝ ≤ η}

Proposition 7.13

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 7.13: the support function is unchanged when C is replaced by its convex hull or its closed convex hull.

universe u open scoped InnerProductSpace variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] theorem supportFunction_eq_convexHull_and_closure_convexHull (C : Set 𝓗) : σ[C] = σ[convexHull ℝ C] ∧ σ[convexHull ℝ C] = σ[closure (convexHull ℝ C)]

Definition 7.14

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Definition 7.14: the polar set Cᵒ⊙ of C consists of the vectors u for which the inner-product supremum of C at u is at most 1, equivalently the lower level set at height 1 of the support function of C.

universe u open scoped InnerProductSpace namespace Set variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] def polarSet (C : Set 𝓗) : Set 𝓗 := {u | sSup ((fun x : 𝓗 ↦ (⟪x, u⟫_ℝ : EReal)) '' C) ≤ 1}

Example 7.15

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Example 7.15 (1): if K is a cone in a real Hilbert space, then its polar set agrees with its polar cone.

universe u open scoped InnerProductSpace Pointwise namespace Set variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] theorem polarSet_eq_polarCone_of_isCone {K : Set 𝓗} (hK : IsCone K) : Kᵒ⊙ = Kᵒ⊖

Proposition 7.16

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 7.16 (1): textbook clause (i), first half. The orthogonal set of C is contained in its polar cone.

universe u open scoped InnerProductSpace Pointwise namespace Set variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] -- Proof sketch: if `u ∈ orthogonalSet C`, then `⟪x, u⟫ = 0` for every `x ∈ C`, hence in particular -- `⟪x, u⟫ ≤ 0`; rewriting with `mem_orthogonalSet` and `mem_polarCone_iff_forall_inner_nonpos` -- yields the inclusion. theorem orthogonalSet_subset_polarCone (C : Set 𝓗) : orthogonalSet C ⊆ polarCone C

Remark 7.17.1

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Remark 7.17.1 (1): every subset, and hence every cone, of a real Hilbert space is contained in its bipolar cone.

universe u open scoped InnerProductSpace Pointwise namespace Set variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] theorem subset_polarCone_polarCone (K : Set 𝓗) : K ⊆ (Kᵒ⊖)ᵒ⊖

Remark 7.17.2

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Remark 7.17.2 (1): every linear subspace V of a real Hilbert space is contained in its double orthogonal complement Vᗮᗮ.

universe u v open scoped InnerProductSpace recall Submodule.le_orthogonal_orthogonal {𝕜 : Type u} {E : Type v} [RCLike 𝕜] [NormedAddCommGroup E] [InnerProductSpace 𝕜 E] (K : Submodule 𝕜 E) : K ≤ Kᗮᗮ

Theorem 7.18

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Theorem 7.18: the bipolar polar set of C is exactly the closed convex hull of C ∪ {0}.

universe u open scoped InnerProductSpace namespace Set variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] [CompleteSpace 𝓗] theorem polarSet_polarSet_eq_closure_convexHull_union_singleton_zero (C : Set 𝓗) : Cᵒ⊙ᵒ⊙ = closure (convexHull ℝ (C ∪ ({0} : Set 𝓗)))

Corollary 7.19

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Corollary 7.19 (1): textbook clause (1), forward direction. A closed convex set containing the origin is equal to its bipolar polar set.

universe u open scoped InnerProductSpace Pointwise namespace Set variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] [CompleteSpace 𝓗] -- Proof sketch: apply Theorem 7.18 to rewrite `Cᵒ⊙ᵒ⊙` as -- `closure (convexHull ℝ (C ∪ {0}))`; for a closed convex set containing `0`, this closure and -- convex hull reduce to `C`. theorem polarSet_polarSet_eq_of_isClosed_of_convex_of_zero_mem (C : Set 𝓗) (hC_closed : IsClosed C) (hC_convex : Convex ℝ C) (hC_zero : (0 : 𝓗) ∈ C) : Cᵒ⊙ᵒ⊙ = C