Chapter 04 — Convexity and Notions of Nonexpansiveness

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

Definition 4.1

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

Source header · Attribution source

Definition 4.1: the fixed-point set of T in D is D ∩ Function.fixedPoints T.

universe u open Function Set variable {α : Type u} theorem fixedPointSetOn_eq_inter_fixedPoints (D : Set α) (T : α → α) : fixedPointSetOn D T = D ∩ fixedPoints T

Proposition 4.2

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

Source header · Attribution source

Proposition 4.2: for a map T : D → E, firm quasinonexpansiveness, quasinonexpansiveness of the reflected map 2T - Id, and the three equivalent fixed-point inner-product inequalities from (iii), (iv), and (v) are all equivalent.

open scoped RealInnerProductSpace universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] variable {D : Set E} theorem firmly_quasinonexpansive_on_tfae (T : D → E) : [ IsFirmlyQuasinonexpansiveOn T, IsQuasinonexpansiveOn (fun x : D ↦ (2 : ℝ) • T x - (x : E)), tx_norm_sq_le_inner_on_fixedPoints T, inner_yTx_xTx_nonpos_on_fixedPoints T, displacement_norm_sq_le_inner_on_fixedPoints T ].TFAE

Proposition 4.3

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

Source header · Attribution source

Proposition 4.3: if T is firmly quasinonexpansive on D, then every nonnegative relaxation x ↦ (1 - λ) • x + λ • T x satisfies the estimate ‖((1 - λ) • x + λ • T x) - y‖^2 ≤ ‖x - y‖^2 - λ (2 - λ) ‖T x - x‖^2 at every fixed point y of T in D.

universe u variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] theorem sq_norm_relaxedMap_sub_fixedPoint_le {D : Set H} {T : D → H} (hT : IsFirmlyQuasinonexpansiveOn T) {lam : ℝ} (hlam : 0 ≤ lam) (x y : D) (hy : T y = (y : H)) : ‖((1 - lam) • (x : H) + lam • T x) - (y : H)‖ ^ 2 ≤ ‖(x : H) - y‖ ^ 2 - lam * (2 - lam) * ‖T x - (x : H)‖ ^ 2

Proposition 4.4

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

Source header · Attribution source

Proposition 4.4: for an operator on a subset of a real Hilbert space, firm nonexpansiveness, firm nonexpansiveness of Id - T, nonexpansiveness of 2T - Id, and the equivalent inequalities in (iv), (v), and (vi) form a TFAE list.

open SubtypeFirmness -- Declarations for this item will be appended below by the statement pipeline. universe u variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] theorem firmlyNonexpansiveOn_tfae (D : Set H) (T : D → H) : List.TFAE [ FirmlyNonexpansiveOn D T, FirmlyNonexpansiveOn D (residualMap D T), ∀ x y : D, ‖reflectedMap D T x - reflectedMap D T y‖ ≤ ‖(x : H) - y‖, ∀ x y : D, ‖T x - T y‖ ^ 2 ≤ inner ℝ ((x : H) - y) (T x - T y), ∀ x y : D, 0 ≤ inner ℝ (T x - T y) (residualMap D T x - residualMap D T y), ∀ (x y : D) (α : ℝ), α ∈ Set.Icc (0 : ℝ) 1 → ‖T x - T y‖ ≤ ‖α • ((x : H) - y) + (1 - α) • (T x - T y)‖ ]

Corollary 4.5

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

Source header · Attribution source

For a bounded linear operator on a real Hilbert space, firm nonexpansiveness, the norm bound ‖2T - Id‖ ≤ 1, the pointwise inequality ‖T x‖² ≤ ⟪x, T x⟫, firm nonexpansiveness of the adjoint, and positivity of T + T† - 2 T†T are equivalent.

open SubtypeFirmness -- Declarations for this item will be appended below by the statement pipeline. open ContinuousLinearMap open scoped InnerProductSpace universe u variable {H : Type u} variable [NormedAddCommGroup H] [InnerProductSpace ℝ H] -- Proof sketch: use the polarization identity -- `‖(2 • T - id) u‖ ^ 2 = ‖u‖ ^ 2 + 4 * ‖T u‖ ^ 2 - 4 * ⟪u, T u⟫_ℝ` to identify clauses -- (i), (ii), and (iii); transfer (ii) across adjoints using `‖T.adjoint‖ = ‖T‖`; and rewrite -- clause (iii) as positivity of `T + T.adjoint - 2 • T.adjoint.comp T`. variable [CompleteSpace H] theorem tfae_firmly_nonexpansive_adjoint_norm_quadratic (T : H →L[ℝ] H) : List.TFAE [ FirmlyNonexpansiveOn (Set.univ : Set H) (fun x : Set.univ ↦ T x), ‖(2 : ℝ) • T - 1‖ ≤ 1, ∀ x : H, ‖T x‖ ^ (2 : ℕ) ≤ ⟪x, T x⟫_ℝ, FirmlyNonexpansiveOn (Set.univ : Set H) (fun x : Set.univ ↦ T.adjoint x), (T + T.adjoint - (2 : ℝ) • (T.adjoint.comp T)).IsPositive ]

Proposition 4.6

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

Source header · Attribution source

