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.
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 TProposition 4.2
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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 ].TFAEProposition 4.3
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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)‖ ^ 2Proposition 4.4
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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.
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)‖ ^ 2Proposition 4.8
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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.
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.
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.
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.
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.
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.
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 / β)) TRemark 4.15.2
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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_operatorProposition 4.16
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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.
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.
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.
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.
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.
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 PProposition 4.22
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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.
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.
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.
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 = uTheorem 4.27
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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 = uCorollary 4.28
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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).NonemptyProposition 4.30
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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 - xCorollary 4.32
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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 xRemark 4.34
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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 TProposition 4.35
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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)‖ ^ 2Remark 4.36
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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 TRemark 4.37
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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 TProposition 4.38
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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 : ℝ) TProposition 4.39
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
-
FirmlyNonexpansiveOn.lean(Documentation) (Lean source)
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.