Chapter 06 — Convex Cones and Generalized Interiors

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

Definition 6.1

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

Source header · Attribution source

Definition 6.1: the conical hull cone C is the intersection of all cones containing C, hence the smallest cone containing C.

open scoped Pointwise universe u namespace Set variable {X : Type u} [AddCommGroup X] [Module ℝ X] -- Route correction: the file uses the imported project notion `IsCone = (Ioi 0) • _`, -- so the proofs proceed through the `sInter` universal property of that existing notion. -- Proof sketch: for the forward direction, rewrite `IsCone K` using the existing project -- definition and unpack membership in a pointwise scalar multiple; for the reverse direction, -- use the nonnegative-scalar closure hypothesis with `1 ≥ 0` and the existing characterization -- of `IsCone`. def conicalHull (C : Set X) : Set X := sInter {K : Set X | IsCone K ∧ C ⊆ K} -- Proof sketch: if `x ∈ C`, then `x` belongs to every cone `K` with `C ⊆ K`; therefore `x` -- belongs to the intersection defining `cone C`.

Proposition 6.2

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

Source header · Attribution source

Proposition 6.2 (1): textbook clause (i). The conical hull cone C is exactly the set of strictly positive real multiples of points of C.

open scoped Pointwise universe u namespace Set local notation "cone" => Set.conicalHull variable {E : Type u} [AddCommGroup E] [Module ℝ E] theorem conicalHull_eq_pos_smul (C : Set E) : cone C = (Ioi (0 : ℝ) : Set ℝ) • C

Proposition 6.3

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

Source header · Attribution source

Proposition 6.3 (1): a cone in a real vector space is convex exactly when it is closed under pointwise addition.

open Set open scoped Pointwise universe u variable {X : Type u} [AddCommGroup X] [Module ℝ X] theorem IsCone.convex_iff_add_subset {C : Set X} (hC_cone : IsCone C) : Convex ℝ C ↔ C + C ⊆ C

Proposition 6.4

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

Source header · Attribution source

Proposition 6.4 (1): for a nonempty convex subset C of a real vector space, its linear span coincides with the difference of the cone generated by C with itself.

universe u open scoped Pointwise variable {E : Type u} [AddCommGroup E] [Module ℝ E] theorem span_eq_cone_sub_cone {C : Set E} (hC_nonempty : C.Nonempty) (hC_convex : Convex ℝ C) : ((Submodule.span ℝ C : Submodule ℝ E) : Set E) = ((hC_convex.toCone C : ConvexCone ℝ E) : Set E) - ((hC_convex.toCone C : ConvexCone ℝ E) : Set E)

Definition 6.5

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

Source header · Attribution source

Definition 6.5 (1): a cone is pointed when its intersection with its negative is contained in {0}.

open scoped Pointwise universe u namespace Set variable {E : Type u} [AddGroup E] def IsPointedCone (K : Set E) : Prop := K ∩ -K ⊆ ({0} : Set E) -- Proof sketch: unfold `Set.IsPointedCone`; this is exactly the defining condition from the -- textbook.

Example 6.6

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

Source header · Attribution source

Example 6.6: the set determined by a vector u is the closed half-space of vectors whose inner product with u is nonpositive.

universe u open scoped InnerProductSpace Pointwise namespace Set variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] def nonpositiveInnerHalfspace (u : 𝓗) : Set 𝓗 := {x | ⟪x, u⟫_ℝ ≤ 0} -- Proof sketch: unfold `Set.nonpositiveInnerHalfspace`.

Example 6.7

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

Source header · Attribution source

Example 6.7: the positive orthant in ℓ²(I) equals the closure of the conic hull of the convex hull of the standard unit vectors.

open Filter open Set open scoped Pointwise universe u variable (I : Type u) variable {I : Type u} theorem ell2PositiveOrthant_eq_closure_standardUnitCone [Nonempty I] : ell2PositiveOrthant I = closure (ell2StandardUnitCone I : Set (PiLp 2 fun _ : I ↦ ℝ))

Proposition 6.8

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

Source header · Attribution source

Proposition 6.8 at the cone-owner level: the pointed cone generated by the finite image x '' ↑s is exactly the convex cone generated by the same image together with 0.