Proposition 4.6 (1): the squared norm of the weighted average difference equals the weighted sum of squared norms minus the pairwise variance term.

open scoped BigOperators universe u ι variable {E : Type u} variable [NormedAddCommGroup E] variable {I : Type ι} [Fintype I] variable [NormedSpace ℝ E] variable {D : Set E} variable [InnerProductSpace ℝ E] [CompleteSpace E] [Nonempty I] -- Proof sketch: apply the weighted variance identity in a real Hilbert space to the family of -- vectors `T i x - T i y`. theorem weightedOperatorAverage_norm_sq_eq_weighted_norm_sq_sub_pairwise (ω : I → ℝ) (T : I → D → E) (hT : ∀ i, IsFirmlyNonexpansiveOn (T i)) (hω_mem : ∀ i, ω i ∈ Set.Ioc (0 : ℝ) 1) (hω_sum : ∑ i : I, ω i = 1) (x y : D) : ‖weightedOperatorAverage ω T x - weightedOperatorAverage ω T y‖ ^ 2 = ∑ i : I, ω i * ‖T i x - T i y‖ ^ 2 - (1 / 2 : ℝ) * ∑ i : I, ∑ j : I, ω i * ω j * ‖(T i x - T i y) - (T j x - T j y)‖ ^ 2

Proposition 4.8

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

Source header · Attribution source

Proposition 4.8 (1): Zarantonello's weighted identity for the family i ↦ (T (x i), x i - T (x i)) at the affine combination y = ∑ i ∈ s, α i • x i.

open SubtypeFirmness -- Declarations for this item will be appended below by the statement pipeline. universe u v open scoped BigOperators InnerProductSpace variable {ι : Type u} {H : Type v} [NormedAddCommGroup H] [InnerProductSpace ℝ H] theorem zarantonello_weighted_firm_identity (s : Finset ι) (T : H → H) (x : ι → H) (α : ι → ℝ) (y : H) (hy : y = ∑ i ∈ s, α i • x i) (hα_sum : ∑ i ∈ s, α i = 1) : ‖T y - ∑ i ∈ s, α i • T (x i)‖ ^ (2 : ℕ) + ∑ i ∈ s, α i * ⟪T y - T (x i), (y - T y) - (x i - T (x i))⟫_ℝ = (1 / 2 : ℝ) * ∑ i ∈ s, ∑ j ∈ s, α i * α j * ⟪T (x i) - T (x j), (x i - T (x i)) - (x j - T (x j))⟫_ℝ

Proposition 4.9

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

Source header · Attribution source

Proposition 4.9 (1): a finite convex weighted average of nonexpansive operators on D is nonexpansive.

open scoped BigOperators open Function Set universe u variable {H : Type u} [NormedAddCommGroup H] [NormedSpace ℝ H] {D : Set H} theorem lipschitzWith_weightedOperator {n : ℕ} (ω : Fin (n + 1) → ℝ) (T : Fin (n + 1) → D → H) (hT : ∀ i, LipschitzWith 1 (T i)) (hω : ∀ i, ω i ∈ Set.Icc (0 : ℝ) 1) (hω_sum : ∑ i, ω i = 1) : LipschitzWith 1 (weightedOperatorAverage ω T)

Definition 4.10

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

Source header · Attribution source

Definition 4.10: a map T : D → H on a real Hilbert space is β-cocoercive, or β-inverse strongly monotone, when β > 0 and ⟪x - y, T x - T y⟫ ≥ β ‖T x - T y‖² for all x, y ∈ D.

universe u variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] def CocoerciveOn (β : ℝ) (D : Set H) (T : D → H) : Prop := 0 < β ∧ ∀ x y : D, β * ‖T x - T y‖ ^ 2 ≤ inner ℝ ((x : H) - y) (T x - T y)

Proposition 4.11

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

Source header · Attribution source

Proposition 4.11: a map on a subset of a real inner product space is nonexpansive exactly when its residual map Id - T is 1 / 2-cocoercive.

universe u variable {H : Type u} [NormedAddCommGroup H] variable [InnerProductSpace ℝ H] theorem lipschitzWith_one_iff_residualMap_cocoerciveOn_half {D : Set H} (T : D → H) : LipschitzWith 1 T ↔ CocoerciveOn (1 / 2 : ℝ) D (residualMap D T)

Proposition 4.12

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

Source header · Attribution source

Proposition 4.12: if each Tᵢ is βᵢ-cocoercive, then the finite sum ∑ i, Lᵢ* ∘ Tᵢ ∘ Lᵢ is (∑ i, ‖Lᵢ‖² / βᵢ)⁻¹-cocoercive for a nonempty finite family.

universe u v w open ContinuousLinearMap open scoped BigOperators InnerProductSpace variable {ι : Type v} {H : Type u} {K : ι → Type w} variable [Fintype ι] variable [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] variable [∀ i, NormedAddCommGroup (K i)] [∀ i, InnerProductSpace ℝ (K i)] variable [∀ i, CompleteSpace (K i)] theorem cocoerciveOn_univ_adjointCompositeFamilySum [Nonempty ι] (L : ∀ i, H →L[ℝ] K i) (βi : ι → ℝ) (T : ∀ i, K i → K i) (hL : ∀ i, L i ≠ 0) (hT : ∀ i, CocoerciveOn (βi i) Set.univ (fun x : Set.univ ↦ T i x)) : CocoerciveOn (1 / ∑ i, ‖L i‖ ^ (2 : ℕ) / βi i) Set.univ (fun x : Set.univ ↦ adjointCompositeFamilySum L T x)

