Chapter 05 — Fejér Monotonicity and Fixed Point Iterations

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

Definition 5.1

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

Source header · Attribution source

Definition 5.1: a sequence x : ℕ → X is Fejer monotone with respect to C if for every c ∈ C the distances dist (x n) c do not increase from one step to the next. In a seminormed additive group this is the textbook inequality ‖x n - c‖.

universe u variable {X : Type u} [PseudoMetricSpace X] variable {C : Set X} {x : ℕ → X} def FejerMonotone (C : Set X) (x : ℕ → X) : Prop := ∀ c ∈ C, ∀ n : ℕ, dist (x (n + 1)) c ≤ dist (x n) c -- Proof sketch: unfold `FejerMonotone` and specialize the defining inequality at the chosen -- point `c ∈ C` and index `n`.

Example 5.2.1

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

Source header · Attribution source

Example 5.2.1 (1): an increasing real sequence bounded above is Fejér monotone with respect to the closed ray starting at the supremum of its range.

open Set -- Proof sketch: if `c ≥ sSup (range x)`, then -- `x n ≤ x (n + 1) ≤ sSup (range x) ≤ c`, so `x (n + 1)` lies in the interval `[x n, c]`. -- The distance to the right endpoint of a real interval decreases as one moves inside the interval. theorem fejerMonotone_Ici_sSup_range_of_monotone {x : ℕ → ℝ} (hx_mono : Monotone x) (hx_bdd : BddAbove (range x)) : FejerMonotone (Ici (sSup (range x))) x

Example 5.2.2

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

Source header · Attribution source

Example 5.2.2 (1): for an increasing real sequence bounded above, the one-step distance to any point of the closed ray starting at the supremum of its range does not increase.

open Set theorem abs_sub_le_abs_sub_of_mem_Ici_sSup_range_of_monotone {x : ℕ → ℝ} (hx_mono : Monotone x) (hx_bdd : BddAbove (range x)) {c : ℝ} (hc : c ∈ Ici (sSup (range x))) (n : ℕ) :

Example 5.3.1

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

Source header · Attribution source

Example 5.3.1 records exactly the canonical chapter theorem that the Picard iterates of a quasinonexpansive self-map are Fejér monotone with respect to its fixed-point set.

recall quasinonexpansive_iterates_fejer_monotone

Example 5.3.2

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

Source header · Attribution source

Example 5.3.2: the Picard iterates of a quasinonexpansive self-map are Fejér monotone with respect to the ambient realization of its fixed-point set.

universe u variable {H : Type u} [NormedAddCommGroup H] variable {D : Set H} -- Proof sketch: for each ambient fixed point of `T`, apply quasinonexpansiveness to the iterate -- `(T^[n]) x₀` and use `T ((T^[n]) x₀) = (T^[n.succ]) x₀` to obtain the one-step Fejér -- inequality. theorem quasinonexpansive_iterates_fejer_monotone (T : D → D) (hT : IsQuasinonexpansiveOn (fun x : D ↦ (T x : H))) (x₀ : D) : FejerMonotone (Subtype.val '' Function.fixedPoints T) (fun n ↦ (T^[n] x₀ : H))

Proposition 5.4

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

Source header · Attribution source

Proposition 5.4 (1): (i) a Fejér-monotone sequence with respect to a nonempty set is bounded.

open Filter open scoped Topology universe u variable {X : Type u} [PseudoMetricSpace X] variable {C : Set X} {u : ℕ → X} namespace FejerMonotone theorem isBounded (h : FejerMonotone C u) (hC : C.Nonempty) : Bornology.IsBounded (Set.range u)

Theorem 5.5

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

Source header · Attribution source

Theorem 5.5: if a sequence in a real Hilbert space is Fejér monotone with respect to a nonempty set C and every weak sequential cluster point of the sequence belongs to C, then the sequence converges weakly to some point of C.

open Filter open scoped Topology universe u variable {H : Type u} theorem tendsto_weakly_of_fejerMonotone_of_weakSequentialClusterPts_mem [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] {C : Set H} (hC : C.Nonempty) (x : ℕ → H) (hfejer : FejerMonotone C x) (hcluster : ∀ z : H, IsSequentialClusterPt (fun n ↦ toWeakSpace ℝ H (x n)) (toWeakSpace ℝ H z) → z ∈ C) : ∃ z ∈ C, Tendsto (fun n ↦ toWeakSpace ℝ H (x n)) atTop (𝓝 (toWeakSpace ℝ H z))

Example 5.6

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

Source header · Attribution source

Example 5.6: an orthonormal sequence is Fejér monotone with respect to {0}.