universe u v namespace Set open scoped BigOperators variable {ι : Type v} {E : Type u} variable [AddCommMonoid E] [Module ℝ E] -- Proof sketch: apply `PointedCone.mem_hull_set` to the finite image `x '' ↑s`, then rewrite the -- resulting finitely supported conical combination as a sum indexed by `s`. theorem pointedConeHull_image_finset_eq_convexConeHull_image_union_zero (s : Finset ι) (x : ι → E) : (PointedCone.hull ℝ (x '' (s : Set ι)) : ConvexCone ℝ E) = ConvexCone.hull ℝ (x '' (s : Set ι) ∪ ({0} : Set E))

Definition 6.9

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

Source header · Attribution source

Definition 6.9 (1): the core core C is the set of points x ∈ C such that the cone generated by the translate C - x is the whole ambient real vector space.

open scoped Pointwise universe u namespace Set variable {E : Type u} [AddCommGroup E] [Module ℝ E] scoped notation "cone" => Set.cone def core (C : Set E) : Set E := {x ∈ C | Set.cone (C - ({x} : Set E)) = (univ : Set E)}

Example 6.10

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

Source header · Attribution source

Example 6.10 (1): if a nonempty convex set is symmetric with respect to the origin, then the origin belongs to its relative interior.

open Set open scoped Pointwise universe u variable {E : Type u} [AddCommGroup E] [Module ℝ E] theorem zero_mem_relativeInterior_of_eq_neg {C : Set E} (hC_nonempty : C.Nonempty) (hC_convex : Convex ℝ C) (hC_symmetric : C = -C) : (0 : E) ∈ {x ∈ C | (ConvexCone.hull ℝ (C - ({x} : Set E)) : Set E) = (Submodule.span ℝ (C - ({x} : Set E)) : Set E)}

Proposition 6.12

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

Source header · Attribution source

Proposition 6.12: for a convex set in a complete real normed space, the interior coincides with its core whenever (i) the interior is nonempty, or (ii) the set is closed, or (iii) the ambient space is finite-dimensional.

open Set Topology open scoped Pointwise universe u namespace Proposition612Absorbent variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] [CompleteSpace E] theorem interior_eq_core_of_convex {C : Set E} (hC : Convex ℝ C) (h : (interior C).Nonempty ∨ IsClosed C ∨ FiniteDimensional ℝ E) : interior C = Set.core C

Fact 6.13

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

Source header · Attribution source

Fact 6.13: for closed convex subsets C and D of a real Hilbert space, the interior of the difference set C - D coincides with its core.

open Set Topology open scoped Pointwise universe u namespace Proposition612Absorbent variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] -- Proof sketch: the cited external corollary says that a surjective continuous linear image of a -- closed convex set in a Hilbert space has interior equal to core. Apply it to the closed convex -- product `C ×ˢ D` under the continuous linear map `(x, y) ↦ x - y`. theorem interior_sub_eq_core_sub_of_isClosed_of_convex {C D : Set H} (hC_closed : IsClosed C) (hD_closed : IsClosed D) (hC_convex : Convex ℝ C) (hD_convex : Convex ℝ D) : interior (C - D) = Set.core (C - D)

Fact 6.14

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

Source header · Attribution source

Fact 6.14 (1): in source clause (i), for a convex subset of a finite-dimensional real Hilbert space, ri C is the interior of C relative to affineSpan ℝ C, i.e. intrinsicInterior ℝ C.

open Set Topology open scoped Pointwise universe u v variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] theorem relativeInterior_eq_intrinsicInterior_of_finiteDimensional {C : Set H} [FiniteDimensional ℝ H] (hC_convex : Convex ℝ C) : ri C = intrinsicInterior ℝ C

Corollary 6.15

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

Source header · Attribution source

Corollary 6.15 (1): for a nonempty convex subset C of a finite-dimensional real Hilbert space and a continuous linear map L : H →L[ℝ] K into a finite-dimensional real Hilbert space, the relative interior of L '' C is the image of the relative interior of C.

open Set open scoped Pointwise universe u v variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [FiniteDimensional ℝ H] variable {K : Type v} [NormedAddCommGroup K] [InnerProductSpace ℝ K] [FiniteDimensional ℝ K] -- Proof sketch: Fact 6.14(6) identifies `ri C` with `qri C` in finite dimension, and -- Fact 6.14(13) then sends `qri C` through the continuous linear image `L`. theorem relativeInterior_image_eq_image_relativeInterior_of_finiteDimensional (L : H →L[ℝ] K) (C : Set H) (hC_nonempty : C.Nonempty) (hC_convex : Convex ℝ C) : ri (L '' C) = L '' ri C