Corollary 4.13

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

Source header · Attribution source

Corollary 4.13: if T is firmly nonexpansive on the real Hilbert space K in the standard inner-product form and L : H →L[ℝ] K has operator norm at most 1, then the compressed map L.adjoint ∘ T ∘ L is firmly nonexpansive on H.

open SubtypeFirmness -- Declarations for this item will be appended below by the statement pipeline. open ContinuousLinearMap open scoped InnerProductSpace universe u v variable {H : Type u} {K : Type v} variable [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] variable [NormedAddCommGroup K] [InnerProductSpace ℝ K] [CompleteSpace K] -- Rewrite the compressed inner product on `H` as the corresponding inner product on `K`. theorem adjoint_comp_firmlyNonexpansive_of_norm_le_one (T : K → K) (hT : FirmlyNonexpansiveOn (Set.univ : Set K) (fun x : Set.univ ↦ T x)) (L : H →L[ℝ] K) (hL : ‖L‖ ≤ 1) : FirmlyNonexpansiveOn (Set.univ : Set H) (fun x : Set.univ ↦ (L.adjoint ∘ T ∘ L) x)

Example 4.14

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

Source header · Attribution source

Example 4.14: if T : H → H is firmly nonexpansive, then for every closed linear subspace V the compressed operator P_V ∘ T ∘ P_V is firmly nonexpansive.

open SubtypeFirmness -- Declarations for this item will be appended below by the statement pipeline. open scoped InnerProductSpace universe u variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] theorem orthogonal_projection_compression_firmly_nonexpansive (V : ClosedSubmodule ℝ H) {T : H → H} (hT : FirmlyNonexpansiveOn Set.univ (fun x ↦ T x)) : FirmlyNonexpansiveOn Set.univ (fun x ↦ (V.starProjection ∘ T ∘ V.starProjection) x)

Remark 4.15.1

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

Source header · Attribution source

Remark 4.15.1: a β-cocoercive map on a subset of a real Hilbert space is Lipschitz with constant 1 / β.

universe u variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] theorem lipschitzWith_of_cocoercive {D : Set H} {β : ℝ} {T : D → H} (hT : CocoerciveOn β D T) : LipschitzWith (Real.toNNReal (1 / β)) T

Remark 4.15.2

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

Source header · Attribution source

Remark 4.15.2: the cyclic difference operator associated to B = [[1, -1, 0], [0, 1, -1], [-1, 0, 1]] is 1 / 2-cocoercive on ℝ^3 and is √3-Lipschitz continuous.

open scoped Matrix local notation "R3" => EuclideanSpace ℝ (Fin 3) theorem cyclic_difference_operator_cocoercive_and_lipschitz : CocoerciveOn (1 / 2 : ℝ) Set.univ (fun x : Set.univ ↦ cyclic_difference_operator x) ∧ LipschitzWith (NNReal.sqrt 3) cyclic_difference_operator

Proposition 4.16

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

Source header · Attribution source

Proposition 4.16: the metric projection onto a nonempty closed convex subset of a real Hilbert space is firmly nonexpansive: for all x and y, the canonical projection map P := projectionPoint C (isChebyshev_of_nonempty_isClosed_convex hC_nonempty hC_closed hC_convex) satisfies ‖P x - P y‖^2 ≤ ⟪P x - P y, x - y⟫_ℝ.

universe u open scoped InnerProductSpace 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 norm_sq_projectionPoint_sub_le_inner_projectionPoint_sub_of_nonempty_isClosed_convex (x y : 𝓗) : ‖P x - P y‖ ^ (2 : ℕ) ≤ ⟪P x - P y, x - y⟫_ℝ

Example 4.17

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

Source header · Attribution source

Example 4.17 (1): for positive level ρ, the soft thresholder is firmly nonexpansive.

universe u open scoped InnerProductSpace variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] theorem softThresholder_firmlyNonexpansive [CompleteSpace H] (ρ : ℝ) (hρ : 0 < ρ) : FirmlyNonexpansiveOn (Set.univ : Set H) (softThresholder ρ : H → H)

Corollary 4.18

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

Source header · Attribution source

Corollary 4.18: if P is the canonical metric projection onto a nonempty closed convex subset C of a real Hilbert space, then its residual map Id - P is firmly nonexpansive and its reflector 2P - Id is nonexpansive.

open SubtypeFirmness -- Declarations for this item will be appended below by the statement pipeline. universe u open scoped InnerProductSpace variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] [CompleteSpace 𝓗] variable {C : Set 𝓗} variable (hC_nonempty : C.Nonempty) (hC_closed : IsClosed C) (hC_convex : Convex ℝ C) local notation "P" => fun x : Set.univ ↦ projectionPoint C (isChebyshev_of_nonempty_isClosed_convex hC_nonempty hC_closed hC_convex) (x : 𝓗) theorem metricProjection_residual_firmlyNonexpansive_and_reflection_nonexpansive : FirmlyNonexpansiveOn (Set.univ : Set 𝓗) (residualMap (Set.univ : Set 𝓗) P) ∧ LipschitzWith 1 (reflectedMap (Set.univ : Set 𝓗) P)