universe u variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] theorem orthonormal_sequence_fejer_monotone_with_respect_to_singleton_zero (x : ℕ → H) (hx : Orthonormal ℝ x) : FejerMonotone ({0} : Set H) x

Proposition 5.7

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

Source header · Attribution source

Proposition 5.7 (1): if C is a nonempty closed convex subset of a real Hilbert space and xₙ is Fejer monotone with respect to C, then the projection shadow n ↦ P (xₙ n) converges strongly to some z ∈ C, where P := projectionPoint C (isChebyshev_of_nonempty_isClosed_convex hC_nonempty hC_closed hC_convex).

open Filter open scoped Topology InnerProductSpace universe u variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] variable {C : Set H} 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) theorem exists_shadowLimit_of_fejerMonotone (xₙ : ℕ → H) (hxₙ : FejerMonotone C xₙ) : ∃ z ∈ C, Tendsto (fun n ↦ P (xₙ n)) atTop (𝓝 z)

Corollary 5.8

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

Source header · Attribution source

Corollary 5.8: if C is a nonempty closed convex subset of a real Hilbert space, xₙ is Fejér monotone with respect to C, x ∈ C, and xₙ converges weakly to x, then the shadow sequence of metric projections of xₙ onto C converges strongly to x.

open Filter open scoped Topology InnerProductSpace universe u variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] variable {C : Set H} 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 Proposition 5.7 to obtain some `y ∈ C` such that the projection shadow -- sequence `P_C (xₙ n)` converges strongly to `y`. Then combine the weak convergence `xₙ ⇀ x`, the -- strong convergence `P_C (xₙ n) → y`, and the projection variational inequality to show -- `‖x - y‖ ^ 2 = 0`, hence `x = y`. theorem tendsto_projectionPoint_of_fejerMonotone_of_tendsto_weakly (xₙ : ℕ → H) (hxₙ : FejerMonotone C xₙ) {x : H} (hx : x ∈ C) (hweak : Tendsto (fun n ↦ toWeakSpace ℝ H (xₙ n)) atTop (𝓝 (toWeakSpace ℝ H x))) : Tendsto (fun n ↦ P (xₙ n)) atTop (𝓝 x)

Proposition 5.9

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

Source header · Attribution source

Proposition 5.9 (1): if a sequence is Fejér monotone with respect to a closed affine subspace C, then the metric projection of every term onto C equals the projection of the initial term.

open Filter open scoped InnerProductSpace Topology universe u variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] variable {C : AffineSubspace ℝ H} variable (hC_nonempty : (C : Set H).Nonempty) (hC_closed : IsClosed (C : Set H)) local notation "P" => projectionPoint (C : Set H) (isChebyshev_of_nonempty_isClosed_convex hC_nonempty hC_closed C.convex) theorem projectionPoint_eq_initial_of_fejerMonotone_affineSubspace (x : ℕ → H) (hfejer : FejerMonotone (C : Set H) x) (n : ℕ) : P (x n) = P (x 0)

Proposition 5.10

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

Source header · Attribution source

Proposition 5.10: if C has nonempty interior and xₙ is Fejer monotone with respect to C, then xₙ converges strongly in the real Hilbert space and the norms of its successive increments form a summable series.

open Filter open scoped BigOperators Topology universe u variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] variable {C : Set H} {xₙ : ℕ → H} namespace FejerMonotone theorem exists_tendsto_and_summable_norm_sub_of_interior_nonempty (hxₙ : FejerMonotone C xₙ) (hC_int : (interior C).Nonempty) : ∃ x : H, Tendsto xₙ atTop (𝓝 x) ∧ Summable (fun n ↦ ‖xₙ (n + 1) - xₙ n‖)

Theorem 5.11

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

Source header · Attribution source

Theorem 5.11: for a Fejér-monotone sequence with respect to a nonempty closed set C in a complete pseudometric space, strong convergence to a point of C, existence of a strong sequential cluster point in C, and vanishing lower limit of the distance sequence n ↦ Metric.infDist (xₙ n) C are equivalent.

open Filter open scoped Topology universe u variable {X : Type u} [PseudoMetricSpace X] [CompleteSpace X] variable {C : Set X} {xₙ : ℕ → X} namespace FejerMonotone theorem strongConvergent_seqClusterPt_liminf_infDist_eq_zero_tfae (hxₙ : FejerMonotone C xₙ) (hC_nonempty : C.Nonempty) (hC_closed : IsClosed C) : List.TFAE [ ∃ z ∈ C, Tendsto xₙ atTop (𝓝 z), ∃ z ∈ C, IsSequentialClusterPt xₙ z, liminf (fun n ↦ (Metric.infDist (xₙ n) C : EReal)) atTop = 0 ]