Proposition 6.16

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

Source header · Attribution source

Proposition 6.16: if C is a convex subset of a real normed space, contains 0, and has nonempty interior, then interior (cone C) = cone (interior C).

open Set AffineMap open scoped Pointwise universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] theorem interior_cone_eq_cone_interior {C : Set E} (hC_convex : Convex ℝ C) (h0C : (0 : E) ∈ C) (hC_int_nonempty : (interior C).Nonempty) : interior (cone C) = cone (interior C)

Proposition 6.17

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

Source header · Attribution source

Proposition 6.17: for a convex subset C of a real normed space with nonempty interior, the following are equivalent: (i) 0 ∈ interior C; (ii) cone (interior C) = univ; (iii) cone C = univ; and (iv) closure (cone C) = univ.

open scoped Pointwise universe u namespace Set variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] theorem zero_mem_interior_tfae_cone_interior_cone_closure_eq_univ {C : Set E} (hC_convex : Convex ℝ C) (hC_int_nonempty : (interior C).Nonempty) : List.TFAE [ 0 ∈ interior C, cone (interior C) = univ, cone C = univ, closure (cone C) = univ ]

Example 6.18

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

Source header · Attribution source

Example 6.18: for a sequence (e_n), let S be the closure of the convex hull of the dyadically scaled points ± 2^{-n} e_n. Using the canonical owner closedAbsConvexHull ℝ (dyadicScaledRange e) for that symmetric closed hull, let C = S + S^⊥, represented here by dyadicSignedCylinder e. The orthonormality assumptions from the textbook enter only in the later theorems about this set.

open Set open scoped Pointwise InnerProductSpace Topology universe u namespace Set variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] def dyadicSignedCylinder (e : ℕ → 𝓗) : Set 𝓗 := let S : Set 𝓗 := closedAbsConvexHull ℝ (dyadicScaledRange e) S + S^⊥

Proposition 6.19

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

Source header · Attribution source

Proposition 6.19: if C and D are nonempty convex subsets of real Hilbert spaces and one of the regularity conditions (i) through (x) from the text holds for the continuous linear image L '' C, then the origin belongs to the strong relative interior of D - L '' C.

open Set Topology open scoped Pointwise universe u v variable {H : Type u} {K : Type v} variable [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] variable [NormedAddCommGroup K] [InnerProductSpace ℝ K] [CompleteSpace K] theorem zero_mem_strongRelativeInterior_sub_image_of_regularity {C : Set H} {D : Set K} (hC_nonempty : C.Nonempty) (hD_nonempty : D.Nonempty) (hC_convex : Convex ℝ C) (hD_convex : Convex ℝ D) (L : H →L[ℝ] K) (h : strongRelativeInteriorSubImageRegularity C D L) : (0 : K) ∈ sri (D - L '' C)

Proposition 6.20

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

Source header · Attribution source

The intersection of the sets preceding the (i + 2)-nd term of a finite family.

open Set Topology open scoped Pointwise universe u variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] def previousIntersection (n : ℕ) (C : Fin (n + 2) → Set H) (i : Fin (n + 1)) : Set H := ⋂ j : Fin i.1.succ, C (Fin.castLT j (Nat.lt_trans j.2 i.succ.isLt))

Proposition 6.21

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

Source header · Attribution source

Proposition 6.21 (1): for nonempty convex sets C and D, the origin belongs to the strong relative interior of D - L '' C exactly when the origin of the product space belongs to the strong relative interior of C ×ˢ D - gra L.

open Set open scoped Pointwise universe u v variable {H : Type u} {K : Type v} variable [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] variable [NormedAddCommGroup K] [InnerProductSpace ℝ K] [CompleteSpace K] theorem zero_mem_strongRelativeInterior_sub_image_iff_zero_mem_strongRelativeInterior_prod_sub_graph {C : Set H} {D : Set K} (hC_nonempty : C.Nonempty) (hD_nonempty : D.Nonempty) (hC_convex : Convex ℝ C) (hD_convex : Convex ℝ D) (L : H →L[ℝ] K) : (0 : K) ∈ sri (D - L '' C) ↔ (0 : H × K) ∈ sri (C ×ˢ D - (L.toLinearMap.graph : Set (H × K)))