Proposition 4.19

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

Source header · Attribution source

Proposition 4.19 (1): for a nonempty closed affine subspace of a real Hilbert space, the metric projector P is weakly continuous on the ambient space.

universe u open EuclideanGeometry open scoped InnerProductSpace variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] [CompleteSpace 𝓗] variable {C : AffineSubspace ℝ 𝓗} variable (hC_nonempty : (C : Set 𝓗).Nonempty) (hC_closed : IsClosed (C : Set 𝓗)) local notation "P" => @projectionPoint 𝓗 inferInstance (C : Set 𝓗) (isChebyshev_of_nonempty_isClosed_convex hC_nonempty hC_closed C.convex) theorem projectionPoint_weaklyContinuous_of_nonempty_isClosed_affineSubspace : WeaklyContinuous (fun x : (Set.univ : Set 𝓗) ↦ P x)

Example 4.20

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

Source header · Attribution source

Example 4.20: in an infinite-dimensional real Hilbert space, the metric projector onto the closed unit ball is not weakly continuous.

open scoped InnerProductSpace Topology open Filter universe u variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] local notation "C" => Metric.closedBall (0 : H) 1 local notation "P" => projectionPoint C (isChebyshev_of_nonempty_isClosed_convex closedUnitBall_nonempty (Metric.isClosed_closedBall : IsClosed C) (convex_closedBall (0 : H) 1)) theorem closedUnitBallProjector_not_weaklyContinuous (h_infinite : ¬ FiniteDimensional ℝ H) : ¬ WeaklyContinuous (fun x : (Set.univ : Set H) ↦ P x)

Proposition 4.21

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

Source header · Attribution source

Proposition 4.21: if C is a nonempty closed convex subset of a real Hilbert space, z ∈ H, every weak sequential cluster point of a sequence xₙ belongs to C, and the nonnegative distance sequence satisfies the canonical ℝ≥0∞ limsup bound limsup ‖xₙ - z‖ ≤ dist(z, C), then xₙ converges strongly to the metric projection of z onto C.

open Filter open scoped Topology InnerProductSpace universe u variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] theorem tendsto_projectionPoint_of_limsup_norm_sub_le_infDist_of_weakSequentialClusterPts_mem {C : Set H} (hC_nonempty : C.Nonempty) (hC_closed : IsClosed C) (hC_convex : Convex ℝ C) (z : H) (xₙ : ℕ → H) (hlimsup : Filter.limsup (fun n ↦ ENNReal.ofReal (‖xₙ n - z‖)) atTop ≤ ENNReal.ofReal (Metric.infDist z C)) (hcluster : ∀ x : H, IsSequentialClusterPt (fun n ↦ toWeakSpace ℝ H (xₙ n)) (toWeakSpace ℝ H x) → x ∈ C) : Tendsto xₙ atTop (𝓝 (projectionPoint C (isChebyshev_of_nonempty_isClosed_convex hC_nonempty hC_closed hC_convex) z))

Text 4.21.1

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

Source header · Attribution source

Text 4.21.1 (1): the metric projection onto a nonempty closed convex subset of a real Hilbert space is firmly nonexpansive.

open SubtypeFirmness -- Declarations for this item will be appended below by the statement pipeline. universe u open scoped InnerProductSpace variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] [CompleteSpace 𝓗] variable {C : Set 𝓗} variable (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) -- Proof sketch: apply the projection characterization from -- `eq_projectionPoint_iff_mem_and_inner_sub_right_nonpos_of_nonempty_isClosed_convex` to `P x` -- with test point `P y`, and to `P y` with test point `P x`; adding the resulting inequalities and -- rearranging yields the displayed firm nonexpansiveness inequality. theorem firmlyNonexpansive_projectionPoint_of_nonempty_isClosed_convex : FirmlyNonexpansive P

Proposition 4.22

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

Source header · Attribution source

Proposition 4.22: if D is a nonempty convex subset of a real Hilbert space and T is quasinonexpansive on D, then the fixed-point set of T in D is convex.

universe u open Function Set variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] theorem convex_fixedPointSetOn_of_quasinonexpansiveOn {D : Set H} (hD : D.Nonempty) (hD_convex : Convex ℝ D) {T : H → H} (hT : QuasinonexpansiveOn D T) : Convex ℝ (fixedPointSetOn D T)

Proposition 4.23

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

Source header · Attribution source

Proposition 4.23 (1): if D is nonempty and T is quasinonexpansive on D, then the fixed point set of T in D is the intersection, over x ∈ D, of the half-spaces {y ∈ D | ⟪y - T x, x - T x⟫_ℝ ≤ (1 / 2) ‖T x - x‖^2}.

open scoped InnerProductSpace universe u variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] variable {D : Set H} {T : H → H} theorem fixedPointSetOn_eq_iInter_halfspaces_of_quasinonexpansive (hD : D.Nonempty) (hT : QuasinonexpansiveOn D T) : fixedPointSetOn D T = ⋂ x ∈ D, {y : H | y ∈ D ∧ ⟪y - T x, x - T x⟫_ℝ ≤ (1 / 2 : ℝ) * ‖T x - x‖ ^ 2}