Theorem 5.12

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

Source header · Attribution source

Theorem 5.12: if C is a nonempty closed subset of a complete pseudometric space, xₙ is Fejér monotone with respect to C, and the distances Metric.infDist (xₙ n) C decay geometrically with ratio κ satisfying 0 ≤ κ < 1, then xₙ converges strongly to some x ∈ C; more precisely, for every n, one has dist (xₙ n) x ≤ 2 * κ ^ n * Metric.infDist (xₙ 0) C.

open Filter open scoped Topology universe u variable {X : Type u} [PseudoMetricSpace X] [CompleteSpace X] variable {C : Set X} {xₙ : ℕ → X} {κ : ℝ} namespace FejerMonotone theorem exists_tendsto_with_dist_le_of_infDist_contracts (hxₙ : FejerMonotone C xₙ) (hC_nonempty : C.Nonempty) (hC_closed : IsClosed C) (hκ_nonneg : 0 ≤ κ) (hκ_lt_one : κ < 1) (hdist : ∀ n, Metric.infDist (xₙ (n + 1)) C ≤ κ * Metric.infDist (xₙ n) C) : ∃ x ∈ C, Tendsto xₙ atTop (𝓝 x) ∧ ∀ n, dist (xₙ n) x ≤ 2 * κ ^ n * Metric.infDist (xₙ 0) C

Proposition 5.13

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

Source header · Attribution source

Proposition 5.13 (1): (i) every relaxed step decreases the squared distance to each common fixed point by the residual term λₙ (2 - λₙ) ‖Tₙ xₙ - xₙ‖².

open Filter Function Set open scoped BigOperators Topology universe u variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] theorem sq_norm_sub_commonFixedPoint_le_of_relaxedOperatorIteration (T : ℕ → H → H) (lam : ℕ → ℝ) (x0 : H) (hT : ∀ n, FirmlyQuasinonexpansive (T n)) (z : H) (hz : z ∈ ⋂ n, fixedPoints (T n)) (n : ℕ) (hlam : 0 ≤ lam n) : ‖relaxedOperatorIteration T lam x0 (n + 1) - z‖ ^ 2 ≤ ‖relaxedOperatorIteration T lam x0 n - z‖ ^ 2 - lam n * (2 - lam n) * ‖T n (relaxedOperatorIteration T lam x0 n) - relaxedOperatorIteration T lam x0 n‖ ^ 2

Theorem 5.14

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

Source header · Attribution source

Theorem 5.14 (1): (i) if a nonexpansive self-map of a nonempty closed convex subset has a nonempty fixed-point set and its Picard residuals converge strongly to 0, then its Picard iterates converge weakly to a fixed point.

open Filter open scoped Topology universe u variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] variable {D : Set H} theorem tendsto_weakly_iterates_to_fixedPoint_of_residual_tendsto_zero_of_nonexpansive (hD_closed : IsClosed D) (hD_convex : Convex ℝ D) {T : D → D} (hT : LipschitzWith 1 T) (hFix : (Function.fixedPoints T).Nonempty) (x₀ : D) (hres : Tendsto (fun n ↦ ((T^[n]) x₀ : H) - (T ((T^[n]) x₀) : H)) atTop (𝓝 (0 : H))) : ∃ z ∈ Function.fixedPoints T, Tendsto (fun n ↦ toWeakSpace ℝ H ((T^[n]) x₀ : H)) atTop (𝓝 (toWeakSpace ℝ H (z : H)))

Theorem 5.15

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

Source header · Attribution source

Theorem 5.15 (1): the Krasnosel'skii-Mann iteration is Fejér monotone with respect to the ambient realization of its fixed-point set.

open Filter Function open scoped BigOperators Topology universe u variable {H : Type u} [NormedAddCommGroup H] [NormedSpace ℝ H] variable {D : Set H} -- Proof sketch: for each fixed point `y` of `T`, expand the squared norm of -- `(1 - λ n) • (xₙ - y) + λ n • (T xₙ - y)` in the subtype metric and use nonexpansiveness of `T` -- together with `T y = y` to obtain the one-step Fejér inequality. theorem krasnoselskiiMannIteration_fejerMonotone (hD_convex : Convex ℝ D) (T : D → D) (hT : LipschitzWith 1 T) (relax : ℕ → ℝ) (hrelax : ∀ n, relax n ∈ Set.Icc (0 : ℝ) 1) (x₀ : D) : FejerMonotone (Subtype.val '' fixedPoints T) (fun n ↦ (krasnoselskiiMannIteration hD_convex T relax hrelax x₀ n : H))