Definition 6.22

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

Source header · Attribution source

Definition 6.22 (1): the polar cone Cᵒ⊖ of C consists of the vectors u such that the inner-product supremum of C at u is nonpositive.

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

Proposition 6.23

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

Source header · Attribution source

Proposition 6.23: if C is a linear subspace of a real Hilbert space, then its negative and positive polar cones are both equal to the orthogonal complement Cᗮ, hence to each other and to the textbook orthogonal set C^⊥.

universe u open scoped InnerProductSpace Pointwise namespace Set variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] -- Proof sketch: use `mem_negativePolar`, `mem_positivePolar`, and `Submodule.mem_orthogonal`. -- Because a submodule is closed under negation, the nonpositive and nonnegative inner-product -- inequalities force vanishing, and conversely vanishing implies both inequalities. theorem negativePolar_and_positivePolar_eq_orthogonal_of_submodule (C : Submodule ℝ E) : negativePolar (C : Set E) = (Cᗮ : Set E) ∧ positivePolar (C : Set E) = (Cᗮ : Set E)

Proposition 6.24

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

Source header · Attribution source

Proposition 6.24 (1): textbook clause (i) for the negative polar cone. If D ⊆ C, then C^⊖ ⊆ D^⊖.

open Set open scoped Pointwise InnerProductSpace universe u namespace Set variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] theorem negativePolar_subset_of_subset {C D : Set E} (hDC : D ⊆ C) : negativePolar C ⊆ negativePolar D

Example 6.25

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

Source header · Attribution source

Example 6.25: the coordinatewise nonnegative cone ℓ²₊(I) in ℓ²(I, ℝ) is self-dual.

open scoped InnerProductSpace universe u variable {I : Type u} theorem ell2PositiveOrthant_isSelfDual : ({x : lp (fun _ : I ↦ ℝ) 2 | ∀ i, 0 ≤ x i} : Set (lp (fun _ : I ↦ ℝ) 2)).IsSelfDual

Example 6.26

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

Source header · Attribution source

Example 6.26: the cone of positive semidefinite matrices in the real symmetric matrix space 𝕊^N, modeled by the canonical self-adjoint submodule of N × N real matrices, is self-dual.

theorem posSemidefSymmetricMatrixCone_isSelfDual (N : ℕ) : ({A : ↥(selfAdjoint.submodule ℝ (Matrix (Fin N) (Fin N) ℝ)) | A.1.PosSemidef} : Set ↥(selfAdjoint.submodule ℝ (Matrix (Fin N) (Fin N) ℝ))).IsSelfDual

Proposition 6.27

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

Source header · Attribution source

Proposition 6.27 (1): if K₁ and K₂ are nonempty cones in a real inner product space, then the polar cone of their pointwise sum is the intersection of their polar cones.

open scoped InnerProductSpace Pointwise universe u namespace Set variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] theorem polarCone_add_eq_inter {K₁ K₂ : Set 𝓗} (hK₁_cone : IsCone K₁) (hK₁_nonempty : K₁.Nonempty) (hK₂_cone : IsCone K₂) (hK₂_nonempty : K₂.Nonempty) : (K₁ + K₂)ᵒ⊖ = K₁ᵒ⊖ ∩ K₂ᵒ⊖

Proposition 6.28

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

Source header · Attribution source

Proposition 6.28 (1): if p is the projection of x onto the proper cone K, then p ∈ K.

open Set open scoped InnerProductSpace Pointwise universe u variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] [CompleteSpace 𝓗] theorem mem_of_eq_projectionPoint_on_properCone (K : ProperCone ℝ 𝓗) {x p : 𝓗} (hp : p = projectionPoint (K : Set 𝓗) (properConeProjectionChebyshev K) x) : p ∈ K

Example 6.29

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

Source header · Attribution source

Example 6.29: the metric projection onto the coordinatewise nonnegative cone in ℓ²(I, ℝ) is the coordinatewise positive part.