Corollary 4.24

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

Source header · Attribution source

Corollary 4.24: if D is a nonempty closed convex subset of a real inner product space and T is nonexpansive on D, then the fixed point set Fix T = {x ∈ D | T x = x} is closed and convex.

universe u variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] theorem isClosed_and_convex_fixedPointSet_of_nonexpansiveOn {D : Set H} (_hD_nonempty : D.Nonempty) (hD_closed : IsClosed D) (hD_convex : Convex ℝ D) {T : H → H} (hT : LipschitzOnWith 1 T D) : IsClosed (fixedPointSetOn D T) ∧ Convex ℝ (fixedPointSetOn D T)

Corollary 4.25

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

Source header · Attribution source

Corollary 4.25: if D is a nonempty subset of a real Hilbert space and T is firmly quasinonexpansive on D, then the fixed points of T in D are exactly the intersection of the half-spaces {y ∈ D | ⟪y - T x, x - T x⟫_ℝ ≤ 0} over all x ∈ D.

open Set open scoped InnerProductSpace universe u variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] variable {D : Set H} {T : H → H} theorem fixedPointSetOn_eq_iInter_inner_nonpos_of_firmlyQuasinonexpansive (hD : D.Nonempty) (hT : FirmlyQuasinonexpansiveOn D T) : fixedPointSetOn D T = ⋂ x ∈ D, {y : H | y ∈ D ∧ ⟪y - T x, x - T x⟫_ℝ ≤ 0}

Definition 4.26

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

Source header · Attribution source

Definition 4.26: T : D → H is demiclosed at u if every sequence in D that converges weakly to some x ∈ D and whose image under T converges strongly to u satisfies T x = u.

universe u open Filter variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] def DemiclosedAt (D : Set H) (T : D → H) (u : H) : Prop := ∀ ⦃xₙ : ℕ → D⦄ ⦃x : D⦄, Tendsto (fun n ↦ toWeakSpace ℝ H (xₙ n : H)) atTop (nhds (toWeakSpace ℝ H (x : H))) → Tendsto (fun n ↦ T (xₙ n)) atTop (nhds u) → T x = u

Theorem 4.27

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

Source header · Attribution source

Theorem 4.27: Browder's demiclosedness principle says that if D is weakly sequentially closed in a real Hilbert space and T is nonexpansive on D, then weak convergence of a sequence in D together with norm convergence of the residuals xₙ - T xₙ forces the limit residual to be x - T x.

open Filter open scoped InnerProductSpace Topology universe u variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] theorem browder_demiclosedness_principle {D : Set H} (hD : IsSeqClosed ((toWeakSpace ℝ H) '' D)) {T : H → H} (hT : LipschitzOnWith 1 T D) {xSeq : ℕ → H} (hxSeq : ∀ n, xSeq n ∈ D) {x u : H} (hx : Tendsto (fun n ↦ toWeakSpace ℝ H (xSeq n)) atTop (𝓝 (toWeakSpace ℝ H x))) (hu : Tendsto (fun n ↦ xSeq n - T (xSeq n)) atTop (𝓝 u)) : x - T x = u

Corollary 4.28

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

Source header · Attribution source

Corollary 4.28: if D is a closed convex subset of a real Hilbert space, T : D → H is nonexpansive, xₙ converges weakly to x in D, and the residuals xₙ - T xₙ converge strongly to 0, then x is a fixed point of T.

open Filter open scoped InnerProductSpace Topology universe u variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] -- Proof sketch: closed convex subsets of a real Hilbert space are weakly sequentially closed by -- Theorem 3.34. Apply the demiclosedness principle from Theorem 4.27 to the residual map -- `x ↦ x - T x` at `0`; the residual convergence hypothesis then forces `T x = x`. theorem map_eq_of_tendsto_weakly_of_residual_tendsto_zero_of_nonexpansive {D : Set H} (_hD_closed : IsClosed D) (_hD_convex : Convex ℝ D) {T : D → H} (hT : LipschitzWith 1 T) {xₙ : ℕ → D} {x : D} (hweak : Tendsto (fun n ↦ toWeakSpace ℝ H (xₙ n : H)) atTop (𝓝 (toWeakSpace ℝ H (x : H)))) (hres : Tendsto (fun n ↦ (xₙ n : H) - T (xₙ n)) atTop (𝓝 (0 : H))) : T x = (x : H)

Theorem 4.29

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

Source header · Attribution source

Theorem 4.29: Browder--Göhde--Kirk guarantees that a nonexpansive self-map of a nonempty bounded closed convex subset of a real Hilbert space has a fixed point in that subset.