Proposition 5.16

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

Source header · Attribution source

Proposition 5.16 (1): (i) for an α-averaged operator on a real Hilbert space, the relaxed iteration xₙ₊₁ = xₙ + λₙ • (T xₙ - xₙ) is Fejér monotone with respect to Fix T.

open Filter Function open scoped BigOperators InnerProductSpace Topology universe u variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] variable {α : ℝ} {T : H → H} variable (hT : AveragedWith α (fun x : (Set.univ : Set H) ↦ T x)) variable (lam : ℕ → ℝ) (hlam : ∀ n, lam n ∈ Set.Icc (0 : ℝ) (1 / α)) include hT hlam theorem fejerMonotone_fixedPoints_of_relaxedOperatorIteration_of_averagedWith (x₀ : H) : FejerMonotone (fixedPoints T) (relaxedOperatorIteration (fun _ ↦ T) lam x₀)

Corollary 5.17

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

Source header · Attribution source

Corollary 5.17 (1): for a firmly nonexpansive self-map, the relaxed iteration generated by relaxation parameters in [0, 2] is Fejér monotone with respect to the fixed-point set of T.

open Filter Function open scoped BigOperators InnerProductSpace Topology universe u open Corollary517KM variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] -- Proof sketch: replace the relaxed iteration for `T` by the Krasnosel'skii-Mann iteration of -- the reflector `R = 2T - Id` with parameters `λₙ / 2`, then use that `Fix R = Fix T`. theorem fejerMonotone_fixedPoints_of_relaxedOperatorIteration_of_firmlyNonexpansive {T : H → H} (hT : FirmlyNonexpansive T) (relax : ℕ → ℝ) (hrelax : ∀ n, relax n ∈ Set.Icc (0 : ℝ) 2) (x0 : H) : FejerMonotone (fixedPoints T) (relaxedOperatorIteration (fun _ ↦ T) relax x0)

Example 5.18

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

Source header · Attribution source

Example 5.18: if T : H → H is firmly nonexpansive on a real Hilbert space and Fix T is nonempty, then the Picard iterates n ↦ (T^[n]) x₀ converge weakly to a fixed point of T.

open SubtypeFirmness -- Declarations for this item will be appended below by the statement pipeline. open Filter Function open scoped Topology universe u variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] variable [CompleteSpace H] -- Proof sketch: this is Corollary 5.17(3) specialized to the constant relaxation sequence -- `λₙ = 1`, for which the relaxed iteration is exactly the Picard orbit. theorem tendsto_weakly_iterates_to_fixedPoint_of_firmlyNonexpansive {T : H → H} (hT : FirmlyNonexpansive T) (hFix : (fixedPoints T).Nonempty) (x₀ : H) : ∃ z ∈ fixedPoints T, Tendsto (fun n ↦ toWeakSpace ℝ H ((T^[n]) x₀)) atTop (𝓝 (toWeakSpace ℝ H z))

Corollary 5.19

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

Source header · Attribution source

Corollary 5.19: for a finite weighted family of finite ordered compositions of averaged nonexpansive self-maps on a real Hilbert space, if the block index map covers the whole family and ∑ λₙ (1 - α λₙ) = +∞ with α = ∑ k, ω k * (1 / (1 + (∑ l, avg (i k l) / (1 - avg (i k l)))⁻¹)), then the relaxed orbit of the corresponding weighted block operator, written canonically via weightedOperatorAverage, converges weakly to a common fixed point of the original family.

