v21 Corollary 2: quantitative eigenvalue bounds

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

public sectionnoncomputable sectionopen Filter DFP.Polaropen scoped MatrixOrder Topology InnerProductnamespace DFPWolfe.V21.IdentityQuantitative

Helper for cor:identity-initialization: every canonical decreasing-order eigenvalue of a positive-definite real planar matrix is strictly positive.

theorem orderedEigenvalue_pos {A : Matrix (Fin 2) (Fin 2) ℝ} (hA : A.PosDef) (i : Fin (Fintype.card (Fin 2))) : 0 < hA.isHermitian.eigenvalues₀ i := by let e : Fin (Fintype.card (Fin 2)) ≃ Fin 2 := Fintype.equivOfCardEq (Fintype.card_fin (Fintype.card (Fin 2))) have hp := hA.eigenvalues_pos (e i) simpa only [Matrix.IsHermitian.eigenvalues, e, Equiv.symm_apply_apply] using hp

Helper for cor:identity-initialization: the canonical smallest and largest Hermitian eigenvalues are exact scalar Loewner bounds for the original matrix.

theorem orderedEigenvalue_bounds {A : Matrix (Fin 2) (Fin 2) ℝ} (hA : A.IsHermitian) : hA.eigenvalues₀ 1 • (1 : Matrix (Fin 2) (Fin 2) ℝ) ≤ A ∧ A ≤ hA.eigenvalues₀ 0 • (1 : Matrix (Fin 2) (Fin 2) ℝ) := by have hlower : algebraMap ℝ (Matrix (Fin 2) (Fin 2) ℝ) (hA.eigenvalues₀ 1) ≤ A := by apply algebraMap_le_of_le_spectrum _ hA.isSelfAdjoint intro x hx rw [hA.spectrum_real_eq_range_eigenvalues] at hx obtain ⟨i, rfl⟩ := hx rw [Matrix.IsHermitian.eigenvalues] exact hA.eigenvalues₀_antitone (Fin.le_last _) have hupper : A ≤ algebraMap ℝ (Matrix (Fin 2) (Fin 2) ℝ) (hA.eigenvalues₀ 0) := by apply le_algebraMap_of_spectrum_le _ hA.isSelfAdjoint intro x hx rw [hA.spectrum_real_eq_range_eigenvalues] at hx obtain ⟨i, rfl⟩ := hx rw [Matrix.IsHermitian.eigenvalues] exact hA.eigenvalues₀_antitone (Fin.zero_le _) simpa only [Algebra.algebraMap_eq_smul_one] using And.intro hlower hupper

Helper for cor:identity-initialization: Euclidean realization preserves the Loewner order of real matrices.

theorem matrixOperator_mono {n : ℕ} {A B : Matrix (Fin n) (Fin n) ℝ} (h : A ≤ B) : Matrix.toEuclideanCLM (𝕜 := ℝ) A ≤ Matrix.toEuclideanCLM (𝕜 := ℝ) B := by rw [ContinuousLinearMap.le_def, ← map_sub] exact Matrix.isPositive_toEuclideanCLM_iff.mpr (Matrix.le_iff.mp h)

Helper for cor:identity-initialization: both and Unknown identifier `PP`ContinuousLinearMap.adjoint sorry : ?m.3 →L[?m.1] ?m.2PP† of the literal positive square root have the exact original canonical eigenvalue bounds.

theorem positiveRoot_spectral_bounds {A : Matrix (Fin 2) (Fin 2) ℝ} (hA : A.PosDef) : let P := hA.sqrtEquiv.toContinuousLinearMap let lo := hA.isHermitian.eigenvalues₀ 1 let hi := hA.isHermitian.eigenvalues₀ 0 (lo • 1 ≤ P.pullback 1 ∧ P.pullback 1 ≤ hi • 1) ∧ (lo • 1 ≤ P.pushforward 1 ∧ P.pushforward 1 ≤ hi • 1) := by dsimp only have hmatrix := orderedEigenvalue_bounds hA.isHermitian have hlower := matrixOperator_mono hmatrix.1 have hupper := matrixOperator_mono hmatrix.2 simp only [map_smul, map_one] at hlower hupper have hpull : hA.sqrtEquiv.toContinuousLinearMap.pullback 1 = Matrix.toEuclideanCLM (𝕜 := ℝ) A := by rw [ContinuousLinearMap.pullback_one_eq_pushforward_one _ hA.sqrtEquiv_isSelfAdjoint, ← hA.sqrtEquiv_pushforward_one] rw [hpull, ← hA.sqrtEquiv_pushforward_one] exact ⟨⟨hlower, hupper⟩, ⟨hlower, hupper⟩⟩