open Filter universe u open Function Set open scoped InnerProductSpace variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] -- Proof sketch: use boundedness and closed convexity of `D` in the Hilbert space to obtain weak -- sequential compactness, regularize `T` by the contractions `x ↦ α • x₀ + (1 - α) • T x`, apply -- the Banach fixed-point theorem to each regularization, extract a weakly convergent subsequence, -- and conclude with the demiclosedness principle for `id - T`. theorem browder_gohde_kirk_fixed_point {D : Set H} (hD_nonempty : D.Nonempty) (hD_bounded : Bornology.IsBounded D) (hD_closed : IsClosed D) (hD_convex : Convex ℝ D) {T : H → H} (hTD : MapsTo T D D) (hT : LipschitzOnWith 1 T D) : (D ∩ fixedPoints T).Nonempty

Proposition 4.30

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

Source header · Attribution source

Proposition 4.30 (1): for every ε ∈ ]0,1[ and every x ∈ D, there is a unique point x_ε ∈ D satisfying x_ε = εx + (1 - ε)T x_ε.

open SubtypeFirmness -- Declarations for this item will be appended below by the statement pipeline. open Filter Function Set open scoped InnerProductSpace Topology universe u variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] theorem approximatingCurvePoint_existsUnique {D : Set H} (hD_closed : IsClosed D) (hD_convex : Convex ℝ D) (T : D → D) (hT : LipschitzWith 1 T) (ε : Set.Ioo (0 : ℝ) 1) (x : D) : ∃! z : D, (z : H) = (ε : ℝ) • (x : H) + (1 - (ε : ℝ)) • (T z : H)

Proposition 4.31

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

Source header · Attribution source

Proposition 4.31 (1): for any self-maps T₁ and T₂, the reflector of T = T₁ (2T₂ - Id) + Id - T₂ is the composition (2T₁ - Id) ∘ (2T₂ - Id).

open SubtypeFirmness -- Declarations for this item will be appended below by the statement pipeline. open EuclideanGeometry open scoped InnerProductSpace universe u variable {H : Type u} [AddCommGroup H] [Module ℝ H] theorem reflected_douglasRachfordOperator_eq_comp_reflectedMap {T₁ T₂ : H → H} : (fun x ↦ (2 : ℝ) • douglasRachfordOperator T₁ T₂ x - x) = (fun x ↦ (2 : ℝ) • T₁ x - x) ∘ fun x ↦ (2 : ℝ) • T₂ x - x

Corollary 4.32

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

Source header · Attribution source

Corollary 4.32: if V is a closed linear subspace of a real Hilbert space and T₂ is firmly nonexpansive, then the Douglas--Rachford operator attached to P_V and T₂, equivalently the map x ↦ P_V (T₂ x) + P_{Vᗮ} (x - T₂ x), is firmly nonexpansive and its fixed point set is {x | P_V x = T₂ x}.

open SubtypeFirmness -- Declarations for this item will be appended below by the statement pipeline. open EuclideanGeometry open scoped InnerProductSpace open Function universe u variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] [CompleteSpace 𝓗] theorem orthogonal_projector_residual_combination_firmlyNonexpansive_and_fixedPoints (V : ClosedSubmodule ℝ 𝓗) {T₂ : 𝓗 → 𝓗} (hT₂ : FirmlyNonexpansive T₂) : FirmlyNonexpansive (douglasRachfordOperator V.starProjection T₂) ∧ fixedPoints (douglasRachfordOperator V.starProjection T₂) = {x : 𝓗 | V.starProjection x = T₂ x}

Definition 4.33

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

Source header · Attribution source

Definition 4.33: a map T : D → H is averaged with constant α when α ∈ ]0, 1[ and there is a nonexpansive map R : D → H such that T = (1 - α) Id + α R.

universe u variable {H : Type u} [NormedAddCommGroup H] [NormedSpace ℝ H] variable {D : Set H} def AveragedWith (α : ℝ) (T : D → H) : Prop := α ∈ Set.Ioo (0 : ℝ) 1 ∧ ∃ R : D → H, LipschitzWith 1 R ∧ T = fun x : D ↦ (1 - α) • (x : H) + α • R x

Remark 4.34

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

Source header · Attribution source

Remark 4.34 (1): every averaged map on a subset of a real Hilbert space is nonexpansive.

open SubtypeFirmness -- Declarations for this item will be appended below by the statement pipeline. universe u variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] theorem lipschitzWith_one_of_averagedWith {D : Set H} {α : ℝ} {T : D → H} (hT : AveragedWith α T) : LipschitzWith 1 T

Proposition 4.35

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

Source header · Attribution source

Proposition 4.35, clause (1) ↔ (3): for α ∈ (0, 1), averagedness is equivalent to the quadratic residual inequality.

universe u variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] variable {D : Set H} theorem averagedWith_iff_residual_sqnorm_ineq {α : ℝ} (hα : α ∈ Set.Ioo (0 : ℝ) 1) {T : D → H} : AveragedWith α T ↔ ∀ x y : D, ‖T x - T y‖ ^ 2 ≤ ‖(x : H) - y‖ ^ 2 - ((1 - α) / α) * ‖((x : H) - T x) - (y - T y)‖ ^ 2

Remark 4.36

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

Source header · Attribution source

Remark 4.36: an averaged self-map on D is strictly quasinonexpansive on D.

universe u open Set variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] variable {D : Set H} {T : H → H} {α : ℝ} theorem averaged_strictlyQuasinonexpansiveOn (hT : AveragedWith α (fun x : D ↦ T x)) : StrictlyQuasinonexpansiveOn D T