universe u open scoped InnerProductSpace Pointwise variable {I : Type u} local notation "L2" => lp (fun _ : I ↦ ℝ) 2 theorem projectionPoint_l2PositiveOrthant_eq_positivePart (x : L2) : projectionPoint (l2PositiveOrthant I) (isChebyshev_of_nonempty_isClosed_convex l2PositiveOrthant_nonempty l2PositiveOrthant_isClosed l2PositiveOrthant_convex) x = l2PositivePart x

Theorem 6.30

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

Source header · Attribution source

Theorem 6.30 (1): textbook clause (i). Every vector decomposes as the sum of its projections onto a proper cone and its negative polar cone.

open scoped InnerProductSpace Pointwise universe u variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] [CompleteSpace 𝓗] -- Proof sketch: a proper cone is nonempty, closed, and convex, so apply -- `isChebyshev_of_nonempty_isClosed_convex`. theorem eq_projectionPoint_add_projectionPoint_negativePolar (K : ProperCone ℝ 𝓗) (x : 𝓗) : x = projectionPoint (K : Set 𝓗) (isChebyshev_of_properCone K) x + projectionPoint (Set.negativePolar (K : Set 𝓗)) (isChebyshev_negativePolar K) x

Corollary 6.31

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

Source header · Attribution source

Corollary 6.31 (1): clause (i). If x = y + z with y ∈ K and z ∈ Kᵒ⊖, and if z is not the projection of x onto Kᵒ⊖, then the norm of the projection of x onto K is strictly less than ‖y‖.

open Set open scoped InnerProductSpace Pointwise universe u variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] [CompleteSpace 𝓗] variable (K : ProperCone ℝ 𝓗) local notation "P" => projectionPoint (K : Set 𝓗) (isChebyshev_of_properCone K) local notation "Q" => projectionPoint (negativePolar (K : Set 𝓗)) (isChebyshev_negativePolar K) theorem norm_projectionPoint_lt_norm_of_decomposition {x y z : 𝓗} (hy : y ∈ (K : Set 𝓗) \ {P x}) (hz : z ∈ negativePolar (K : Set 𝓗) \ {Q x}) (hx : x = y + z) : ‖P x‖ < ‖y‖

Proposition 6.32

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

Source header · Attribution source

Proposition 6.32: if the inner product of x with the residual from its metric projection onto a nonempty closed convex cone K is nonpositive, then x already belongs to K.

open scoped InnerProductSpace universe u variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] [CompleteSpace 𝓗] variable (K : ProperCone ℝ 𝓗) local notation "P" => projectionPoint (K : Set 𝓗) (isChebyshev_of_nonempty_isClosed_convex K.nonempty K.isClosed K.convex) theorem mem_of_inner_sub_projectionPoint_nonpos_of_properCone (x : 𝓗) (hinner : ⟪x, x - P x⟫_ℝ ≤ 0) : x ∈ K

Proposition 6.33

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

Source header · Attribution source

Proposition 6.33: for a nonempty convex subset C of a real Hilbert space, the double polar cone of C is the closure of the cone generated by C.

open scoped InnerProductSpace Pointwise universe u namespace Set variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] [CompleteSpace 𝓗] theorem polarCone_polarCone_eq_closure_cone_of_nonempty_convex {C : Set 𝓗} (hC_nonempty : C.Nonempty) (hC_convex : Convex ℝ C) : (Cᵒ⊖)ᵒ⊖ = closure (cone C)

Corollary 6.34

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

Source header · Attribution source

Corollary 6.34: the bipolar theorem for a nonempty closed convex cone in a real Hilbert space is canonically formalized by ProperCone.innerDual_innerDual, stating that a proper cone equals its double inner dual.

recall ProperCone.innerDual_innerDual

Proposition 6.35

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

Source header · Attribution source

Proposition 6.35: if K₁ and K₂ are nonempty convex cones in a real Hilbert space, then the polar cone of closure K₁ ∩ closure K₂ is the closure of the sum of the polar cones of K₁ and K₂. This is the formula obtained by polarizing the identity in the proof; the raw sum need not be closed in an infinite-dimensional Hilbert space.

open scoped InnerProductSpace Pointwise universe u namespace Set variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] [CompleteSpace 𝓗] theorem polarCone_inter_closure_eq_closure_add_polarCone {K₁ K₂ : Set 𝓗} (hK₁_nonempty : K₁.Nonempty) (hK₁_convex : Convex ℝ K₁) (hK₁_cone : IsCone K₁) (hK₂_nonempty : K₂.Nonempty) (hK₂_convex : Convex ℝ K₂) (hK₂_cone : IsCone K₂) : (closure K₁ ∩ closure K₂)ᵒ⊖ = closure (K₁ᵒ⊖ + K₂ᵒ⊖)