open Filter Function open scoped BigOperators Topology universe u v variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] variable {I : Type v} local notation "H_univ" => (Set.univ : Set H) theorem exists_tendsto_weakly_to_common_fixedPoint_of_krasnoselskiiMann_weightedBlockComposition {p : ℕ+} (m : Fin p → ℕ+) (i : (k : Fin p) → Fin (m k) → I) (T : I → H → H) (avg : I → ℝ) (ω : Fin p → ℝ) (hT : ∀ j, AveragedWith (avg j) (fun x : (Set.univ : Set H) ↦ T j x)) (hFix : (⋂ j, fixedPoints (T j)).Nonempty) (hω : ∀ k, ω k ∈ Set.Ioc (0 : ℝ) 1) (hω_sum : ∑ k : Fin p, ω k = 1) (hcover : Surjective (fun q : Σ k : Fin p, Fin (m k) ↦ i q.1 q.2)) (lam : ℕ → ℝ) (hlam : ∀ n, lam n ∈ Set.Icc (0 : ℝ) (1 / ∑ k : Fin p, ω k * (1 / (1 + (∑ l : Fin (m k), avg (i k l) / (1 - avg (i k l)))⁻¹)))) (hdiv : Tendsto (fun N ↦ ∑ n ∈ Finset.range N, lam n * (1 - (∑ k : Fin p, ω k * (1 / (1 + (∑ l : Fin (m k), avg (i k l) / (1 - avg (i k l)))⁻¹))) * lam n)) atTop atTop) (x₀ : H) : let S : H → H := fun x ↦ weightedOperatorAverage ω (fun k : Fin p ↦ fun y : (Set.univ : Set H) ↦ finiteComposition (fun l : Fin (m k) ↦ T (i k l)) y) ⟨x, by simp⟩ ∃ z ∈ ⋂ j, fixedPoints (T j), Tendsto (fun n ↦ toWeakSpace ℝ H (relaxedOperatorIteration (fun _ ↦ S) lam x₀ n)) atTop (𝓝 (toWeakSpace ℝ H z))

Example 5.21

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

Source header · Attribution source

Example 5.21: for a finite family of closed convex sets with nonempty intersection, the orbit generated by weighted string averages of the relaxed projectors Tᵢ = (1 - βᵢ) Id + βᵢ P_{Cᵢ} converges weakly to a point of the common intersection.

open Filter open scoped BigOperators Topology universe u v variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] variable {I : Type v} local notation "H_univ" => (Set.univ : Set H) -- Proof sketch: a point in the common intersection belongs to every component set, so it gives a -- witness of nonemptiness for each `C j`. theorem exists_tendsto_weakly_to_point_in_iInter_of_stringAveragedRelaxedProjectionOrbit {p : ℕ+} (m : Fin p → ℕ+) (i : (k : Fin p) → Fin (m k) → I) (C : I → Set H) (hC_closed : ∀ j, IsClosed (C j)) (hC_convex : ∀ j, Convex ℝ (C j)) (hC_inter_nonempty : (⋂ j, C j).Nonempty) (β : I → ℝ) (hβ : ∀ j, β j ∈ Set.Ioo (0 : ℝ) 2) (ω : Fin p → ℝ) (hω : ∀ k, ω k ∈ Set.Ioc (0 : ℝ) 1) (hω_sum : ∑ k : Fin p, ω k = 1) (hcover : Function.Surjective (fun q : Σ k : Fin p, Fin (m k) ↦ i q.1 q.2)) (x₀ : H) : ∃ z ∈ ⋂ j, C j, Tendsto (fun n ↦ toWeakSpace ℝ H (stringAveragedRelaxedProjectionOrbit ω m i C hC_closed hC_convex hC_inter_nonempty β x₀ n)) atTop (𝓝 (toWeakSpace ℝ H z))

Example 5.22.1

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

Source header · Attribution source

Example 5.22.1: for a finite family of closed convex sets with nonempty common intersection, the Krasnosel'skii-Mann iteration of the weighted average of the metric projectors converges weakly to a point in the common intersection whenever the weights are strictly positive, sum to 1, and the relaxation parameters satisfy ∑ λₙ (2 - λₙ) = +∞.

open Corollary517KM -- Declarations for this item will be appended below by the statement pipeline. open Filter open scoped BigOperators InnerProductSpace Topology universe u v variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] variable {I : Type v} local notation "H_univ" => (Set.univ : Set H) omit [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] in -- Proof sketch: choose a point in the common intersection `⋂ i, C i`; its `i`-th coordinate -- membership shows that `C i` is nonempty. variable [Fintype I] theorem parallelProjectionOrbit_tendsto_weakly_to_point_of_iInter (C : I → Set H) (hC : (⋂ i, C i).Nonempty) (hC_closed : ∀ i, IsClosed (C i)) (hC_convex : ∀ i, Convex ℝ (C i)) (ω : I → ℝ) (hω_pos : ∀ i, 0 < ω i) (hω_sum : ∑ i, ω i = 1) (relax : ℕ → ℝ) (hrelax : ∀ n, relax n ∈ Set.Icc (0 : ℝ) 2) (hdiv : Tendsto (fun N ↦ ∑ n ∈ Finset.range N, relax n * (2 - relax n)) atTop atTop) (x0 : H) : ∃ z ∈ ⋂ i, C i, Tendsto (fun n ↦ toWeakSpace ℝ H (relaxedOperatorIteration (fun _ ↦ parallelProjectionOperator C hC hC_closed hC_convex ω) relax x0 n)) atTop (𝓝 (toWeakSpace ℝ H z))