Helper for cor:identity-initialization: a precise adjoint lower singular value bound passes the FULL source gradient limit to the transformed liminf.

theorem pulledGradient_liminf_ge {n : ℕ} {c₁ c₂ q : ℝ} (c : DFP.StrongWolfeCounterexample (Fin n) (1 / 2) (3 / 2) c₁ c₂) (P : EuclideanSpace ℝ (Fin n) ≃L[ℝ] EuclideanSpace ℝ (Fin n)) (hq : 0 ≤ q) (hlower : q • (1 : EuclideanSpace ℝ (Fin n) →L[ℝ] EuclideanSpace ℝ (Fin n)) ≤ P.toContinuousLinearMap.pushforward 1) : Real.sqrt q * c.gradientLimit ≤ liminf (fun k ↦ ‖IdentityInitialization.pulledGradients c.iteration P k‖) atTop := by have hlimit := c.gradientNormTendsto.const_mul (Real.sqrt q) have hpointwise : ∀ᶠ k in atTop, Real.sqrt q * ‖DFP.gradients c.iteration.objective c.iteration.point k‖ ≤ ‖IdentityInitialization.pulledGradients c.iteration P k‖ := by filter_upwards [] with k rw [IdentityInitialization.pulledGradients_apply] exact P.toContinuousLinearMap.norm_adjoint_lower_bound hq hlower _ obtain ⟨B, hB⟩ := c.gradientNormTendsto.isBoundedUnder_le have hupper : ∀ᶠ k in atTop, ‖IdentityInitialization.pulledGradients c.iteration P k‖ ≤ ‖P.toContinuousLinearMap.adjoint‖ * B := by filter_upwards [hB] with k hk rw [IdentityInitialization.pulledGradients_apply] exact (P.toContinuousLinearMap.adjoint.le_opNorm _).trans (mul_le_mul_of_nonneg_left hk (norm_nonneg _)) have hmono := liminf_le_liminf hpointwise hlimit.isBoundedUnder_ge (isCoboundedUnder_ge_of_eventually_le atTop hupper) rwa [hlimit.liminf_eq] at hmono

Helper for cor:identity-initialization: the source initial minimum is the canonical Hermitian eigenvalue at decreasing-order index one.

def initialMinEigenvalue {c₁ c₂ : ℝ} (c : DFP.StrongWolfeCounterexample (Fin 2) (1 / 2) (3 / 2) c₁ c₂) : ℝ := (c.iteration.inverseHessianPosDef 0).isHermitian.eigenvalues₀ 1

Helper for cor:identity-initialization: the source initial maximum is the canonical Hermitian eigenvalue at decreasing-order index zero.

def initialMaxEigenvalue {c₁ c₂ : ℝ} (c : DFP.StrongWolfeCounterexample (Fin 2) (1 / 2) (3 / 2) c₁ c₂) : ℝ := (c.iteration.inverseHessianPosDef 0).isHermitian.eigenvalues₀ 0

Helper for cor:identity-initialization: the initial minimum uses the original initial inverse matrix and canonical source eigenvalue.

theorem initialMinEigenvalue_def {c₁ c₂ : ℝ} (c : DFP.StrongWolfeCounterexample (Fin 2) (1 / 2) (3 / 2) c₁ c₂) : initialMinEigenvalue c = (c.iteration.inverseHessianPosDef 0).isHermitian.eigenvalues₀ 1 := by rfl