Theorem 6.36

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

Source header · Attribution source

Theorem 6.36: for a finite family (uᵢ) indexed by a finite type ι, membership of v in the cone ∑ i, ℝ₊ uᵢ, represented in Lean by PointedCone.hull ℝ (range u), is equivalent to the containment ⋂ i, ({uᵢ}ᵒ⊖) ⊆ ({v}ᵒ⊖).

universe u v namespace Set variable {ι : Type v} {𝓗 : Type u} variable [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] local notation "polarDual" => PointedCone.dual (-innerₗ 𝓗) theorem mem_pointedConeHull_range_iff_iInter_polarCone_singleton_subset (hι : Finite ι) {u : ι → 𝓗} {v : 𝓗} : v ∈ (PointedCone.hull ℝ (range u) : Set 𝓗) ↔ (⋂ i, ({u i} : Set 𝓗)ᵒ⊖) ⊆ ({v} : Set 𝓗)ᵒ⊖

Theorem 6.37

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

Source header · Attribution source

Theorem 6.37 (1): the polar cone of the preimage of a nonempty closed convex cone under a continuous linear map is the closure of the adjoint image of the polar cone of that cone.

open Set open scoped InnerProductSpace Pointwise universe u v variable {𝓗 : Type u} {𝓚 : Type v} variable [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] [CompleteSpace 𝓗] variable [NormedAddCommGroup 𝓚] [InnerProductSpace ℝ 𝓚] [CompleteSpace 𝓚] theorem polarCone_preimage_eq_closure_adjoint_image_polarCone (L : 𝓗 →L[ℝ] 𝓚) (K : ProperCone ℝ 𝓚) : (L ⁻¹' (K : Set 𝓚))ᵒ⊖ = closure (L.adjoint '' ((K : Set 𝓚)ᵒ⊖))

Definition 6.38

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

Source header · Attribution source

Definition 6.38 (1): the tangent cone to C at x is the closure of the cone generated by C - x when x ∈ C, and it is empty otherwise.

open scoped InnerProductSpace Pointwise universe u namespace Set variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] noncomputable def tangentCone (C : Set E) (x : E) : Set E := {v : E | x ∈ C ∧ v ∈ closure (cone (C - ({x} : Set E)))}

Example 6.39

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

Source header · Attribution source

Example 6.39 (1): at a boundary point of the closed unit ball, the tangent cone is the closed half-space of directions whose inner product with the boundary point is nonpositive.

open scoped InnerProductSpace Pointwise universe u variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] local notation "C" => Metric.closedBall (0 : H) 1 theorem tangentCone_closedUnitBall_eq_inner_nonpos_of_norm_eq_one {x : H} (hx : ‖x‖ = 1) : Set.tangentCone (Metric.closedBall (0 : H) 1) x = {y : H | ⟪y, x⟫_ℝ ≤ 0}

Example 6.40

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

Source header · Attribution source

Example 6.40 (1): if K is a convex cone in a real Hilbert space and x ∈ K, then the tangent cone at x is the closure of K + ℝ x, represented in Lean as the set sum with the line ℝ ∙ x.

open scoped Pointwise InnerProductSpace universe u namespace Set local postfix:100 "ᵒ⊖" => Set.negativePolar variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] [CompleteSpace 𝓗] theorem tangentCone_eq_closure_add_line_of_mem_convex_cone {K : Set 𝓗} (hK_cone : IsCone K) (hK_convex : Convex ℝ K) {x : 𝓗} (hx : x ∈ K) : T[K] x = closure (K + (ℝ ∙ x : Set 𝓗))

Example 6.41

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

Source header · Attribution source

Example 6.41: at a point x of the positive orthant in ℓ²(I), the normal cone consists exactly of the vectors with nonpositive coordinates that satisfy the complementary-slackness relations x i * v i = 0 coordinatewise.