Theorem 5.23

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

Source header · Attribution source

Theorem 5.23: for a finite family T 0, ..., T n of averaged self-maps of a nonempty closed convex subset of a real Hilbert space, if the ordered composition has a fixed point, then the Picard residuals converge strongly to 0, and the Picard orbit admits cyclic weak limits whose shadow convergences, cyclic relations, and cyclic fixed-point identities encode (5.24)--(5.28).

open Filter Function open scoped Topology universe u variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] variable {D : Set H} theorem residual_tendsto_zero_and_exists_cyclicWeakLimits_of_averaged_finiteComposition (hD_closed : IsClosed D) (hD_convex : Convex ℝ D) {n : ℕ} (T : Fin (n + 1) → D → D) (hAveraged : ∀ i, ∃ α : ℝ, AveragedWith α (fun x : D ↦ (T i x : H))) (hFix : (fixedPoints (finiteComposition T)).Nonempty) (x₀ : D) : Tendsto (fun k ↦ (((finiteComposition T : D → D)^[k]) x₀ : H) - ((((finiteComposition T : D → D)^[k.succ]) x₀) : H)) atTop (𝓝 (0 : H)) ∧ ∃ y : Fin (n + 1) → D, (∀ i : Fin (n + 1), Tendsto (fun k ↦ toWeakSpace ℝ H ((cyclicShadow T i) (((finiteComposition T)^[k]) x₀) : H)) atTop (𝓝 (toWeakSpace ℝ H (y i : H)))) ∧ (∀ i : Fin (n + 1), y i = T i (y (cyclicNext i))) ∧ ∀ i : Fin (n + 1), y i ∈ fixedPoints (cyclicComposition T i)

Corollary 5.24

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

Source header · Attribution source

Corollary 5.24: if a finite cyclic family of nonempty closed convex sets in a real Hilbert space has a composite projector with a fixed point, then the POCS orbit starting from x₀ admits points y₁, …, y_m in the respective sets that form a cyclic projector relation and are the weak limits of the orbit and its tail-shadow sequences.

open Filter Function open scoped InnerProductSpace Topology universe u variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] local notation "H_univ" => (Set.univ : Set H) theorem exists_pocs_limitCycle_of_fixedPoint_pocsOperator {m : ℕ} (C : Fin (m + 1) → Set H) (hC_nonempty : ∀ i, (C i).Nonempty) (hC_closed : ∀ i, IsClosed (C i)) (hC_convex : ∀ i, Convex ℝ (C i)) (x₀ : H) (hfix : (Function.fixedPoints (pocsOperator C hC_nonempty hC_closed hC_convex)).Nonempty) : ∃ y, IsPocsLimitCycle C hC_nonempty hC_closed hC_convex x₀ y

Corollary 5.26

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

Source header · Attribution source

Corollary 5.26: if a finite family of closed convex sets in a real Hilbert space has nonempty intersection, then the Picard iterates of the ordered composition of their metric projectors converge weakly to a point in the common intersection.

open Filter Function open scoped Topology universe u variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] local notation "H_univ" => (Set.univ : Set H) theorem exists_tendsto_weakly_to_point_in_iInter_of_cyclicProjection {m : ℕ} (C : Fin (m + 1) → Set H) (hC_closed : ∀ i, IsClosed (C i)) (hC_convex : ∀ i, Convex ℝ (C i)) (hC_inter_nonempty : (⋂ i, C i).Nonempty) (x₀ : H) : ∃ z ∈ ⋂ i, C i, Tendsto (fun n ↦ toWeakSpace ℝ H (((finiteComposition fun i ↦ projectionPoint (C i) (isChebyshev_of_nonempty_isClosed_convex (nonempty_component_of_nonempty_iInter hC_inter_nonempty i) (hC_closed i) (hC_convex i)))^[n]) x₀)) atTop (𝓝 (toWeakSpace ℝ H z))

Proposition 5.28

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

Source header · Attribution source

Proposition 5.28: if T is a nonexpansive bounded linear operator on a real Hilbert space, then the Picard iterates converge strongly to the orthogonal projection of x₀ onto the fixed- point subspace fixedSubspace T = Fix T if and only if the successive differences converge strongly to 0.