Helper for cor:identity-initialization: the initial maximum uses the original initial inverse matrix and canonical source eigenvalue.

theorem initialMaxEigenvalue_def {c₁ c₂ : ℝ} (c : DFP.StrongWolfeCounterexample (Fin 2) (1 / 2) (3 / 2) c₁ c₂) : initialMaxEigenvalue c = (c.iteration.inverseHessianPosDef 0).isHermitian.eigenvalues₀ 0 := by rfl

Helper for cor:identity-initialization: both extremal eigenvalues of the actual positive-definite initial inverse matrix are positive.

theorem initialEigenvalues_pos {c₁ c₂ : ℝ} (c : DFP.StrongWolfeCounterexample (Fin 2) (1 / 2) (3 / 2) c₁ c₂) : 0 < initialMinEigenvalue c ∧ 0 < initialMaxEigenvalue c := by exact ⟨orderedEigenvalue_pos (c.iteration.inverseHessianPosDef 0) 1, orderedEigenvalue_pos (c.iteration.inverseHessianPosDef 0) 0⟩

Helper for cor:identity-initialization: the Hessian of the SAME literal pullback is exactly .

theorem pullback_hessian_eq {c₁ c₂ : ℝ} (c : DFP.StrongWolfeCounterexample (Fin 2) (1 / 2) (3 / 2) c₁ c₂) {target : DFP.InverseIteration (Fin 2)} {P : EuclideanSpace ℝ (Fin 2) ≃L[ℝ] EuclideanSpace ℝ (Fin 2)} (hdata : IdentityInitialization.PullbackData c.iteration target P) (z : EuclideanSpace ℝ (Fin 2)) : hessian target.objective z = P.toContinuousLinearMap.pullback (hessian c.iteration.objective (P z)) := by rw [hdata.objective, IdentityInitialization.pulledObjective_def] exact P.comp_right_hessian _ z ((c.objectiveContDiff.gradient_succ (n := 1)).differentiable_one (P z))

Helper for cor:identity-initialization: the actual positive-root pullback has the LITERAL displayed planar Hessian bounds, without changing its objective.

theorem pullback_hessian_bounds {c₁ c₂ : ℝ} (c : DFP.StrongWolfeCounterexample (Fin 2) (1 / 2) (3 / 2) c₁ c₂) {target : DFP.InverseIteration (Fin 2)} {P : EuclideanSpace ℝ (Fin 2) ≃L[ℝ] EuclideanSpace ℝ (Fin 2)} (hP : P = (c.iteration.inverseHessianPosDef 0).sqrtEquiv) (hdata : IdentityInitialization.PullbackData c.iteration target P) : HasHessianBounds (initialMinEigenvalue c / 2) (3 * initialMaxEigenvalue c / 2) target.objective := by have hroot := positiveRoot_spectral_bounds (c.iteration.inverseHessianPosDef 0) rw [← hP] at hroot have hdiff : Differentiable ℝ (gradient c.iteration.objective) := (c.objectiveContDiff.gradient_succ (n := 1)).differentiable_one have hhalf : (0 : ℝ) ≤ 1 / 2 := by norm_num have hthree : (0 : ℝ) ≤ 3 / 2 := by norm_num rw [hdata.objective, IdentityInitialization.pulledObjective_def] have h : HasHessianBounds ((1 / 2 : ℝ) * initialMinEigenvalue c) ((3 / 2 : ℝ) * initialMaxEigenvalue c) (c.iteration.objective ∘ P) := c.hessianBounds.comp_continuousLinearEquiv P hdiff hhalf hthree hroot.1.1 hroot.1.2 simpa only [div_mul_eq_mul_div, one_mul] using h

Helper for cor:identity-initialization: the exact source gradient limit one gives on that SAME canonical pullback.