open scoped InnerProductSpace universe u variable {I : Type u} local notation "E" => lp (fun _ : I ↦ ℝ) 2 theorem normalCone_ell2PositiveOrthant_eq_setOf_nonpos_mul_eq_zero {x : E} (hx : x ∈ ({ξ : E | ∀ i, 0 ≤ ξ i} : Set E)) : Set.normalCone ({ξ : E | ∀ i, 0 ≤ ξ i} : Set E) x = {v : E | ∀ i, v i ≤ 0 ∧ x i * v i = 0}

Example 6.42

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

Source header · Attribution source

Example 6.42 (1): at a point of the positive orthant in ℝ^N, membership in the normal cone is equivalent to having nonpositive coordinates where x vanishes and zero coordinates where x is strictly positive.

open scoped InnerProductSpace Pointwise variable {N : ℕ} local notation "E" => PiLp 2 fun _ : Fin N ↦ ℝ theorem mem_normalCone_positiveOrthant_iff {x y : E} (hx : x ∈ ({ξ : E | ∀ i, 0 ≤ ξ i} : Set E)) : y ∈ Set.normalCone ({ξ : E | ∀ i, 0 ≤ ξ i} : Set E) x ↔ ∀ i : Fin N, (x i = 0 → y i ≤ 0) ∧ (0 < x i → y i = 0)

Example 6.43

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

Source header · Attribution source

Example 6.43 (1): if x ∈ C, then the tangent cone to the affine subspace C is the closure of the parallel linear subspace V = C - C, expressed in Lean as closure (C.direction : Set H).

open scoped InnerProductSpace Pointwise universe u variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] theorem tangentCone_affineSubspace_eq_closure_direction_of_mem (C : AffineSubspace ℝ H) {x : H} (hx : x ∈ (C : Set H)) : Set.tangentCone (C : Set H) x = closure (C.direction : Set H)

Proposition 6.44

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

Source header · Attribution source

Proposition 6.44 (1): at a point of a set, the polar cone of the tangent cone equals the normal cone.

open scoped InnerProductSpace Pointwise universe u namespace Set variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] [CompleteSpace 𝓗] theorem polarCone_tangentCone_eq_normalCone_of_mem {C : Set 𝓗} {x : 𝓗} (hC_convex : Convex ℝ C) (hx : x ∈ C) : (T[C] x)ᵒ⊖ = N[C] x

Proposition 6.45

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

Source header · Attribution source

Proposition 6.45 (i) ↔ (ii): for a convex subset C of a real normed space with nonempty interior and a point x ∈ C, the point x lies in interior C if and only if the tangent cone T[C] x is the whole space.

open scoped InnerProductSpace Pointwise universe u namespace Set variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] variable {C : Set E} {x : E} -- Proof sketch: apply Proposition 6.17 to the translated convex set `C - {x}`. Translation by -- `-x` identifies `x ∈ interior C` with `0 ∈ interior (C - {x})`, and `tangentCone_of_mem hx` -- identifies the tangent cone with `closure (cone (C - {x}))`. theorem mem_interior_iff_tangentCone_eq_univ_of_convex (hC_convex : Convex ℝ C) (hC_int_nonempty : (interior C).Nonempty) (hx : x ∈ C) : x ∈ interior C ↔ T[C] x = (univ : Set E)

Proposition 6.46

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

Source header · Attribution source

Proposition 6.46: for a convex subset C of a finite-dimensional real Hilbert space and a point x ∈ C, the following are equivalent: x ∈ interior C, the tangent cone T[C] x is the whole space, and the normal cone N[C] x is trivial.

open scoped InnerProductSpace Pointwise universe u namespace Set variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] [FiniteDimensional ℝ 𝓗] -- Proof sketch: every vector orthogonal to the direction of `affineSpan ℝ C` annihilates each -- difference `y - x` with `y ∈ C`, hence belongs to `N[C] x`. If `N[C] x = {0}`, then the -- orthogonal complement of `(affineSpan ℝ C).direction` is trivial, so the direction is `⊤`. -- Therefore `affineSpan ℝ C = ⊤`, which makes `interior C` nonempty in finite dimension; then `x` -- lies in the interior. theorem mem_interior_tfae_tangentCone_eq_univ_normalCone_eq_singleton_zero_of_convex_finiteDimensional {C : Set 𝓗} {x : 𝓗} (hC_convex : Convex ℝ C) (hx : x ∈ C) : List.TFAE [ x ∈ interior C, T[C] x = (univ : Set 𝓗), N[C] x = ({0} : Set 𝓗) ]

