v21 Lemma 7: general secant degeneration

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

Source header · Attribution source

public sectionopen Filteropen DFP.PlanarConvergence.SecantDegenerationopen scoped Topology ContDiffnamespace DFPWolfe.V21

Helper for lem:planar-degeneration and eq:planar-scalar-definition: the source step and secant are the actual displacement and gradient difference.

theorem planarStepSecantIdentities (iteration : DFP.SecantIteration 2) (k : ℕ) : step iteration k = iteration.point (k + 1) - iteration.point k ∧ secant iteration k = gradient iteration.objective (iteration.point (k + 1)) - gradient iteration.objective (iteration.point k) := by exact ⟨step_def iteration k, secant_def iteration k⟩

Helper for lem:planar-degeneration and eq:planar-scalar-definition: the curvature is , and the original coefficient for Unknown identifier `k`sorry ≥ 1 : Propk≥1 is . Natural subtraction merely totalizes the latter at zero.

theorem planarScalarDefinitions (iteration : DFP.SecantIteration 2) (k : ℕ) : curvature iteration k = inner ℝ (step iteration k) (secant iteration k) / ‖step iteration k‖ ^ 2 ∧ freeCoefficient iteration k = curvature iteration (k - 1) * (iteration.inverseHessian k).det := by exact ⟨curvature_def iteration k, freeCoefficient_def iteration k⟩

lem:planar-degeneration (v21 Lemma 7). A C² globally μ-strongly convex planar objective has a unique global minimizer. For nonstationary iterates generated by symmetric positive definite search matrices satisfying the previous secant equation, with positive step lengths and fixed weak Wolfe conditions, failure of convergence to this minimizer forces degeneration of the source free coefficient and smallest eigenvalue. The predicate LineSearch.IsWeakWolfe.{u} {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] (c₁ c₂ : ℝ) (f : E → ℝ) (x s : E) : PropLineSearch.IsWeakWolfe includes and both source inequalities.

With the exact scalars in Unknown identifier `planarScalarDefinitions`planarScalarDefinitions, eq:planar-degeneration is expressed by the projections of DFP.PlanarConvergence.SecantDegeneration.DegenerationEstimates (iteration : DFP.SecantIteration 2) : PropDegenerationEstimates. Unknown identifier `positive`positive gives for every Unknown identifier `k`sorry ≥ 1 : Propk≥1; Unknown identifier `product_bound`product_bound gives eventually, with one Unknown identifier `C`sorry > 0 : PropC>0; Unknown identifier `coefficient_limit`coefficient_limit gives . Unknown identifier `operator_bound`operator_bound bounds the induced Euclidean norm ‖sorry‖ : ℝ‖Function expected at Matrix.toEuclideanCLM but this term has type Matrix ?m.4 ?m.4 ?m.3 ≃⋆ₐ[?m.3] EuclideanSpace ?m.3 ?m.4 →L[?m.3] EuclideanSpace ?m.3 ?m.4 Note: Expected a function because this term is being applied to the argument H_kMatrix.toEuclideanCLM H_k‖ for every Unknown identifier `k`k, including Unknown identifier `H₀`H₀. Unknown identifier `determinant_limit`determinant_limit gives Unknown identifier `det`sorry → sorry : Sort (imax u_1 u_2)det H_k→failed to synthesize instance of type class OfNat (Sort ?u.2) 0 numerals are polymorphic in Lean, but the numeral `0` cannot be used in a context where the expected type is Sort ?u.2 due to the absence of the instance above Hint: Type class instance resolution failures can be inspected with the `set_option trace.Meta.synthInstance true` command.0; Unknown identifier `smallest_eigenvalue_limit`smallest_eigenvalue_limit gives convergence to zero of the canonical decreasingly ordered Hermitian eigenvalue at index 1 : ℕ1, the planar minimum.

The accepted proof follows eq:planar-secant-representation and its energy absorption argument. The general DFP.SecantIteration (n : ℕ) : TypeDFP.SecantIteration interface requires neither a DFP update nor Hessian Lipschitz continuity.

theorem planarDegeneration (iteration : DFP.SecantIteration 2) {μ c₁ c₂ : ℝ} (hf : ContDiff ℝ 2 iteration.objective) (hstrong : StrongConvexOn Set.univ μ iteration.objective) (hμ : 0 < μ) (hStep : ∀ k, 0 < iteration.stepLength k) (hw : ∀ k, LineSearch.IsWeakWolfe c₁ c₂ iteration.objective (iteration.point k) (iteration.point (k + 1) - iteration.point k)) : ∃! xstar : EuclideanSpace ℝ (Fin 2), (∀ z, iteration.objective xstar ≤ iteration.objective z) ∧ (¬ Tendsto iteration.point atTop (𝓝 xstar) → DegenerationEstimates iteration) := by exact DFP.PlanarConvergence.SecantDegeneration.planarDegeneration iteration hf hstrong hμ hStep hw
end DFPWolfe.V21