theorem pullback_gradient_liminf {c₁ c₂ : ℝ} (c : DFP.StrongWolfeCounterexample (Fin 2) (1 / 2) (3 / 2) c₁ c₂) (hlimit : c.gradientLimit = 1) {target : DFP.InverseIteration (Fin 2)} {P : EuclideanSpace ℝ (Fin 2) ≃L[ℝ] EuclideanSpace ℝ (Fin 2)} (hP : P = (c.iteration.inverseHessianPosDef 0).sqrtEquiv) (hdata : IdentityInitialization.PullbackData c.iteration target P) : Real.sqrt (initialMinEigenvalue c) ≤ liminf (fun k ↦ ‖DFP.gradients target.objective target.point k‖) atTop := by have hroot := positiveRoot_spectral_bounds (c.iteration.inverseHessianPosDef 0) rw [← hP] at hroot have h := pulledGradient_liminf_ge c P (initialEigenvalues_pos c).1.le hroot.2.1 simpa only [hdata.gradients, hlimit, mul_one] using h

Helper for cor:identity-initialization: the source identity-block extension preserves each normalized planar gradient norm exactly.

theorem extension_gradient_norm {n : ℕ} {hn : 2 ≤ n} {source : DFP.InverseIteration (Fin 2)} {target : DFP.InverseIteration (Fin n)} (h : IdentityInitialization.DimensionExtensionData n hn source target) (k : ℕ) : ‖DFP.gradients target.objective target.point k‖ = ‖DFP.gradients source.objective source.point k‖ := by rw [extension_gradients h, (OrthogonalExtension.planeEmbedding n hn).norm_map]

Helper for cor:identity-initialization: the SAME orthogonal extension has the displayed minimum and maximum of the planar and identity-block bounds.

theorem extension_hessian_bounds {n : ℕ} {hn : 2 ≤ n} {m M : ℝ} {source : DFP.InverseIteration (Fin 2)} {target : DFP.InverseIteration (Fin n)} (h : IdentityInitialization.DimensionExtensionData n hn source target) (hC2 : ContDiff ℝ 2 source.objective) (hm : 0 < m) (hbound : HasHessianBounds m M source.objective) : HasHessianBounds (min m 1) (max M 1) target.objective := by have hwide := PlanarCounterexample.hessianBounds_mono hC2 hbound (min_le_left m 1) (le_max_left M 1) have hsum := EuclideanSpace.OrthogonalSum.Gradient.hasHessianBounds_objective (kappa := Fin (n - 2)) hC2 hwide (min_le_right m 1) (le_max_right M 1) have hsumC2 := EuclideanSpace.OrthogonalSum.Gradient.contDiff_objective (kappa := Fin (n - 2)) hC2 have hdiff := (hsumC2.gradient_succ (n := 1)).differentiable_one rw [h.objective] exact hsum.comp_linearIsometryEquiv (OrthogonalExtension.coordinateEquiv n hn) hdiff (lt_min hm zero_lt_one).le (zero_lt_one.trans_le (le_max_right M 1)).le
end DFPWolfe.V21.IdentityQuantitativenamespace DFPWolfe.V21open IdentityQuantitative

cor:identity-initialization, quantitative paragraph (main.tex:1185–1210). The SAME original polar source and literal positive-root normalization have global planar Hessian bounds and , and transformed gradient-norm liminf at least . The canonical eigenvalues are in decreasing order, with indices one and zero respectively, and are positive.

The accepted normalized matrix iteration, its objective , points , matrices , original positive alpha and Wolfe pair are retained through Unknown identifier `PullbackData`PullbackData. The SAME subsequent identity-block extension has the displayed minimum/maximum with one, exactly preserves normalized planar gradient norms, and retains the full centered ellipse, half-Hölder Hessian and unique origin. The existing certificate bounds remain as provenance; the additional sharp bounds below hold on those VERY SAME iterations.