Remark 4.37

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

Source header · Attribution source

Remark 4.37: if T : D → H is α-averaged for some α ∈ (0, 1 / 2], then T is firmly nonexpansive on D.

open SubtypeFirmness -- Declarations for this item will be appended below by the statement pipeline. universe u variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] variable {D : Set H} {α : ℝ} {T : D → H} theorem firmlyNonexpansiveOn_of_averagedWith_le_half (hT : AveragedWith α T) (hα : α ≤ 1 / 2) : FirmlyNonexpansiveOn D T

Proposition 4.38

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

Source header · Attribution source

Proposition 4.38: if T : D → H is ρ-Lipschitz with 0 < ρ < 1, then T is ((ρ + 1) / 2)-averaged.

universe u variable {H : Type u} [NormedAddCommGroup H] [NormedSpace ℝ H] variable {D : Set H} theorem averagedWith_of_lipschitz_lt_one {ρ : ℝ} (hρ : ρ ∈ Set.Ioo (0 : ℝ) 1) {T : D → H} (hT : LipschitzWith (Real.toNNReal ρ) T) : AveragedWith ((ρ + 1) / 2 : ℝ) T

Proposition 4.39

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

Source header · Attribution source

Proposition 4.39: on a subset D of a real inner product space, a map T : D → H is β-cocoercive if and only if the map x ↦ x - γ • T x is γ / (2 * β)-averaged whenever 0 < β and γ ∈ ]0, 2β[.

open SubtypeFirmness -- Declarations for this item will be appended below by the statement pipeline. universe u variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] theorem cocoerciveOn_iff_averagedWith_id_sub_smul {D : Set H} {β γ : ℝ} (hβ : 0 < β) (hγ : γ ∈ Set.Ioo (0 : ℝ) (2 * β)) (T : D → H) : CocoerciveOn β D T ↔ AveragedWith (γ / (2 * β)) (fun x : D ↦ (x : H) - γ • T x)

Proposition 4.40

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

Source header · Attribution source

Proposition 4.40: if α ∈ (0,1) and λ ∈ (0, 1 / α), then T is α-averaged if and only if the relaxation x ↦ (1 - λ) • x + λ • T x is (λ * α)-averaged.

universe u variable {H : Type u} [NormedAddCommGroup H] [NormedSpace ℝ H] variable {D : Set H} {α lam : ℝ} {T : D → H} theorem averagedWith_iff_averagedWith_relaxedMap (hα : α ∈ Set.Ioo (0 : ℝ) 1) (hlam : lam ∈ Set.Ioo (0 : ℝ) (1 / α)) : AveragedWith α T ↔ AveragedWith (lam * α) (fun x : D ↦ (1 - lam) • (x : H) + lam • T x)

Corollary 4.41

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

Source header · Attribution source

Corollary 4.41: on a subset D of a real Hilbert space, T is firmly nonexpansive if and only if its relaxation x ↦ (1 - λ) • x + λ • T x is (λ / 2)-averaged for λ ∈ (0, 2).

open SubtypeFirmness -- Declarations for this item will be appended below by the statement pipeline. universe u variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] theorem firmlyNonexpansiveOn_iff_relaxation_averagedWith {D : Set H} (T : D → H) {lam : ℝ} (hlam : lam ∈ Set.Ioo (0 : ℝ) 2) : FirmlyNonexpansiveOn D T ↔ AveragedWith (lam / 2) (fun x : D ↦ (1 - lam) • (x : H) + lam • T x)

Proposition 4.42

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

Source header · Attribution source

Proposition 4.42: a finite convex combination of α i-averaged operators on a subset of a real Hilbert space is (\sum i, ω i * α i)-averaged.

open scoped BigOperators universe u v variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] variable {D : Set H} {I : Type v} [Fintype I] theorem averagedWith_weightedSum (ω α : I → ℝ) (T : I → D → H) (hω : ∀ i, ω i ∈ Set.Icc (0 : ℝ) 1) (hω_sum : ∑ i, ω i = 1) (hT : ∀ i, AveragedWith (α i) (T i)) : AveragedWith (∑ i, ω i * α i) (fun x : D ↦ ∑ i, ω i • T i x)

Proposition 4.44

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

Source header · Attribution source

Proposition 4.44: the composition of two averaged self-maps is averaged, with averaging constant compositionAveragingConstant α₁ α₂.

universe u variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] variable {D : Set H} theorem averagedWith_comp {α₁ α₂ : ℝ} {T₁ T₂ : D → D} (hT₁ : AveragedWith α₁ (fun x : D ↦ (T₁ x : H))) (hT₂ : AveragedWith α₂ (fun x : D ↦ (T₂ x : H))) : AveragedWith (compositionAveragingConstant α₁ α₂) (fun x : D ↦ (T₁ (T₂ x) : H))

Proposition 4.46

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

Source header · Attribution source

Proposition 4.46: if D is nonempty, m ≥ 2, and each self-map T i : D → D is α i-averaged, then the increasing-order composition T 0 ∘ T 1 ∘ ... ∘ T (m - 1) is 1 / (1 + (∑ i, α i / (1 - α i))⁻¹)-averaged.