Proposition 6.47

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

Source header · Attribution source

Proposition 6.47: for a nonempty closed convex subset C of a real Hilbert space, a point p is the metric projection of x onto C if and only if the residual vector x - p belongs to the normal cone of C at p.

open scoped InnerProductSpace Pointwise universe u variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] variable {C : Set 𝓗} (hC_nonempty : C.Nonempty) (hC_closed : IsClosed C) (hC_convex : Convex ℝ C) variable [CompleteSpace 𝓗] local notation "P" => projectionPoint C (isChebyshev_of_nonempty_isClosed_convex hC_nonempty hC_closed hC_convex) theorem eq_projectionPoint_iff_sub_mem_normalCone_of_nonempty_isClosed_convex {x p : 𝓗} : p = P x ↔ x - p ∈ Set.normalCone C p

Definition 6.48

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

Source header · Attribution source

Definition 6.48 (1): the recession cone rec C is the set of vectors x such that x + C ⊆ C, written in Lean as {x} + C ⊆ C.

open scoped Pointwise InnerProductSpace universe u namespace Set variable {E : Type u} [Add E] def recessionCone (C : Set E) : Set E := {x : E | ({x} : Set E) + C ⊆ C}

Proposition 6.49

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

Source header · Attribution source

Proposition 6.49 (1): for a convex set C, the recession cone rec C is convex.

open scoped InnerProductSpace Pointwise universe u namespace Set variable {E : Type u} [AddCommGroup E] [Module ℝ E] theorem recessionCone_convex {C : Set E} (hC_convex : Convex ℝ C) : Convex ℝ (rec C)

Corollary 6.50

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

Source header · Attribution source

Corollary 6.50: the recession cone of a nonempty closed convex cone in a real Hilbert space equals the cone itself.

universe u namespace Set variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] [CompleteSpace 𝓗] open scoped Pointwise Topology theorem recessionCone_eq_self_of_nonempty_isClosed_convex_isCone {K : Set 𝓗} (hK_nonempty : K.Nonempty) (hK_closed : IsClosed K) (hK_convex : Convex ℝ K) (hK_cone : IsCone K) : rec K = K

Proposition 6.51

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

Source header · Attribution source

Proposition 6.51: for a nonempty closed convex set C and a vector x, membership of x in rec C is equivalent to the existence of sequences xₙ ∈ C and αₙ ∈ ]0, 1] with αₙ → 0 such that αₙ • xₙ → x strongly, and also equivalent to the analogous weak convergence statement.

open Filter open scoped Topology InnerProductSpace Pointwise universe u namespace Set variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] theorem mem_recessionCone_tfae_exists_scaled_sequence_tendsto (C : Set 𝓗) (x : 𝓗) (hC_nonempty : C.Nonempty) (hC_closed : IsClosed C) (hC_convex : Convex ℝ C) : List.TFAE [x ∈ rec C, HasStrongScaledApproximation C x, HasWeakScaledApproximation C x]

Corollary 6.52

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

Source header · Attribution source

Corollary 6.52: for a nonempty closed convex subset C of a finite-dimensional real normed space, C is bounded if and only if its recession cone is the singleton {0}.

open Filter open scoped Topology Pointwise universe u namespace Set variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [NormedSpace ℝ 𝓗] [FiniteDimensional ℝ 𝓗] theorem bounded_iff_recessionCone_eq_singleton_zero_of_nonempty_isClosed_convex (C : Set 𝓗) (hC_nonempty : C.Nonempty) (hC_closed : IsClosed C) (hC_convex : Convex ℝ C) : Bornology.IsBounded C ↔ rec C = ({0} : Set 𝓗)

Corollary 6.53

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

Source header · Attribution source

Corollary 6.53: if C is a nonempty closed convex subset of a real inner-product space and 0 ∉ C, then cone C ∪ rec C is the closure of cone C.

open Filter open scoped Topology InnerProductSpace Pointwise universe u namespace Set variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] theorem cone_union_recessionCone_eq_closure_cone_of_nonempty_isClosed_convex_zero_not_mem (C : Set 𝓗) (hC_nonempty : C.Nonempty) (hC_closed : IsClosed C) (hC_convex : Convex ℝ C) (h0C : (0 : 𝓗) ∉ C) : cone C ∪ rec C = closure (cone C)