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.
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.
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 ℝ) • CProposition 6.3
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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 ⊆ CProposition 6.4
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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.
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.
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.
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.
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.
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.
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 CFact 6.13
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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 ℝ CCorollary 6.15
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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 CProposition 6.16
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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.
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.
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.
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.
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.
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.
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.
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 DExample 6.25
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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)).IsSelfDualExample 6.26
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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) ℝ))).IsSelfDualProposition 6.27
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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 ∈ KExample 6.29
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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 xTheorem 6.30
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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) xCorollary 6.31
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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 ∈ KProposition 6.33
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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_innerDualProposition 6.35
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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] xProposition 6.45
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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.
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 pDefinition 6.48
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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.
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 = KProposition 6.51
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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.
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)