theorem identityInitializationQuantitative (n : ℕ) (hn : 2 ≤ n) (c₁ c₂ : ℝ) (hc₁ : 0 < c₁) (hc₁lim : c₁ < 2 / 3) (hc₂lim : 2 / 3 ≤ c₂) (hc₂ : c₂ < 1) : ∃ νStar > baseAngle, ∃ κ > 0, ∃ j₀ : ℕ, 0 < j₀ ∧ ∃ source : DFP.StrongWolfeCounterexample (Fin 2) (1 / 2) (3 / 2) c₁ c₂, PlanarCounterexample.SourceIdentity (Parameters.of j₀ νStar) κ source ∧ PlanarCounterexample.CounterexampleProperties (1 / 2) source ∧ 0 < initialMinEigenvalue source ∧ 0 < initialMaxEigenvalue source ∧ ∃ (P : EuclideanSpace ℝ (Fin 2) ≃L[ℝ] EuclideanSpace ℝ (Fin 2)) (m M : ℝ) (planar : DFP.WolfeCounterexample.MatrixIdentityLiminfStrongWolfeCertificate 2 m M c₁ c₂), P = (source.iteration.inverseHessianPosDef 0).sqrtEquiv ∧ IdentityInitialization.PullbackData source.iteration planar.iteration P ∧ HasHessianBounds (initialMinEigenvalue source / 2) (3 * initialMaxEigenvalue source / 2) planar.iteration.objective ∧ Real.sqrt (initialMinEigenvalue source) ≤ liminf (fun k ↦ ‖DFP.gradients planar.iteration.objective planar.iteration.point k‖) atTop ∧ ∃ result : DFP.WolfeCounterexample.MatrixIdentityLiminfStrongWolfeCertificate n (min m 1) (max M 1) c₁ c₂, IdentityInitialization.DimensionExtensionData n hn planar.iteration result.iteration ∧ IdentityInitialization.EllipseObjectiveProperties result.iteration ((OrthogonalExtension.planeEmbedding n hn).toLinearMap.comp P.symm.toLinearMap) ∧ HasHessianBounds (min (initialMinEigenvalue source / 2) 1) (max (3 * initialMaxEigenvalue source / 2) 1) result.iteration.objective ∧ Real.sqrt (initialMinEigenvalue source) ≤ liminf (fun k ↦ ‖DFP.gradients result.iteration.objective result.iteration.point k‖) atTop ∧ result.iteration.stepLength = source.iteration.stepLength ∧ ∀ k, ‖DFP.gradients result.iteration.objective result.iteration.point k‖ = ‖DFP.gradients planar.iteration.objective planar.iteration.point k‖ := by have hhalf : (0 : ℝ) < 1 / 2 := by norm_num have hhalfOne : (1 / 2 : ℝ) < 1 := by norm_num obtain ⟨νStar, hνStar, κ, hκ, j₀, hj₀, source, hsource, hproperties⟩ := PlanarCounterexample.planarCounterexample c₁ c₂ (1 / 2) hc₁ hc₁lim hc₂lim hc₂ hhalf hhalfOne obtain ⟨P, m, M, planar, hP, hdata, hellipse⟩ := IdentityInitialization.normalizePlanarWithProperties source hproperties.origin hproperties.unique_minimizer hproperties.half_holder hproperties.cluster have heigen := initialEigenvalues_pos source have hplanar := pullback_hessian_bounds source hP hdata have hgradient := pullback_gradient_liminf source hproperties.gradientLimit hP hdata obtain ⟨result, hextend, hfinal⟩ := IdentityInitialization.extendNormalizedPlanar n hn planar P.symm.toLinearMap hellipse have hextended := extension_hessian_bounds hextend planar.objectiveContDiff (half_pos heigen.1) hplanar have hnorm := extension_gradient_norm hextend have hliminf : Real.sqrt (initialMinEigenvalue source) ≤ liminf (fun k ↦ ‖DFP.gradients result.iteration.objective result.iteration.point k‖) atTop := by simpa only [hnorm] using hgradient have halpha : result.iteration.stepLength = source.iteration.stepLength := hextend.stepLength.trans hdata.stepLength exact ⟨νStar, hνStar, κ, hκ, j₀, hj₀, source, hsource, hproperties, heigen.1, heigen.2, P, m, M, planar, hP, hdata, hplanar, hgradient, result, hextend, hfinal, hextended, hliminf, halpha, hnorm⟩
end DFPWolfe.V21