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.
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.
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.
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.
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 CProposition 7.3
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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.
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.
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.
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.
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 CExercise 7.7
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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 : 𝓗) 1Definition 7.8
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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 : 𝓗) : ERealExercise 7.8
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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 : 𝓗) 1Exercise 7.9
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.conjExponentExercise 7.10
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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 uCorollary 7.12
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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.
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.
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.
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 CRemark 7.17.1
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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.
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.
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