open EuclideanGeometry open Filter Function open scoped Topology universe u variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] local notation "H_univ" => (Set.univ : Set H) theorem tendsto_iterates_to_starProjection_fixedSubspace_iff_tendsto_residual_zero_of_nonexpansive {T : H →L[ℝ] H} (hT : LipschitzWith 1 T) (x₀ : H) : Tendsto (fun n ↦ (T^[n]) x₀) atTop (𝓝 ((fixedSubspace T).starProjection x₀)) ↔ Tendsto (fun n ↦ (T^[n]) x₀ - (T^[n + 1]) x₀) atTop (𝓝 (0 : H))

Example 5.29

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

Source header · Attribution source

Example 5.29: if a bounded linear operator on a real Hilbert space is averaged, then its Picard iterates starting at x₀ converge strongly to the projection of x₀ onto V = Fix T.

open Filter Function open scoped Topology universe u variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] theorem tendsto_iterates_to_starProjection_fixedSubspace_of_averaged {T : H →L[ℝ] H} (havg : ∃ α : ℝ, AveragedWith α (fun x : (Set.univ : Set H) ↦ (T (x : H) : H))) (x₀ : H) : Tendsto (fun n ↦ (T^[n]) x₀) atTop (𝓝 ((fixedSubspace T).starProjection x₀))

Corollary 5.30

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

Source header · Attribution source

Corollary 5.30: (von Neumann--Halperin) for a finite family of closed affine subspaces of a real Hilbert space with nonempty intersection, the cyclic projection orbit converges strongly to the metric projection of the initial point onto the intersection.

open Filter open EuclideanGeometry open scoped InnerProductSpace Topology universe u variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] local notation "H_univ" => (Set.univ : Set H) theorem tendsto_affinePocsOrbit_to_affineProjector_iInf {m : ℕ} (A : Fin (m + 1) → AffineSubspace ℝ H) (hA_closed : ∀ i, IsClosed (A i : Set H)) (hFix : (((⨅ i, A i : AffineSubspace ℝ H) : AffineSubspace ℝ H) : Set H).Nonempty) (x₀ : H) : Tendsto (affinePocsOrbit A hA_closed hFix x₀) atTop (𝓝 (affineProjector (⨅ i, A i) hFix (isClosed_iInf_affineSubspace A hA_closed) x₀))

Lemma 5.31

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

Source header · Attribution source

Lemma 5.31: if nonnegative sequences α and β satisfy the perturbed descent recursion α (n + 1) + β n ≤ (1 + γ n) * α n + ε n and the perturbation sequences γ and ε are summable, then α converges in ℝ≥0 and β is summable.

open Filter open scoped BigOperators Topology NNReal theorem tendsto_and_summable_of_summable_perturbed_descent {α β γ ε : ℕ → ℝ≥0} (hγ : Summable γ) (hε : Summable ε) (hrec : ∀ n : ℕ, α (n + 1) + β n ≤ (1 + γ n) * α n + ε n) : (∃ l : ℝ≥0, Tendsto α atTop (𝓝 l)) ∧ Summable β

Definition 5.32

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

Source header · Attribution source

Definition 5.32: a sequence x : ℕ → H is quasi-Fejér monotone with respect to C if for every c ∈ C there is a summable nonnegative error sequence controlling the one-step growth of the squared distances ‖x n - c‖ ^ 2.

universe u variable {H : Type u} [NormedAddCommGroup H] variable {C : Set H} {x : ℕ → H} def QuasiFejerMonotone (C : Set H) (x : ℕ → H) : Prop := ∀ c ∈ C, ∃ ε : ℕ → NNReal, Summable ε ∧ ∀ n : ℕ, ‖x (n + 1) - c‖ ^ 2 ≤ ‖x n - c‖ ^ 2 + ε n -- Proof sketch: unfold `QuasiFejerMonotone` and specialize the defining quantifiers at the chosen -- point `c ∈ C`.

Theorem 5.33

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

Source header · Attribution source

Theorem 5.33 (1): clause (i). For every z ∈ C, the distance sequence n ↦ ‖x n - z‖ converges.

open Filter open scoped Topology BigOperators universe u variable {H : Type u} [SeminormedAddCommGroup H] variable {C : Set H} {x : ℕ → H} theorem quasiFejerMonotone_norm_tendsto {z : H} (hquasi : UniformQuasiFejerMonotone C x) (hz : z ∈ C) : ∃ l : ℝ, Tendsto (fun n ↦ ‖x n - z‖) atTop (𝓝 l)

Proposition 5.34

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

Source header · Attribution source

Proposition 5.34 (1): (i) if T is nonexpansive, λₙ ∈ [0,1], and ∑ λₙ ‖eₙ‖ < +∞, then the inexact Krasnosel'skii-Mann orbit is quasi-Fejér monotone with respect to Function.fixedPoints T.