open scoped BigOperators universe u variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] variable {D : Set H} theorem averagedWith_compose_fin {m : ℕ} (_hm : 2 ≤ m) (_hD : D.Nonempty) (α : Fin m → ℝ) (T : Fin m → D → D) (hT : ∀ i, AveragedWith (α i) (fun x : D ↦ ((T i x : D) : H))) : AveragedWith (1 / (1 + (∑ i : Fin m, α i / (1 - α i))⁻¹) : ℝ) (fun x : D ↦ ((finiteComposition T : D → D) x : H))

Proposition 4.47

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

Source header · Attribution source

Proposition 4.47: the fixed points in D of the finite weighted average x ↦ ∑ i, ω i • T i x of quasinonexpansive maps are exactly the common fixed points of the family, provided the weights are positive, sum to 1, and the family has a common fixed point.

open scoped BigOperators universe u v variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] variable {D : Set H} {I : Type v} [Fintype I] theorem fixedPointsWithin_weightedAverage_eq_iInter (ω : I → ℝ) (T : I → D → H) (hT : ∀ i, IsQuasinonexpansiveOn (T i)) (hFix : (⋂ i, fixedPointsWithin (T i)).Nonempty) (hω_pos : ∀ i, 0 < ω i) (hω_sum : ∑ i, ω i = 1) : fixedPointsWithin (fun x : D ↦ ∑ i, ω i • T i x) = ⋂ i, fixedPointsWithin (T i)

Corollary 4.48

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

Source header · Attribution source

Corollary 4.48: the finite weighted average of firmly quasinonexpansive operators is firmly quasinonexpansive whenever the weights lie in ]0, 1] and sum to 1.

open scoped BigOperators universe u ι variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] variable {I : Type ι} [Fintype I] variable {D : Set E} theorem weightedOperatorAverage_firmly_quasinonexpansive_on (ω : I → ℝ) (T : I → D → E) (hT : ∀ i, IsFirmlyQuasinonexpansiveOn (T i)) (hω_mem : ∀ i, ω i ∈ Set.Ioc (0 : ℝ) 1) (hω_sum : ∑ i : I, ω i = 1) : IsFirmlyQuasinonexpansiveOn (weightedOperatorAverage ω T)

Proposition 4.49

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

Source header · Attribution source

Proposition 4.49 (1): if T₁ and T₂ are quasinonexpansive self-maps of D with a common fixed point, and at least one of them is strictly quasinonexpansive, then the fixed points of the composition T₁ ∘ T₂ are exactly the common fixed points of T₁ and T₂ in D.

universe u open Function Set variable {H : Type u} [NormedAddCommGroup H] variable {D : Set H} {T₁ T₂ : H → H} theorem fixedPointSetOn_comp_eq_inter_of_one_strictlyQuasinonexpansive (_hT₁_maps : MapsTo T₁ D D) (hT₂_maps : MapsTo T₂ D D) (hT₁_qne : QuasinonexpansiveOn D T₁) (hT₂_qne : QuasinonexpansiveOn D T₂) (hFix : (fixedPointSetOn D T₁ ∩ fixedPointSetOn D T₂).Nonempty) (hstrict : StrictlyQuasinonexpansiveOn D T₁ ∨ StrictlyQuasinonexpansiveOn D T₂) : fixedPointSetOn D (T₁ ∘ T₂) = fixedPointSetOn D T₁ ∩ fixedPointSetOn D T₂

Corollary 4.50

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

Source header · Attribution source

Corollary 4.50: for a nonempty finite family T 0, ..., T n of strictly quasinonexpansive self-maps of D with a common fixed point in D, the ordered composition is strictly quasinonexpansive on D, and its fixed points in D are exactly the common fixed points of the family.

open Function Set universe u variable {H : Type u} variable [NormedAddCommGroup H] theorem finiteComposition_strictlyQuasinonexpansiveOn_and_fixedPointSetOn_eq_iInter {n : ℕ} (D : Set H) (T : Fin (n + 1) → H → H) (hMaps : ∀ i, MapsTo (T i) D D) (hStrict : ∀ i, StrictlyQuasinonexpansiveOn D (T i)) (hFix : (⋂ i, fixedPointSetOn D (T i)).Nonempty) : StrictlyQuasinonexpansiveOn D (finiteComposition T) ∧ fixedPointSetOn D (finiteComposition T) = ⋂ i, fixedPointSetOn D (T i)

Corollary 4.51

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

Source header · Attribution source

Corollary 4.51: for a finite family of averaged self-maps of D with a common fixed point, the fixed points of their ordered composition are exactly the common fixed points.

universe u open Function Set variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] variable {D : Set H} theorem fixedPoints_finiteComposition_eq_iInter_fixedPoints_of_averagedWith {m : ℕ} (T : Fin m → D → D) (havg : ∀ i, ∃ α, AveragedWith α (fun x : D ↦ (T i x : H))) (hfix : Set.Nonempty (⋂ i, Function.fixedPoints (T i) : Set D)) : Function.fixedPoints (finiteComposition T) = ⋂ i, Function.fixedPoints (T i)

Supporting modules

These source modules support the indexed items and are listed separately so the chapter inventory remains complete.

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

Source header · Attribution source