open Filter open scoped BigOperators Topology NNReal universe u variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] theorem inexactKrasnoselskiiMannOrbit_quasiFejerMonotone {T : H → H} (hT : LipschitzWith 1 T) (relax : ℕ → ℝ) (hrelax : ∀ n, relax n ∈ Set.Icc (0 : ℝ) 1) (e : ℕ → H) (hsummable : Summable (fun n ↦ relax n * ‖e n‖)) (x0 : H) : QuasiFejerMonotone (Function.fixedPoints T) (inexactKrasnoselskiiMannOrbit T relax e x0)

Theorem 5.36

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

Source header · Attribution source

Theorem 5.36: if yₙ is quasi-Fejér monotone with respect to a nonempty set C, the distances from xₙ to the tail closed convex hulls tailClosedConvexHull yₙ m = overline (conv {yₖ | m ≤ k}) tend to 0 for every m, and every weak sequential cluster point of xₙ lies in C, then xₙ converges weakly to a point of C.

open Filter open scoped Topology universe u variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] theorem tendsto_weakly_of_quasiFejerMonotone_of_tailClosedConvexHull_infDist_tendsto_zero {C : Set H} (hC : C.Nonempty) (xₙ yₙ : ℕ → H) (hyₙ : ∀ c ∈ C, ∃ ε : ℕ → NNReal, Summable ε ∧ ∀ n : ℕ, ‖yₙ (n + 1) - c‖ ^ 2 ≤ ‖yₙ n - c‖ ^ 2 + ε n) (hdist : ∀ m : ℕ, Tendsto (fun n ↦ Metric.infDist (xₙ n) (tailClosedConvexHull yₙ m)) atTop (𝓝 0)) (hcluster : ∀ z : H, IsSequentialClusterPt (fun n ↦ toWeakSpace ℝ H (xₙ n)) (toWeakSpace ℝ H z) → z ∈ C) : ∃ z ∈ C, Tendsto (fun n ↦ toWeakSpace ℝ H (xₙ n)) atTop (𝓝 (toWeakSpace ℝ H z))

Corollary 5.37

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

Source header · Attribution source

Corollary 5.37: if y is quasi-Fejér monotone with respect to a nonempty set C, if α n k ≥ 0 for k ≤ n, ∑_{k=0}^n α n k = 1, and each fixed coefficient column tends to 0, then the weighted averages ∑_{k=0}^n α n k • y k converge weakly to a point of C provided all of their weak sequential cluster points lie in C.

open Filter open scoped BigOperators Topology universe u variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] variable {C : Set H} {y : ℕ → H} {α : ℕ → ℕ → ℝ} theorem tendsto_weakly_of_weighted_averages_of_quasiFejerMonotone_of_weakSequentialClusterPts_mem (hC : C.Nonempty) (hy : QuasiFejerMonotone C y) (hα_nonneg : ∀ n k, k ≤ n → 0 ≤ α n k) (hα_sum : ∀ n, Finset.sum (Finset.range (n + 1)) (fun k ↦ α n k) = 1) (hα_tendsto : ∀ k, Tendsto (fun n ↦ α n k) atTop (𝓝 0)) (hcluster : ∀ z : H, IsSequentialClusterPt (fun n ↦ toWeakSpace ℝ H (Finset.sum (Finset.range (n + 1)) (fun k ↦ α n k • y k))) (toWeakSpace ℝ H z) → z ∈ C) : ∃ z ∈ C, Tendsto (fun n ↦ toWeakSpace ℝ H (Finset.sum (Finset.range (n + 1)) (fun k ↦ α n k • y k))) atTop (𝓝 (toWeakSpace ℝ H z))

Example 5.38

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

Source header · Attribution source

Example 5.38 (Baillon): if D is a closed convex subset of a real Hilbert space, T : D → D is nonexpansive, and Fix T is nonempty, then the Cesaro averages of the Picard iterates of x₀ converge weakly to a fixed point of T.

open Filter open scoped BigOperators Topology universe u variable {X : Type*} [AddCommGroup X] variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] variable {D : Set H} theorem tendsto_weakly_cesaroIterates_to_fixedPoint_of_nonexpansive (hD_closed : IsClosed D) (hD_convex : Convex ℝ D) {T : D → D} (hT : LipschitzWith 1 T) (hFix : (Function.fixedPoints T).Nonempty) (x₀ : D) : ∃ z ∈ Function.fixedPoints T, Tendsto (fun n ↦ toWeakSpace ℝ H (cesaroIterates T x₀ n)) atTop (𝓝 (toWeakSpace ℝ H (z : H)))