Chapter 03 — Newton’s Methods
Proofs omitted. Hover over highlighted terms to see their Lean types.
Exercise 3.1
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Exercise 3.1 (1): the exact steepest-descent update from (-2, 4) is (26 / 17, 38 / 17).
open Matrix
-- Domain sampling:
-- * `IsExactLineSearchStepOnNonnegativeRay` is the Chapter 2 source-facing owner for exact
-- line search on the nonnegative ray, built on mathlib's minimizer owner `IsMinOn`.
-- * `steepestDescentDirection` and `steepestDescentStep` are the Chapter 3 owners for the
-- steepest-descent direction and update.
-- * `IsNewtonDirectionAt` is the Chapter 3 source-facing owner for Newton directions;
-- `newtonDirection` and `newtonNextIterate` are the explicit inverse-form bridge
-- declarations under nonsingularity.
-- This exercise keeps only the concrete quadratic data source-facing and states the update
-- results through those existing owners.
local notation "Point" => EuclideanSpace ℝ (Fin 2)
theorem chapter03Exercise31_steepestDescentMethod :
steepestDescentStep
chapter03Exercise31Objective
chapter03Exercise31InitialPoint
chapter03Exercise31SteepestDescentStepSize =
chapter03Exercise31SteepestDescentFirstIterate
Exercise 3.2
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Exercise 3.2 (1): for f(x) = (1 / 2) * (x 0 ^ 2 + 9 * x 1 ^ 2), the steepest-descent specialization of a Chapter 2 exact-line-search method with canonical search direction steepestDescentDirection satisfies the explicit linear G-energy bound with contraction factor 4 / 5.
open Matrix
theorem steepestDescent_diagQuadraticOneNine_energyLinearRate
(A :
GeneralUnconstrainedOptimizationMethod 2
(quadraticObjective diagMatrixOneNine 0 0))
(h_direction :
∀ k,
A.d k =
steepestDescentDirection (quadraticObjective diagMatrixOneNine 0 0) (A k))
(k : ℕ) :
ellipsoidNorm diagMatrixOneNine (A k) ≤
(((4 : ℝ) / 5) ^ k) * ellipsoidNorm diagMatrixOneNine (A 0)
Exercise 3.3
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Exercise 3.3: the objective f(x) = 1 / 2 * ‖x‖^2 + σ / 4 * (xᵀ A x)^2 on ℝ⁴, where A = quarticNewtonTestMatrix and xᵀ A x is formalized as quarticNewtonTestQuadraticForm x.
open scoped Matrix
local notation "Point" => EuclideanSpace ℝ (Fin 4)
def quarticNewtonTestObjective (σ : ℝ) (x : Point) : ℝ :=
(1 / 2 : ℝ) * ‖x‖ ^ (2 : ℕ) +
(σ / 4) * (quarticNewtonTestQuadraticForm x) ^ (2 : ℕ)Exercise 3.4
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Exercise 3.4: the reference point (1, 1) is a global minimizer of the Rosenbrock function.
theorem rosenbrockFunction_isMinOn :
IsMinOn rosenbrockFunction Set.univ rosenbrockMinimizerExercise 3.5
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Exercise 3.5 (1): the diag(1, 10000) quadratic from Exercise 3.2 yields the explicit G-energy decay factor 1 - 2 / 10001, which is very close to 1.
open Filter
theorem steepestDescent_diagQuadraticOneTenThousand_energyLinearRate_close_to_one
(A :
GeneralUnconstrainedOptimizationMethod 2
(quadraticObjective diagMatrixOneTenThousand 0 0))
(h_direction :
∀ k : ℕ,
A.d k =
steepestDescentDirection
(quadraticObjective diagMatrixOneTenThousand 0 0)
(A k)) :
∀ k : ℕ,
ellipsoidNorm diagMatrixOneTenThousand (A k) ≤
(((1 : ℝ) - 2 / 10001) ^ k) * ellipsoidNorm diagMatrixOneTenThousand (A 0)
Exercise 3.6
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Exercise 3.6: this exercise is exactly the first clause of the Chapter 3.6 inexact-Newton convergence theorem already owned by Theorem_3_6_6. Source/core/bridge triage: * source-facing: the regular-zero and inexact-Newton owners from Chapter 3.6 * core/canonical: inexactNewton_tendsto_root_and_eventually_linear_of_forcing_bounded * bridge/view: none; the exercise statement matches the existing owner exactly The previous local IsRegularZero and IsInexactNewtonSequence declarations duplicated the Chapter 3.6 owner surface from Theorem_3_6_2 and Algorithm_3_6_extra_2. This file is therefore recall-only.
#check inexactNewton_tendsto_root_and_eventually_linear_of_forcing_bounded
3.1 — The Steepest Descent Method
Algorithm 3.1.1
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Algorithm 3.1.1: the steepest descent method on a real Hilbert space starts from x₀, uses explicit gradient data g k and search directions d k, stops when ‖g k‖ ≤ ε, and otherwise updates by exact line search in the negative-gradient direction.
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
-- Domain sampling: the source-facing exact line-search owner already appears in Chapter 2 as
-- `IsExactLineSearchStepOnNonnegativeRay`, built on mathlib's canonical minimizer owner
-- `IsMinOn`. The Chapter 3 owner declarations for the steepest-descent direction and update are
-- `steepestDescentDirection` and `steepestDescentStep`. This file keeps the algorithm data
-- source-facing and exposes those Chapter 3 owners as the derived API.
structure IsSteepestDescentMethod (f : E → ℝ)
(ε : ℝ) (x₀ : E) (x g d : ℕ → E) (α : ℕ → ℝ) : Prop where
epsilon_pos : 0 < ε
x_zero : x 0 = x₀
hasGradientAt : ∀ k : ℕ, HasGradientAt f (g k) (x k)
direction_eq : ∀ k, ε < ‖g k‖ → d k = -g k
exactLineSearch :
∀ k, ε < ‖g k‖ → IsExactLineSearchStepOnNonnegativeRay f (x k) (d k) (α k)
next_eq :
∀ k, ε < ‖g k‖ → x (k + 1) = x k + α k • d k
Theorem 3.1.2
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Theorem 3.1.2 (Global convergence theorem of the steepest descent method): if f : E → ℝ on a real Hilbert space E is C¹, the iterates form a Chapter 3 IsSteepestDescentSequence, and a subsequence x ∘ φ converges to xStar, then xStar is a stationary point of f.
open Filter
variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
-- Domain sampling pass:
-- Primary domain: smooth unconstrained optimization with exact line search on the
-- steepest-descent ray.
-- Sampled owner declarations:
-- * `IsStationaryPoint` in Chapter01 Definition 1.4.7;
-- * `IsExactLineSearchStepOnNonnegativeRay` in Chapter02 Definition 2.2-extra-1;
-- * `steepestDescentDirection`, `steepestDescentObjective`, and `steepestDescentStep` in
-- Chapter03 Definition 3.1-extra-1.
-- Owner abstraction:
-- * source-facing: a steepest-descent iterate sequence together with an accumulation point of a
-- subsequence;
-- * core/canonical: `IsSteepestDescentSequence`, `steepestDescentObjective`, and
-- `IsStationaryPoint`;
-- * bridge/view: `IsSteepestDescentSequence.exactLineSearch` and
-- `IsSteepestDescentSequence.update` recover the Chapter 2 line-search owner and the Chapter 3
-- update equation on the canonical steepest-descent ray, while the raw formulas
-- `x - α • gradient f x` and `gradient f xStar = 0` remain derived API.
-- Primitive data are therefore the Chapter 3 sequence owner plus the convergent subsequence; the
-- old separate exact-line-search and update hypotheses were duplicate views of that owner.
theorem exactLineSearchSteepestDescent_accumulationPoint_stationary
(f : E → ℝ)
(x : ℕ → E)
(α : ℕ → ℝ)
(hC1 : ContDiff ℝ 1 f)
(hSeq : IsSteepestDescentSequence f x α)
{xStar : E}
{φ : ℕ → ℕ}
(hφ : StrictMono φ)
(hTendsto : Tendsto (x ∘ φ) atTop (nhds xStar)) :
IsStationaryPoint f xStar
Theorem 3.1.3
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Theorem 3.1.3 (Global convergence theorem of the steepest descent method): if f : E → ℝ on a real Hilbert space E is C², the derivative of gradient f is globally bounded in operator norm by a constant M, and x, g, d, α are generated by Algorithm 3.1.1 from x₀ with tolerance ε, then the steepest descent method terminates at some finite iteration, or f (x k) ⟶ -∞, or gradient f (x k) ⟶ 0.
open Filter InnerProductSpace
variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable {f : E → ℝ} {ε : ℝ} {x₀ : E} {x g d : ℕ → E} {α : ℕ → ℝ}
-- Domain sampling:
-- * source-facing owner: `IsSteepestDescentMethod` in Algorithm 3.1.1;
-- * core/canonical owners inspected: `steepestDescentDirection`, `steepestDescentStep`, and
-- `IsExactLineSearchStepOnNonnegativeRay`;
-- * bridge/view avoided here: a second local run predicate restating the same iterate, gradient,
-- direction, exact-line-search, and update data.
--
-- Triage:
-- * source-facing: the global alternative for a steepest-descent run;
-- * core/canonical: the Chapter 3/Chapter 2 owners above;
-- * bridge/view removed: the concrete `ℝ^n` model, since the theorem only uses the real Hilbert
-- space structure already required by the owner API.
--
-- Primitive data are therefore just the objective `f`, the steepest-descent run data
-- `x, g, d, α`, and the `IsSteepestDescentMethod` witness. The exact line-search and update
-- clauses remain derived through that owner.
theorem steepestDescent_globalConvergence
(M : ℝ)
(hC2 : ContDiff ℝ 2 f)
(hHessianBound : ∀ y : E, ‖fderiv ℝ (gradient f) y‖ ≤ M)
(hMethod : IsSteepestDescentMethod f ε x₀ x g d α) :
(∃ k : ℕ, ‖gradient f (x k)‖ ≤ ε) ∨
Tendsto (f ∘ x) atTop atBot ∨
Tendsto (gradient f ∘ x) atTop (nhds 0)
Theorem 3.1.4
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Theorem 3.1.4 (Convergence theorem of the steepest descent method with inexact line search): if f : E → ℝ is C¹, A : InexactLineSearchMethod f (gradient f) is a steepest-descent run with inexact line search in the Chapter 2 sense, and a subsequence of the iterate sequence converges to xStar, then xStar is a stationary point of f, formalized by the Chapter 1 owner IsStationaryPoint f xStar. The zero-tolerance stopping rule and the standard stuttering-tail convention after termination are part of the bridge hypothesis hMethod : InexactLineSearchMethod.IsSteepestDescent f A, while the inherited Chapter 2 built-in initial-sublevel-set gradient regularity hypothesis is packaged in hSetup : SteepestDescentGlobalConvergenceSetup f A.
open Filter
variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
-- Domain sampling pass:
-- Primary domain: smooth unconstrained optimization with inexact line search on the canonical
-- steepest-descent ray.
-- Sampled owner declarations:
-- * `IsStationaryPoint` in Chapter01 Definition 1.4.7;
-- * `InexactLineSearchMethod` in Chapter02 Algorithm 2.5.3;
-- * `initialSublevelSet` in Chapter02 InitialSublevelSet;
-- * `steepestDescentDirection` and `steepestDescentStep` in Chapter03 Definition 3.1-extra-1;
-- Triage:
-- * source-facing: accumulation-point stationarity for steepest descent with inexact
-- line search;
-- * core/canonical: `InexactLineSearchMethod`, `initialSublevelSet`,
-- `steepestDescentDirection`, `steepestDescentStep`, and the Chapter 1
-- stationary-point owner `IsStationaryPoint`;
-- * bridge/view added here: `InexactLineSearchMethod.IsSteepestDescent`, which records the
-- zero-tolerance steepest-descent specialization of the generic Chapter 2 owner together with
-- the standard infinite-sequence stuttering convention after termination; the stronger local
-- Wolfe-Powell specialization remains available as auxiliary support API.
-- Primitive data for Theorem 3.1.4 are therefore the canonical Chapter 2 run owner together
-- with the Chapter 3 steepest-descent bridge and the Chapter 1 stationary-point owner. The
-- source-explicit `C¹` hypothesis remains on the labeled theorem surface, while the inherited
-- Chapter 2 gradient regularity on `initialSublevelSet f A.x0` is packaged in the local support
-- owner `SteepestDescentGlobalConvergenceSetup`.
theorem steepestDescent_accumulationPoint_stationary
(f : E → ℝ)
(A : InexactLineSearchMethod f (gradient f))
(hC1 : ContDiff ℝ 1 f)
(hSetup : SteepestDescentGlobalConvergenceSetup f A)
(hMethod : InexactLineSearchMethod.IsSteepestDescent f A)
{xStar : E}
{φ : ℕ → ℕ}
(hφ : StrictMono φ)
(hTendsto : Tendsto (A ∘ φ) atTop (nhds xStar)) :
IsStationaryPoint f xStar
Theorem 3.1.5
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Theorem 3.1.5 (1): for a symmetric positive definite quadratic objective, the exact-line-search steepest-descent iterates converge to the minimizer 0.
open Matrix
open Filter
variable {n : ℕ}
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
local notation "Point" => EuclideanSpace ℝ (Fin n)
variable {x : ℕ → Point} {α : ℕ → ℝ}
-- Domain sampling for this item:
-- * source-facing: steepest descent with exact line search on the centered quadratic objective
-- `x ↦ (1 / 2) * xᵀ G x`;
-- * core/canonical: the project quadratic owner `quadraticObjective G b c`,
-- `gradient_quadraticObjective`, `steepestDescentDirection`,
-- `IsExactLineSearchStepOnNonnegativeRay`, `posDefEigenvalues`, `ellipsoidNorm`, and the
-- Euclidean norm owner `‖·‖₂`, together with the Chapter 3 run owner
-- `IsSteepestDescentSequence`;
-- * bridge/view: the centered specialization `quadraticObjective G 0 0`, together with the
-- quadratic-gradient identity and the nonstationary closed-form exact line-search step size.
--
-- Triage:
-- * source-facing: the centered quadratic objective and the exact-line-search steepest-descent
-- iterates attached to it;
-- * core/canonical: the project quadratic owner `quadraticObjective G b c`;
-- * bridge/view: `quadraticObjective G 0 0`.
--
-- Primitive data for this theorem family are the iterate sequence `x`, the step sizes `α`, and
-- the Chapter 3 owner `IsSteepestDescentSequence f x α`. The one-step contraction clauses record
-- their ratio domain directly by the nonstationary-step hypothesis `x k ≠ 0`, rather than
-- carrying the heavier algorithm wrapper with tolerance, initial point, and auxiliary streams.
variable (G : MatrixN)
local notation "f" => quadraticObjective G 0 0
theorem steepestDescentQuadraticConverges
(hG : G.PosDef)
(x : ℕ → Point)
(α : ℕ → ℝ)
(hSeq : IsSteepestDescentSequence f x α) :
Tendsto x atTop (nhds 0)
Theorem 3.1.6
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Theorem 3.1.6: let f : E → ℝ on a real Hilbert space E be C² on a ball about the limit point xStar, and suppose its Hessian quadratic form is bounded below by a positive constant m and above by M on that ball, expressed by the Chapter 1 owners HasHessianLowerBoundOn and HasHessianUpperBoundOn. If x and α form a Chapter 3 IsSteepestDescentSequence whose iterates tend to xStar, then xStar is forced to be stationary by the convergent exact-line-search steepest-descent run, the lower Hessian bound upgrades that stationary limit point to a local minimizer, and therefore x converges to xStar at least linearly, expressed by the Chapter 3 eventual-contraction owner HasEventuallyLinearConvergenceTo reused by the refined exact-line-search convergence theorem of Chapter 2. The local Hessian control is only available near xStar, so the stronger global contraction owner HasLinearConvergenceTo would require an additional run-in-ball hypothesis from the initial iterate onward. This keeps the source-faithful “at least linear” owner rather than the stricter Chapter 1 R-linear predicate, without keeping stationarity as redundant public data.
open Filter
variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
-- Domain sampling:
-- * primary domain: local linear convergence of steepest descent with exact line search near a
-- nondegenerate limit point;
-- * source-facing surface for this theorem: the iterate sequence `x`, step sizes `α`, and the
-- Chapter 3 owner `IsSteepestDescentSequence f x α`, with the rate conclusion expressed by
-- the Chapter 3 owner `HasEventuallyLinearConvergenceTo`;
-- * core/canonical owners inspected: `HasEventuallyLinearConvergenceTo`,
-- `rLinearConvergenceTo`,
-- `HasHessianLowerBoundOn`,
-- `HasHessianUpperBoundOn`,
-- `exactLineSearch_atLeastLinearConvergenceTo_of_tendsto_isLocalMin_of_angleBound`,
-- `exactLineSearchSteepestDescent_accumulationPoint_stationary`,
-- `isStrictLocalMin_of_isStationaryPoint_of_iteratedFDeriv_pos`,
-- `steepestDescentDirection`, `steepestDescentStep`, `IsExactLineSearchStepOnNonnegativeRay`,
-- `IsStationaryPoint`, and `IsStrictLocalMin.isLocalMin`;
-- * bridge/view precedent: `IsSteepestDescentSequence.exactLineSearch` and
-- `IsSteepestDescentSequence.update` recover the Chapter 2 exact-line-search owner and the
-- Chapter 3 update equation without keeping them as parallel primitive hypotheses.
--
-- Triage:
-- * source-facing: this theorem is about a steepest-descent run converging at least linearly to
-- `xStar`;
-- * core/canonical: the direction/update/exact-line-search owners above together with the
-- Chapter 3 eventual-linear owner `HasEventuallyLinearConvergenceTo`;
-- * bridge/view removed here: the separate exact-line-search and update hypotheses, which are
-- already packaged by the Chapter 3 owner `IsSteepestDescentSequence`, and the redundant
-- stationary-point binder at `xStar`, which is derived from the convergent steepest-descent
-- run plus the local `C²` neighborhood hypothesis; the raw pointwise Hessian quadratic-form
-- binder on `Metric.ball xStar ε`, which is already owned in Chapter 1 by
-- `HasHessianLowerBoundOn` / `HasHessianUpperBoundOn`;
-- * stricter derived companions only: the global contraction owner
-- `HasLinearConvergenceTo` and the Chapter 1 rate owner `rLinearConvergenceTo`, which require
-- stronger data than the source-facing local hypotheses and exclude finite termination or
-- superlinear tails.
--
-- Primitive data are therefore just the steepest-descent iterate and step-size sequences together
-- with the Chapter 3 sequence owner `IsSteepestDescentSequence`, the local `C²` hypothesis, and
-- the Chapter 1 Hessian-bound owners on `Metric.ball xStar ε`. The search direction, exact line
-- search, and update clauses are derived through the sequence owner, the limit-point
-- stationarity and local-minimum bridge are internal consequences of the run plus those
-- canonical Hessian-bound owners, and the at-least-linear conclusion is expressed by the Chapter
-- 3 eventual-contraction owner `HasEventuallyLinearConvergenceTo`.
theorem steepestDescent_atLeastLinear
(f : E → ℝ)
(x : ℕ → E)
(α : ℕ → ℝ)
(xStar : E)
(ε m M : ℝ)
(hε : 0 < ε)
(hm : 0 < m)
(hC2 : ContDiffOn ℝ 2 f (Metric.ball xStar ε))
(hLower : HasHessianLowerBoundOn (Metric.ball xStar ε) f m)
(hUpper : HasHessianUpperBoundOn (Metric.ball xStar ε) f M)
(hSeq : IsSteepestDescentSequence f x α)
(hTendsto : Tendsto x atTop (nhds xStar)) :
HasEventuallyLinearConvergenceTo x xStar
Theorem 3.1.7
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Theorem 3.1.7 (1): assume f is C² near xStar, xStar is stationary, the Hessian at xStar is positive definite, and x is a steepest-descent sequence with step sizes α whose iterates converge to xStar. Then every ratio steepestDescentContractionFactor f xStar x k whose objective-gap denominator is nonzero is less than 1.
open Filter
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
-- Domain sampling:
-- * `IsSteepestDescentMethod` is the Chapter 3 owner for steepest-descent runs, and
-- `Theorem_3_1_6` already refines local convergence further to direct iterate/step-size data.
-- * `IsStationaryPoint` is the project owner for genuine stationary-point data.
-- * `IsExactLineSearchStepOnNonnegativeRay` is the Chapter 2 owner for exact line search on the
-- nonnegative steepest-descent ray.
-- * `IsSteepestDescentSequence` is the Chapter 3 owner for exact-line-search steepest-descent
-- iterates with their canonical updates.
-- * `hessianAt` / `hessianQuadraticAt` from `Definition_3_5_1` are the project Hessian owners
-- for Euclidean problems.
-- * The source-facing local `C²` and quadratic-form bounds are the primitive neighborhood data,
-- and the spectral statements below are bridge lemmas from those bounds to `hessianAt`.
--
-- Triage:
-- * source-facing: asymptotic contraction of a steepest-descent iterate sequence;
-- * core/canonical: `steepestDescentDirection`, `steepestDescentStep`,
-- `IsExactLineSearchStepOnNonnegativeRay`, and the Hessian owners above;
-- * bridge/view removed here: the Chapter 2 wrapper
-- `GeneralUnconstrainedOptimizationMethod` plus a separate direction-equality hypothesis.
--
-- Primitive data are therefore the iterate sequence `x`, the step sizes `α`, and the source-facing
-- Chapter 3 owner `IsSteepestDescentSequence f x α`.
variable {f : Point → ℝ} {xStar : Point} {x : ℕ → Point} {α : ℕ → ℝ}
theorem steepestDescentContractionFactor_lt_one_of_sourceHypotheses
(x : ℕ → Point)
(α : ℕ → ℝ)
(hC2 : ∃ s ∈ nhds xStar, ContDiffOn ℝ 2 f s)
(hStationary : IsStationaryPoint f xStar)
(hPosDef : ∀ y : Point, y ≠ 0 → 0 < hessianQuadraticAt f xStar y)
(hSeq : IsSteepestDescentSequence f x α)
(hx : Tendsto x atTop (nhds xStar))
(k : ℕ)
(hGapNe : f (x k) ≠ f xStar) :
steepestDescentContractionFactor f xStar x k < 1
Algorithm 3.1.8
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Algorithm 3.1.8: a Barzilai-Borwein gradient-method run for f on a real Hilbert space starts from x0, stops when ‖g k‖ ≤ ε, uses a genuine line-search step at the first nonterminal stage along the steepest-descent direction, and thereafter uses formula (3.1.29) or (3.1.30) for the step size while updating by the canonical steepest-descent step.
universe u
-- Domain sampling for this file:
-- * Chapter 2 already owns the genuine line-search notion `IsLineSearchStep`
-- * Chapter 3 already owns the canonical steepest-descent direction and update through
-- `steepestDescentDirection` and `steepestDescentStep`
-- * `Algorithm_3_1_1.lean` already places the Chapter 3 steepest-descent method on the
-- canonical real-Hilbert-space owner layer, so this file should reuse that ambient level
-- * the source-facing primitive data here are the iterate, gradient, and step-size sequences;
-- the search direction is derived from the chapter owner `steepestDescentDirection`, while the
-- later Barzilai-Borwein steplength rule is recorded by the two textbook quotient predicates
-- with their admissible denominator conditions
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
structure BarzilaiBorweinGradientMethod (E : Type u)
[NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] where
f : E → ℝ
x0 : E
ε : ℝ
x : ℕ → E
g : ℕ → E
α : ℕ → ℝ
x_zero : x 0 = x0
epsilon_pos : 0 < ε
hasGradientAt : ∀ k : ℕ, HasGradientAt f (g k) (x k)
initialLineSearch :
ε < ‖g 0‖ →
IsLineSearchStep f (x 0) (steepestDescentDirection f (x 0)) (α 0)
initialUpdate :
ε < ‖g 0‖ →
x 1 = steepestDescentStep f (x 0) (α 0)
laterStepSize :
∀ k : ℕ, ε < ‖g (k + 1)‖ →
IsBarzilaiBorweinStepSize (x (k + 1)) (x k) (g (k + 1)) (g k) (α (k + 1))
laterUpdate :
∀ k : ℕ, ε < ‖g (k + 1)‖ →
x (k + 2) = steepestDescentStep f (x (k + 1)) (α (k + 1))
Algorithm 3.1.9
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Algorithm 3.1.9: a run of the Barzilai-Borwein gradient algorithm with nonmonotone line search on a real Hilbert space. The primitive run data are x, g, α, and the recorded shrink-factor traces shrinkFactors; the Step 5 accepted step λ_k and the Step 6 difference y_k = g_{k+1} - g_k are derived from those owners rather than stored separately. At every iterate k, the field hasGradientAt records that g k is the gradient of f at x k. The parameter object carries the Step 0 cutoff parameters α^(l) and α^(u) together with the source cutoff hypothesis 0 < α^(l) < α^(u). For every index k with params.ε < ‖g k‖, the fields shrinkFactors_mem, lineSearch, nextPoint_eq, and nextAlpha_eq encode Step 2 through Step 6: reset α_k if it leaves the admissible interval, start from the reciprocal trial step size, shrink it by finitely many factors in [σ₁, σ₂], package the Step 4/Step 5 least-accepted trial through the canonical backtracking owner, update x_{k+1} by the canonical steepest-descent owner with the derived accepted step λ_k, and then update α_{k+1} by the source quotient formula on that nonterminal step. The positivity of λ_k is derived from the cutoff bounds, δ > 0, and the canonical backtracking owner rather than stored as extra primitive data.
universe u
-- Source/core/bridge triage:
-- * source-facing: the Barzilai-Borwein Step 2 cutoff, the Step 4 nonmonotone acceptance
-- inequality, and the Step 6 spectral update recorded along one run;
-- * core/canonical owners inspected: `steepestDescentDirection`, `steepestDescentStep`,
-- `nonmonotoneArmijoReferenceValue`, and `IsBacktrackingLineSearchStep`;
-- * bridge/view: the normalized backtracking factor sequence
-- `backtrackingArmijoStepSizes params.σ₁ (shrinkFactors k)` on the scaled canonical
-- steepest-descent direction
-- `(barzilaiBorweinTrialStep params (α k)) • steepestDescentDirection f (x k)`.
variable {E : Type u}
variable [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
structure BarzilaiBorweinGradientRun (E : Type u)
[NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] where
params : BarzilaiBorweinGradientParams E
f : E → ℝ
x : ℕ → E
g : ℕ → E
α : ℕ → ℝ
shrinkFactors : ℕ → List ℝ
start : x 0 = params.x0
hasGradientAt (k : ℕ) : HasGradientAt f (g k) (x k)
shrinkFactors_mem (k : ℕ) (hk : params.ε < ‖g k‖) (σ : ℝ) (hσ : σ ∈ shrinkFactors k) :
params.σ₁ ≤ σ ∧ σ ≤ params.σ₂
lineSearch (k : ℕ) (hk : params.ε < ‖g k‖) :
IsBacktrackingLineSearchStep
(barzilaiBorweinAcceptable params f x k (α k))
(x k)
((barzilaiBorweinTrialStep params (α k)) • steepestDescentDirection f (x k))
(backtrackingArmijoStepSizes params.σ₁ (shrinkFactors k))
(shrinkFactors k).length
nextPoint_eq (k : ℕ) (hk : params.ε < ‖g k‖) :
x (k + 1) =
steepestDescentStep f (x k) (barzilaiBorweinStepSize params α shrinkFactors k)
nextAlpha_eq (k : ℕ) (hk : params.ε < ‖g k‖) :
α (k + 1) =
-(inner ℝ (g k) (barzilaiBorweinGradientDifference g k)) /
(barzilaiBorweinStepSize params α shrinkFactors k * inner ℝ (g k) (g k))
Theorem 3.1.10
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Theorem 3.1.10 (Kantorovich inequality): if G is a real positive definite matrix, then for every nonzero vector x the quotient (xᵀ x)^2 / ((xᵀ G x) * (xᵀ G⁻¹ x)) is bounded below by the expression formed from the largest and smallest eigenvalues of G.
open Matrix
variable {n : ℕ}
variable (G : Matrix (Fin n) (Fin n) ℝ) (hG : G.PosDef)
theorem kantorovichInequality
(lambdaMax lambdaMin : ℝ)
(hLambdaMax : IsGreatest (Set.range (posDefEigenvalues G hG)) lambdaMax)
(hLambdaMin : IsLeast (Set.range (posDefEigenvalues G hG)) lambdaMin)
(x : Fin n → ℝ) (hx : x ≠ 0) :
(x ⬝ᵥ x) ^ (2 : ℕ) /
((x ⬝ᵥ (G *ᵥ x)) * (x ⬝ᵥ (G⁻¹ *ᵥ x))) ≥
((4 : ℝ) * lambdaMax * lambdaMin) / (lambdaMax + lambdaMin) ^ (2 : ℕ)Definition 3.1.extra.1
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Definition 3.1-extra-1 (1): the source descent-direction notion is already owned by Chapter01 Definition 1.4.3 as IsDescentDirectionAt.
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
#check IsDescentDirectionAt
3.2 — Newton’s Method
Algorithm 3.2.1
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Algorithm 3.2.1: Newton's method for minimizing f : ℝⁿ → ℝ consists of a tolerance ε > 0, an initial point x₀, iterates x k, Newton directions s k, explicit gradient data g k, and Hessian matrices G k satisfying x 0 = x₀. At every index k, g k is the gradient of f at x k; at every nonterminal index with ε < ‖g k‖, G k is a Hessian matrix of f at x k, the Newton linear system (G k).mulVec (s k) = -g k is solved, and the next iterate is updated by x (k + 1) = x k + s k.
open scoped Gradient
variable {n : ℕ}
-- Chapter 3 Newton-family owners keep the objective and canonical derivative data explicit.
-- This file keeps the source-facing matrix realization of the Hessian while tying it to `f`
-- through `HasGradientAt` and `HasFDerivAt (∇ f)`.
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "Hessian" => Matrix (Fin n) (Fin n) ℝ
structure NewtonMethod (n : ℕ) (f : Point → ℝ) where
ε : ℝ
x0 : Point
x : ℕ → Point
s : ℕ → Point
g : ℕ → Point
G : ℕ → Hessian
eps_pos : 0 < ε
x_zero : x 0 = x0
hasGradientAt : ∀ k : ℕ, HasGradientAt f (g k) (x k)
hessian :
∀ k : ℕ, ε < ‖g k‖ →
HasFDerivAt (∇ f)
(((Matrix.toEuclideanCLM : Hessian ≃⋆ₐ[ℝ] Point →L[ℝ] Point) (G k)))
(x k)
linearSystem : ∀ k : ℕ, ε < ‖g k‖ → (G k).mulVec (s k) = -g k
update : ∀ k : ℕ, ε < ‖g k‖ → x (k + 1) = x k + s kTheorem 3.2.2
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Theorem 3.2.2: under the same hypotheses, every sufficiently close Newton method sequence generated from x0 converges to xStar.
open Filter
open scoped Matrix.Norms.L2Operator
open scoped Topology
-- Semantic recall: Chapter 3 already owns the canonical Hessian-matrix and quadratic-rate
-- interfaces. This file keeps only the source-faithful Newton-sequence predicate and the
-- local Hessian-neighborhood hypothesis used in Theorem 3.2.2.
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "Hessian" => Matrix (Fin n) (Fin n) ℝ
theorem newtonMethod_converges_of_posDef_and_lipschitz
(f : Point → ℝ)
(G : Point → Hessian)
(xStar : Point)
(hHessian : HasLocalLipschitzHessianMatrixAt f G xStar)
(hCritical : gradient f xStar = 0)
(hPosDef : (G xStar).PosDef) :
∃ δ : ℝ, 0 < δ ∧ ∀ x0 : Point, ‖x0 - xStar‖ < δ →
∀ x s : ℕ → Point,
IsNewtonMethodSequence f x s (fun k ↦ G (x k)) x0 →
Tendsto x atTop (𝓝 xStar)
Algorithm 3.2.3
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Algorithm 3.2.3: Newton's method with line search consists of a tolerance ε ≥ 0, an initial point x₀ : ℝⁿ, iterates x k, explicit gradient data g k, Newton directions d k, step sizes α k, and Hessian operators G k satisfying x 0 = x₀. At every index k, g k is the gradient of f at x k; at every nonterminal index with ε < ‖g k‖, the operator G k is the Hessian of f at x k, the Newton equation G k (d k) = -g k is solved, α k is an exact line-search minimizer of a ↦ f (x k + a • d k) on Set.Ici 0, and the next iterate is x (k + 1) = x k + α k • d k.
open scoped Gradient
-- Semantic recall: Step 2 is modeled with explicit gradient data `g k` and
-- `HasGradientAt`, matching local Chapter 3 precedent; the Hessian and exact
-- line search still use the canonical `∇ f`, `HasFDerivAt (∇ f)`, and the
-- repository's source-facing exact line-search owner on the nonnegative ray.
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
structure NewtonMethodWithLineSearch (n : ℕ) (f : Point → ℝ) where
ε : ℝ
x0 : Point
x : ℕ → Point
g : ℕ → Point
d : ℕ → Point
α : ℕ → ℝ
G : ℕ → Point →L[ℝ] Point
eps_nonneg : 0 ≤ ε
x_zero : x 0 = x0
hasGradientAt : ∀ k : ℕ, HasGradientAt f (g k) (x k)
hessian : ∀ k : ℕ, ε < ‖g k‖ → HasFDerivAt (∇ f) (G k) (x k)
linearSystem :
∀ k : ℕ, ε < ‖g k‖ → G k (d k) = -g k
exactLineSearch :
∀ k : ℕ, ε < ‖g k‖ → IsExactLineSearchStepOnNonnegativeRay f (x k) (d k) (α k)
update :
∀ k : ℕ, ε < ‖g k‖ →
x (k + 1) = x k + α k • d k
Theorem 3.2.4
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Theorem 3.2.4 (1). If the run of Algorithm 3.2.3 generated from A.x0 is finite and the stopping tolerance is zero, then some terminal iterate is a stationary point of f. The implementation-level equality A.g k = 0 is kept upstream as an auxiliary recorded-gradient fact, while the theorem here uses the canonical Chapter 1 owner IsStationaryPoint together with the source-facing Chapter 3 terminal-index owner A.IsTerminalIndex k.
open Filter
-- Domain sampling for this refine pass:
-- * primary domain: finite-run stationarity and nonterminating-run accumulation-point minimizer
-- statements for the Chapter 3 damped Newton method on `ℝⁿ`;
-- * inspected owner declarations:
-- - `NewtonMethodWithLineSearch` in `Algorithm_3_2_3`;
-- - `NewtonMethodWithLineSearch.DoesNotTerminate` / `terminatedAt` in `Algorithm_3_2_3`;
-- - `IsStationaryPoint` in `Chapter01/Definition_1_4_7`;
-- - `HasLowerLevelHessianLowerBound` / `lowerLevelSetOn` in `Chapter01/Theorem_1_3_19`;
-- - `IsMinOn` as the canonical minimizer owner and the Chapter 3 stronger companion
-- `newtonSequence_tendsto_minimizer` in `Theorem_3_2_5`.
--
-- Best owner abstraction:
-- * source-facing owner: `NewtonMethodWithLineSearch`;
-- * derived canonical owners: `IsStationaryPoint` for the finite zero-tolerance branch and
-- `IsMinOn` for the infinite-run minimizer conclusion on the regularity domain `D`.
--
-- Primitive data vs derived API:
-- * primitive data live in the algorithm owner itself: iterates, gradients, Hessians,
-- line-search data, the nonnegative stopping tolerance, the stop test `terminatedAt`, and the
-- stronger nontermination owner `DoesNotTerminate`;
-- * this file only adds the source-facing zero-tolerance finite-run hypothesis and the
-- lower-level-set Hessian hypotheses needed for Theorem 3.2.4;
-- * the nonterminating clause is kept at the accumulation-point layer rather than the stronger
-- full-sequence convergence layer of `Theorem_3_2_5`;
-- * part `(2)` keeps only the source accumulation-point data on the labeled theorem surface;
-- the required lower-level-set bookkeeping is pushed into a bridge theorem that derives
-- eventual membership in `lowerLevelSetOn D f A.x0` from openness of `D`, convergence to
-- `xStar ∈ D`, and the owner-level exact-line-search monotonicity lemma
-- `NewtonMethodWithLineSearch.objective_nonincreasing_step`;
-- * the stronger theorem `newtonSequence_tendsto_minimizer` from `Theorem_3_2_5` remains a
-- companion, not a replacement, because it adds the extra decrease assumption `(3.2.13)`;
-- * source/core/bridge triage for part `(2)`:
-- source-facing = accumulation points of a genuinely nonterminating damped Newton run together
-- with the source-level regularity assumptions on `D`,
-- core/canonical = `IsMinOn f D xStar`,
-- bridge/view = eventual sampled membership in `lowerLevelSetOn D f A.x0` derived from the
-- run and convergence data; any later result upgrading `IsMinOn f D xStar` to
-- `IsMinOn f Set.univ xStar` must be stated separately from this theorem.
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
variable {f : Point → ℝ} (A : NewtonMethodWithLineSearch n f)
theorem dampedNewton_finiteRun_hasTerminalStationaryPoint
(_hε : A.ε = 0)
(_hFinite : A.IsFiniteSequence) :
∃ k, A.IsTerminalIndex k ∧ IsStationaryPoint f (A k)
Theorem 3.2.5
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Theorem 3.2.5 (1): for a run A of Algorithm 3.2.3, if the Hessian lower bound holds on the lower level set determined by the actual initial point A.x0 and the source line-search decrease inequality (3.2.13) holds along the run, then the gradient norms along the Newton iterates tend to 0.
open Filter
open scoped Gradient
open scoped RealInnerProductSpace
open scoped Topology
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
-- Domain sampling:
-- * source-facing owner: `NewtonMethodWithLineSearch` from `Algorithm_3_2_3`
-- * source-facing lower-level-set Hessian hypothesis:
-- `HasLowerLevelHessianLowerBound D f A.x0 m` from `Theorem_1_3_19`
-- * core/canonical convex-analysis owners for the uniqueness conclusion:
-- `StrongConvexOn` / `StrictConvexOn`
-- * bridge already available upstream: Chapter 1 relates Hessian lower bounds on convex sets to
-- those canonical convexity owners.
-- * Chapter 2 already owns exact line search itself, so this file keeps only the additional
-- source decrease inequality `(3.2.13)` as a theorem hypothesis instead of a parallel run API.
variable {f : Point → ℝ} {D : Set Point} (A : NewtonMethodWithLineSearch n f)
theorem newtonSequence_gradient_tendsto_zero
(hD_open : IsOpen D)
(hD_convex : Convex ℝ D)
(hC2 : ContDiffOn ℝ 2 f D)
(hLevelHessian : ∃ m > 0, HasLowerLevelHessianLowerBound D f A.x0 m)
(hIterates : ∀ k : ℕ, A k ∈ D)
(hLineSearch :
∃ ηbar > 0, ∀ k : ℕ,
ηbar * (((-(⟪A.d k, A.g k⟫)) / ‖A.d k‖) ^ (2 : ℕ)) ≤
f (A k) - f (A (k + 1))) :
Tendsto (fun k : ℕ ↦ ‖∇ f (A k)‖) atTop (nhds (0 : ℝ))
Definition 3.2.extra.1
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Definition 3.2-extra-1 (1): if G represents the Hessian of f, the quadratic model at the current iterate x_k is q^(k) (s) = f(x_k) + (∇ f x_k)ᵀ s + (1 / 2) sᵀ (G x_k) s.
open scoped Gradient
-- Domain sampling:
-- * `HasFDerivAt (∇ f)` together with `Matrix.toEuclideanCLM` is the Chapter 3 canonical owner
-- for Hessian matrix data at a point.
-- * `NewtonMethod.linearSystem` and `IsNewtonMethodSequence.newtonEq` record Newton steps by
-- the linear system `(G k).mulVec (s k) = -g k` together with explicit invertibility.
-- * `Matrix.PosDef.isUnit` is the bridge from the source positivity hypothesis to the
-- invertibility needed by the theorems connecting the inverse-Hessian bridge to the Newton
-- linear system.
-- Source/core/bridge triage:
-- * source-facing: the quadratic model, Newton direction, and Newton update at one iterate.
-- * core/canonical: the direct Hessian condition `∀ x, HasFDerivAt (∇ f) ... x` and the
-- Newton linear system.
-- * bridge/view: the inverse-Hessian formulas; invertibility remains on theorems that prove
-- those formulas satisfy the Newton-system owner.
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "Hessian" => Matrix (Fin n) (Fin n) ℝ
def newtonQuadraticModel (f : Point → ℝ) (xk : Point) (G : Point → Hessian) (s : Point) : ℝ :=
f xk + inner ℝ (gradient f xk) s +
(1 / 2 : ℝ) * inner ℝ s (Matrix.toEuclideanLin (G xk) s)3.3 — Modified Newton’s Method
Algorithm 3.3.1
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Algorithm 3.3.1: the modified Newton method starts from an initial point x0 : ℝ^n for an objective f, records indexed iterates x k, explicit gradients g k, search directions d k, step sizes α k, and the stagewise Gill-Murray modified-Cholesky owners used at each Hessian. Lean records that g k is the gradient of f at x k; the associated ModifiedCholeskyFactorization at step k carries the symmetric Hessian matrix G k, the safeguard parameter δ k, the nonnegative diagonal correction E_k, the corrected matrix Ḡ_k = G_k + E_k, and the pivot-order factorization of Ḡ_k; the safeguard shift is 0 when that correction vanishes and otherwise equals min (b₁, b₂); Ḡ_k is positive definite; the corrected linear system Ḡ_k d_k = -g_k is solved; α k is an exact line-search step on the ray a ↦ f (x k + a • d k); and the next iterate satisfies x (k + 1) = x k + α k • d k.
open scoped Gradient
variable {n : ℕ}
structure ModifiedNewtonMethod (n : ℕ) (f : EuclideanSpace ℝ (Fin n) → ℝ) where
x0 : EuclideanSpace ℝ (Fin n)
x : ℕ → EuclideanSpace ℝ (Fin n)
g : ℕ → EuclideanSpace ℝ (Fin n)
modifiedCholesky : ℕ → ModifiedCholeskyFactorization n
ν : ℕ → ℝ
d : ℕ → EuclideanSpace ℝ (Fin n)
α : ℕ → ℝ
x_zero : x 0 = x0
hasGradientAt : ∀ k : ℕ, HasGradientAt f (g k) (x k)
hessian :
∀ k : ℕ,
HasFDerivAt (∇ f)
((Matrix.toEuclideanCLM :
Matrix (Fin n) (Fin n) ℝ ≃⋆ₐ[ℝ]
EuclideanSpace ℝ (Fin n) →L[ℝ] EuclideanSpace ℝ (Fin n))
((modifiedCholesky k).G))
(x k)
shift_eq_zero_of_correction_eq_zero :
∀ k : ℕ,
(modifiedCholesky k).correctionMatrix = 0 → ν k = 0
shift_eq_min_of_correction_ne_zero :
∀ k : ℕ,
(modifiedCholesky k).correctionMatrix ≠ 0 →
ν k = min
(modifiedCholesky k).shiftUpperBound1
(modifiedCholesky k).shiftUpperBound2
shift_eq_zero_of_posDef : ∀ k : ℕ, ((modifiedCholesky k).G).PosDef → ν k = 0
shift_pos_of_not_posDef : ∀ k : ℕ, ¬ ((modifiedCholesky k).G).PosDef → 0 < ν k
corrected_posDef : ∀ k : ℕ, ((modifiedCholesky k).correctedMatrix).PosDef
linearSystem :
∀ k : ℕ,
((modifiedCholesky k).correctedMatrix).mulVec (d k) = -g k
exactLineSearch : ∀ k : ℕ, IsExactLineSearchStepOnNonnegativeRay f (x k) (d k) (α k)
update : ∀ k : ℕ, x (k + 1) = x k + α k • d k
Algorithm 3.3.2
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Algorithm 3.3.2: the terminal outputs satisfy the modified Cholesky factorization identity for the cumulatively permuted corrected matrix P G Pᵀ + E = L D Lᵀ, with P encoded by perm, E = diagonal e, and D = diagonal d.
open scoped BigOperators
namespace ModifiedCholeskyFactorization
variable {n : Nat}
local notation "Hessian" => Matrix (Fin n) (Fin n) ℝ
theorem factorization (A : ModifiedCholeskyFactorization n) :
-- Route correction: the earlier arbitrary-stage public-entry lemmas were too strong for this
-- row-wise `L` implementation, so the remaining blocker is now concentrated in the final
-- owner-normal forms `reindexedInput_lowerEntry` and `reindexedInput_diagEntry`; the
-- `L D Lᵀ` side already matches the target entries via
-- `modifiedCholeskySystemMatrix_lowerEntry` / `modifiedCholeskySystemMatrix_diagEntry`.
A.permutedCorrectedMatrix = modifiedCholeskySystemMatrix A.L A.dExample 3.3.3
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Example 3.3.3 (1): the reported value of β² is 1.061.
open Matrix
local notation "Matrix3" => Matrix (Fin 3) (Fin 3) ℝ
def chapter03Example333ReportedBetaSq : ℝ :=
(1061 : ℝ) / 1000Theorem 3.3.4
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Theorem 3.3.4: if f is twice continuously differentiable on an open set D, the sublevel set D ∩ {x | f x ≤ f x0} is compact, and A is a modified Newton run in the source sense of Chapter 3, whose iterates stay in D, then ∇ f (A k) ⟶ 0. The Example 3.3.3 descent estimate used by the source proof is packaged inside the run owner instead of appearing as a separate hypothesis.
open scoped Gradient
open scoped Topology
open Filter Set
variable {n : ℕ}
local notation "E" => EuclideanSpace ℝ (Fin n)
-- `ModifiedNewtonMethod` is the source-facing Chapter 3 owner for the modified Newton iterates,
-- gradients, directions, step sizes, and corrected Hessian data. The source uses the
-- quantitative descent bridge recalled in Example 3.3.3 to fit the Chapter 2 exact-line-search
-- convergence theorem; because the current run owner does not record that bridge, this file
-- packages it into a theorem-local source-faithful owner for the labeled theorem rather than
-- exposing it as a separate public hypothesis.
theorem modifiedNewton_gradient_tendsto_zero
(f : E → ℝ)
(D : Set E)
(A : ModifiedNewtonMethodWithExample333DescentEstimate n f)
(hD_open : IsOpen D)
(h_contDiff : ContDiffOn ℝ 2 f D)
(h_compact : IsCompact (D ∩ {x | f x ≤ f A.x0}))
(h_mem : ∀ k, A k ∈ D) :
Tendsto (fun k ↦ ∇ f (A k)) atTop (𝓝 0)
3.4 — Finite-Difference Newton’s Method
Theorem 3.4.1
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Theorem 3.4.1 (1): for F : X → Y on real normed spaces with chosen bases e and u, if fderiv ℝ F is γ-Lipschitz on the open convex set D, then the j-th column of the forward finite-difference Jacobian error, read back in the codomain basis u, has norm at most ((γ : ℝ) / 2) * |h| whenever ‖e j‖ = 1.
open Set
open Matrix
open scoped BigOperators
universe u v
variable {n m : ℕ}
local notation "L1Point" => WithLp (1 : ENNReal) (Fin n → ℝ)
local notation "L1Value" => WithLp (1 : ENNReal) (Fin m → ℝ)
local notation "l1PointBasis" => PiLp.basisFun (1 : ENNReal) ℝ (Fin n)
local notation "l1ValueBasis" => PiLp.basisFun (1 : ENNReal) ℝ (Fin m)
theorem finiteDifferenceJacobianColumnError_le
{X : Type u} {Y : Type v}
[NormedAddCommGroup X] [NormedSpace ℝ X]
[NormedAddCommGroup Y] [NormedSpace ℝ Y]
(e : Module.Basis (Fin n) ℝ X)
(u : Module.Basis (Fin m) ℝ Y)
(D : Set X)
(F : X → Y)
(x : X)
(h : ℝ)
(γ : NNReal)
(j : Fin n)
(hD_open : IsOpen D)
(hD_convex : Convex ℝ D)
(hx : x ∈ D)
(hF : DifferentiableOn ℝ F D)
(hLip : LipschitzOnWith γ (fderiv ℝ F) D)
(hunit : ‖e j‖ = 1)
(hstep : x + h • e j ∈ D)
(hh : h ≠ 0) :
‖u.equivFun.symm
((finiteDifferenceJacobianMatrix e u F x h - jacobianMatrixAt e u F x).col j)‖ ≤
((γ : ℝ) / 2) * |h|
Theorem 3.4.2
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Theorem 3.4.2 (1): specialized to the canonical norm used in Chapter01 Theorem 1.2.23, if f is C² on an open convex set D, its Hessian is γ-Lipschitz on D, and the two shifted points x ± h • e_i lie in D, then the centered finite-difference quotient approximates the i-th gradient coordinate with error at most ((γ : ℝ) / 6) * h ^ 2.
open scoped Gradient
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "e" => EuclideanSpace.basisFun (Fin n) ℝ
theorem centeredDifferenceGradientApprox_component_error_bound
(D : Set Point) (f : Point → ℝ) (x : Point) (h : ℝ) (γ : NNReal)
(hD_open : IsOpen D) (hD_convex : Convex ℝ D) (hf : ContDiffOn ℝ 2 f D)
(hHessianLipschitz :
LipschitzOnWith γ (fun y ↦ iteratedFDeriv ℝ 2 f y) D)
(hh : h ≠ 0)
(i : Fin n)
(h_add : x + h • e i ∈ D)
(h_sub : x - h • e i ∈ D) :
Theorem 3.4.3
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Theorem 3.4.3 (1): under the Chapter03 Theorem 3.4.2 hypotheses, if h > 0, x + h • e_i ∈ D for every coordinate direction, and every mixed forward point x + h • e_i + h • e_j also lies in D, then the forward mixed-difference entry finiteDifferenceHessianMatrix f x h i j approximates the coordinate Hessian entry hessianMatrixAt f x i j with error at most ((5 : ℝ) / 3) * γ * h.
open scoped BigOperators
-- Domain sampling:
-- * source-facing owner here: the forward mixed-difference Hessian matrix on `ℝ^n`
-- * core/canonical owner already in the project: `hessianAt`
-- * bridge/view used here: the Euclidean matrix representation of `hessianAt`
-- via `Matrix.toEuclideanCLM`
-- * canonical standard basis owner reused from nearby Chapter 3 files: `EuclideanSpace.basisFun`
-- * Chapter 1 owners reused unchanged: `‖·‖₁`, `‖·‖∞`, `‖·‖_F`
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "Hessian" => Matrix (Fin n) (Fin n) ℝ
local notation "e" => EuclideanSpace.basisFun (Fin n) ℝ
variable (D : Set Point) (f : Point → ℝ) (x : Point) (h : ℝ) (γ : NNReal)
variable
(hD_open : IsOpen D)
(hD_convex : Convex ℝ D)
(hx : x ∈ D)
(hf : ContDiffOn ℝ 2 f D)
(h_hessian_lipschitz :
∀ y ∈ D,
‖iteratedFDeriv ℝ 2 f y - iteratedFDeriv ℝ 2 f x‖ ≤ (γ : ℝ) * ‖y - x‖)
(hh : 0 < h)
(h_forward_step_mem : ∀ i : Fin n, x + h • e i ∈ D)
theorem finiteDifferenceHessianMatrix_entry_error_bound
{n : ℕ}
(D : Set (EuclideanSpace ℝ (Fin n)))
(f : EuclideanSpace ℝ (Fin n) → ℝ)
(x : EuclideanSpace ℝ (Fin n))
(h : ℝ) (γ : NNReal)
(hD_open : IsOpen D)
(hD_convex : Convex ℝ D)
(hx : x ∈ D)
(hf : ContDiffOn ℝ 2 f D)
(h_hessian_lipschitz :
∀ y ∈ D,
‖iteratedFDeriv ℝ 2 f y - iteratedFDeriv ℝ 2 f x‖ ≤ (γ : ℝ) * ‖y - x‖)
(hh : 0 < h)
(h_forward_step_mem :
∀ i : Fin n, x + h • EuclideanSpace.basisFun (Fin n) ℝ i ∈ D)
(h_mixed_step_mem :
∀ i : Fin n, ∀ j : Fin n,
x + h • EuclideanSpace.basisFun (Fin n) ℝ i +
h • EuclideanSpace.basisFun (Fin n) ℝ j ∈ D)
(i j : Fin n) :
Theorem 3.4.4
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Theorem 3.4.4: if F : ℝⁿ → ℝⁿ is continuously differentiable on an open convex set D, Metric.ball xStar r ⊆ D, F xStar = 0, fderiv ℝ F xStar is invertible with ‖(fderiv ℝ F xStar).inverse‖ ≤ β, and fderiv ℝ F is γ-Lipschitz on Metric.ball xStar r, then there exist ε > 0 and h > 0 such that for every x0 ∈ Metric.ball xStar ε and every step sequence hSeq with 0 < |hSeq k| ≤ h, there exists a sequence x generated by (3.4.18)-(3.4.19) which is well defined on D, converges linearly to xStar, becomes superlinear when hSeq ⟶ 0, and becomes quadratic under (3.4.20) or (3.4.21).
open Filter
open scoped Topology
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "coordBasis" => OrthonormalBasis.toBasis (EuclideanSpace.basisFun (Fin n) ℝ)
theorem finiteDifferenceNewton_existsLocalConvergence
(F : Point → Point) (D : Set Point) (xStar : Point) (r β : ℝ) (γ : NNReal)
(hD_open : IsOpen D) (hD_convex : Convex ℝ D)
(hr : 0 < r) (hβ : 0 < β)
(h_ball : Metric.ball xStar r ⊆ D)
(h_contDiff : ContDiffOn ℝ 1 F D)
(h_root : F xStar = 0)
(h_invertible : (fderiv ℝ F xStar).IsInvertible)
(h_inverse_bound : ‖(fderiv ℝ F xStar).inverse‖ ≤ β)
(h_lipschitz : LipschitzOnWith γ (fun x ↦ fderiv ℝ F x) (Metric.ball xStar r)) :
∃ ε > 0, ∃ h > 0, ∀ x0 : Point, ‖x0 - xStar‖ < ε →
∀ hSeq : ℕ → ℝ, HasAdmissibleFiniteDifferenceSteps hSeq h →
∃ x : ℕ → Point, FiniteDifferenceNewtonLocalConvergence F D x hSeq x0 xStar
Definition 3.4.extra.1
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Definition 3.4-extra-1: the derivative HasDerivAt f f' x is equivalent to the convergence of the canonical finite-difference quotients dslope f x (x + h) to f' as h → 0.
open Filter
open scoped Topology
theorem hasDerivAt_iff_tendsto_dslope_add {f : ℝ → ℝ} {f' x : ℝ} :
HasDerivAt f f' x ↔ Tendsto (fun h ↦ dslope f x (x + h)) (𝓝 0) (𝓝 f')3.5 — Negative Curvature Direction Method
Definition 3.5.1
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Definition 3.5.1 (1): an indefinite point is a point where the Hessian has a negative quadratic direction. This keeps the source-facing owner at the quadratic-form level used by the textbook, while spectral hypotheses remain available through bridge lemmas below.
variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
-- Mathlib recall: use `gradient` and `fderiv` for the Hessian owner,
-- and `Module.End.HasEigenvalue` for the negative-eigenvalue condition.
def IsIndefinitePoint (f : E → ℝ) (x : E) : Prop :=
∃ d : E, hessianQuadraticAt f x d < 0
Algorithm 3.5.2
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Algorithm 3.5.2: with ψ j = dDiag j - eDiag j, choose an index t minimizing ψ; if 0 ≤ ψ t, stop, and otherwise return a concrete direction dk solving (Matrix.transpose Lk).mulVec dk = e_t, where e_t = negativeCurvatureUnitVector t.
structure NegativeCurvaturePivotStep {n : ℕ}
(Lk : Matrix (Fin n) (Fin n) ℝ) (dDiag eDiag : Fin n → ℝ) where
/-- Step 2 chooses the pivot index `t` minimizing `ψ`. -/
t : Fin n
/-- Step 2 chooses `t` so that `ψ t` is minimal among all indices. -/
minimal : negativeCurvaturePivotIsMinimal dDiag eDiag t
/-- Step 3 records whether the algorithm stops or returns a concrete direction. -/
outcome : NegativeCurvaturePivotOutcome Lk dDiag eDiag t
Theorem 3.5.3
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Theorem 3.5.3 (1): let Gk be the Hessian of f at x, let Gk + Matrix.diagonal eDiag = Lk * Matrix.diagonal dDiag * Lkᵀ, and let t be the selected pivot from Algorithm 3.5.2 with negative score negativeCurvaturePivotScores dDiag eDiag t < 0. If dk solves Lkᵀ dk = e_t and Lk is unit lower triangular, then dk is a negative curvature direction at x. This uses the Chapter 3 owner IsNegativeCurvatureDirectionAt directly rather than keeping a parallel quadratic-negativity wrapper theorem.
open Matrix
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "Hessian" => Matrix (Fin n) (Fin n) ℝ
-- Domain sampling pass:
-- * primary domain: negative-curvature directions produced from the LDL pivot data in
-- Algorithm 3.5.2 for a Euclidean Hessian matrix;
-- * sampled source/core owners:
-- `negativeCurvaturePivotScores` / `negativeCurvatureUnitVector` and the Step 3 direction
-- constructor from `Algorithm_3_5_2`,
-- `IsNegativeCurvatureDirectionAt` / `hessianQuadraticAt` from `Definition_3_5_1`,
-- `IsDescentDirectionAt` / `IsDescentDirectionAt.exists_localDecrease` from
-- `Chapter01/Definition_1_4_3`,
-- and `Matrix.IsUnitLowerTriangular` from `Matrix/UnitLowerTriangular`;
-- * owner abstraction chosen here: the algorithmic primitive data is owned by
-- the pivot score and solve equation, while the mathematical conclusions are owned by
-- `IsNegativeCurvatureDirectionAt` and `IsDescentDirectionAt`;
-- * primitive data vs. derived API: for part (1), the source-facing primitive inputs are just
-- the selected pivot `t`, the negativity of `negativeCurvaturePivotScores dDiag eDiag t`,
-- and the solve equation `Lkᵀ dk = e_t`; the negative-curvature and local-decrease
-- conclusions are derived API on top of those owners;
-- * bridge/view note: `Gk` remains only the Euclidean matrix realization of the Hessian via
-- `Matrix.toEuclideanCLM`, so this file does not introduce a second Hessian owner.
variable
{f : Point → ℝ} {x : Point}
{Gk Lk : Hessian} {dDiag eDiag : Fin n → ℝ}
local notation "Glin" =>
((Matrix.toEuclideanCLM : Hessian ≃⋆ₐ[ℝ] Point →L[ℝ] Point) Gk)
theorem negativeCurvaturePivotDirection
(t : Fin n)
(negative : negativeCurvaturePivotScores dDiag eDiag t < 0)
(dk : Point)
(solve_eq : Lk.transpose.mulVec dk = negativeCurvatureUnitVector t)
(hHessian : HasFDerivAt (gradient f) Glin x)
(hLk_unitLower : Lk.IsUnitLowerTriangular)
(hCorrection_nonneg : ∀ i : Fin n, 0 ≤ eDiag i)
(hFactorization : Gk + Matrix.diagonal eDiag = Lk * Matrix.diagonal dDiag * Lk.transpose) :
IsNegativeCurvatureDirectionAt f x dk
Algorithm 3.5.4
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Algorithm 3.5.4: a run of the negative-curvature direction method with modified Cholesky factorization, Algorithm 3.5.2 pivot steps, and line search on ℝ^n. The data x, g, G, L, dDiag, eDiag, pivotStep, d, and α record one execution of the algorithm. Lean uses the 0-based reindexing x 0 = x₀ for the book's initialization k := 1. For every active index k ≤ terminalIndex, Step 2 ties g k = gradient f (x k) and G k to the Hessian of f at x k; Step 3 records the diagonal correction Matrix.diagonal (eDiag k) with nonnegative entries and the factorization G k + Matrix.diagonal (eDiag k) = L k D k L kᵀ; and pivotStep k records the Algorithm 3.5.2 pivot choice and its stop/direction outcome for the same L k, dDiag k, and eDiag k. For every nonterminal index k, the search direction satisfies the Step 4 / Step 5 branching rule, Step 6 updates x (k + 1) = x k + α k • d k, and Step 7 strictly decreases the objective. At the terminal index terminalIndex, either Algorithm 3.5.2 returns the stop branch in the small-gradient case or the computed line-search step fails to decrease f after the terminal Step 6 update.
variable {n : ℕ}
local notation "Point" => NegativeCurvaturePoint n
local notation "Hessian" => Matrix (Fin n) (Fin n) ℝ
-- Semantic recall: `lean_leansearch` points to `Mathlib.Analysis.Matrix.LDL` for `LDLᵀ`
-- factorizations, `modifiedCholeskySystemMatrix` now lives with the Gill-Murray factorization
-- owner in Algorithm 3.3.2, and Chapter 3 already owns the pivot-search data in
-- `NegativeCurvaturePivotStep`. This item keeps the source-facing modified Cholesky and
-- Algorithm 3.5.2 data explicit, since the source algorithm records one concrete run rather than
-- an existence API.
structure NegativeCurvatureDirectionMethodRun (n : ℕ)
(f : NegativeCurvaturePoint n → ℝ) where
ε : ℝ
x0 : NegativeCurvaturePoint n
x : ℕ → NegativeCurvaturePoint n
g : ℕ → NegativeCurvaturePoint n
G : ℕ → Matrix (Fin n) (Fin n) ℝ
L : ℕ → Matrix (Fin n) (Fin n) ℝ
dDiag : ℕ → Fin n → ℝ
eDiag : ℕ → Fin n → ℝ
pivotStep : ∀ k : ℕ, NegativeCurvaturePivotStep (L k) (dDiag k) (eDiag k)
d : ℕ → NegativeCurvaturePoint n
α : ℕ → ℝ
terminalIndex : ℕ
x_zero : x 0 = x0
gradient_eq : ∀ k : ℕ, k ≤ terminalIndex → g k = gradient f (x k)
hessian :
∀ k : ℕ, k ≤ terminalIndex →
HasFDerivAt (gradient f)
(((Matrix.toEuclideanCLM :
Matrix (Fin n) (Fin n) ℝ ≃⋆ₐ[ℝ]
NegativeCurvaturePoint n →L[ℝ] NegativeCurvaturePoint n) (G k)))
(x k)
correction_nonneg :
∀ k : ℕ, k ≤ terminalIndex → ∀ i : Fin n, 0 ≤ eDiag k i
factorization :
∀ k : ℕ, k ≤ terminalIndex →
G k + Matrix.diagonal (eDiag k) = modifiedCholeskySystemMatrix (L k) (dDiag k)
iterateDirection :
∀ k : ℕ, k < terminalIndex →
NegativeCurvatureDirectionStep ε (g k) (L k) (dDiag k) (eDiag k) (pivotStep k) (d k)
update :
∀ k : ℕ, k < terminalIndex → x (k + 1) = x k + α k • d k
strictDecrease :
∀ k : ℕ, k < terminalIndex → f (x (k + 1)) < f (x k)
terminal :
negativeCurvatureTerminalSmallGradient
ε (g terminalIndex) (L terminalIndex) (dDiag terminalIndex) (eDiag terminalIndex)
(pivotStep terminalIndex) ∨
negativeCurvatureTerminalLineSearchFailure
f ε x g L dDiag eDiag pivotStep d α terminalIndex
Theorem 3.5.5
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Theorem 3.5.5: if f : ℝ^n → ℝ is twice continuously differentiable on the open set D, the starting point satisfies x₀ ∈ L(xBar), the level set L(xBar) is closed, and {x_k} is generated by Algorithm 3.5.4 with ε = 0, then every accumulation point of {x_k} is a stationary point of f.
open Filter
open scoped Topology
variable {n : ℕ}
-- Domain sampling pass:
-- * primary domain: source-facing infinite sequences generated by Algorithm 3.5.4 on `ℝⁿ`;
-- * sampled source/core owners: `negativeCurvatureLevelSet` from `Theorem_3_5_6` and the
-- concrete Step 4 / Step 5 data from `Algorithm_3_5_4`;
-- * owner abstraction chosen here: a Euclidean sequence owner that records exactly the
-- algorithmic data needed to say that `{x_k}` is generated by Algorithm 3.5.4 with `ε = 0`;
-- * source/core/bridge triage: the labeled theorems stay source-facing, with the textbook
-- bounded/closed/convex level-set hypotheses explicit in the theorem headers;
-- * primitive/derived split: primitive data are the algorithm-generated sequence and the source
-- level-set assumptions, while accumulation-point existence and stationarity remain theorem
-- conclusions.
variable {f : NegativeCurvaturePoint n → ℝ}
variable {D : Set (NegativeCurvaturePoint n)}
variable {xBar x₀ : NegativeCurvaturePoint n}
variable {x : ℕ → NegativeCurvaturePoint n}
theorem zeroToleranceNegativeCurvatureInfiniteRun_accumulationPoint_stationary
(hD_open : IsOpen D)
(hC2 : ContDiffOn ℝ 2 f D)
(hLevel_closed : IsClosed (negativeCurvatureLevelSet D f xBar))
(hAlgorithm : IsZeroToleranceNegativeCurvatureDirectionMethodSequence f D x₀ x)
(hx₀ : x₀ ∈ negativeCurvatureLevelSet D f xBar)
{xStar : NegativeCurvaturePoint n} {φ : ℕ → ℕ}
(hφ : StrictMono φ)
(hTendsto : Tendsto (x ∘ φ) atTop (nhds xStar)) :
IsStationaryPoint f xStar
Theorem 3.5.6
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Theorem 3.5.6: once the source two-case backtracking argument is carried out, the combined model term converges to 0; the two source conclusions then follow by squeezing the first- and second-order terms against this quantity.
open Filter
open scoped Topology
variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable (D : Set E) (f : E → ℝ) (x s d : ℕ → E) (backtrackingExponent : ℕ → ℕ)
(x₀ : E) (ρ γ : ℝ)
variable (hD_open : IsOpen D)
variable (hC2 : ContDiffOn ℝ 2 f D)
variable (hLevelSetCompact : IsCompact (negativeCurvatureLevelSet D f x₀))
variable (hx_mem : ∀ k, x k ∈ D)
variable (hs_bounded : Bornology.IsBounded (Set.range s))
variable (hd_bounded : Bornology.IsBounded (Set.range d))
variable (hLineSearch :
IsNegativeCurvatureLineSearchSequence f x s d backtrackingExponent x₀ ρ γ)
variable (hDescentPair : ∀ k, IsDescentPairAt f (x k) (s k) (d k))
lemma negativeCurvature_model_term_tendsto_zero
(hD_open : IsOpen D)
(hC2 : ContDiffOn ℝ 2 f D)
(hLevelSetCompact : IsCompact (negativeCurvatureLevelSet D f x₀))
(hx_mem : ∀ k, x k ∈ D)
(hs_bounded : Bornology.IsBounded (Set.range s))
(hd_bounded : Bornology.IsBounded (Set.range d))
(hLineSearch :
IsNegativeCurvatureLineSearchSequence f x s d backtrackingExponent x₀ ρ γ)
(hDescentPair : ∀ k, IsDescentPairAt f (x k) (s k) (d k)) :
Tendsto (fun k ↦ negativeCurvatureModelTerm
(f := f) (x := x) (s := s) (d := d) k) atTop (nhds 0)
Theorem 3.5.7
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Theorem 3.5.7: under the hypotheses above, the Hessian at an accumulation point x* is positive semidefinite, formalized by HasPositiveSemidefiniteHessianAt f xStar.
open Filter
open scoped Topology
-- Domain sampling pass:
-- * primary domain: accumulation-point analysis for negative-curvature line-search
-- sequences for Chapter 3 negative-curvature methods;
-- * sampled source/core owners:
-- `IsNegativeCurvatureLineSearchSequence` from `Theorem_3_5_6`,
-- `hessianAt` / `HasPositiveSemidefiniteHessianAt` from `Definition_3_5_1`,
-- and the Euclidean Hessian-matrix bridge `hessianMatrixAt` from `Theorem_3_4_3`;
-- * owner abstraction chosen here:
-- the labeled source-facing theorem keeps the common Theorem 3.5.6-style
-- sequence hypotheses together with the additional constants and inequalities
-- `(3.5.40)`-`(3.5.42)`; its three conclusion clauses use the
-- canonical owners `IsStationaryPoint`, `HasPositiveSemidefiniteHessianAt`, and
-- `Module.End.HasEigenvalue (hessianAt f xStar).toLinearMap 0`;
-- * primitive data on the source-facing side: the sequence data from Theorem 3.5.6; the
-- additional constants `c₁`, `c₂`, `c₃` and the source inequalities
-- `(3.5.40)`-`(3.5.42)` are kept explicit together with the sequence
-- `leastEigenvalueSeq` that records the most negative Hessian eigenvalue and the
-- normalized least-eigenvalue directions `d k`;
-- the positive-semidefinite and zero-eigenvalue clauses use the
-- finite-dimensional least-eigenvalue and matrix-positive-semidefinite
-- surfaces supplied by `hessianMatrixAt`, while the final zero-eigenvalue clause stays on
-- the intrinsic Hessian eigenvalue owner;
-- * bridge/view note: `hessianMatrixAt` is the existing project bridge from the intrinsic owner
-- `hessianAt` to the textbook Euclidean matrix surface, so no local spectral wrapper is kept.
variable {n : ℕ}
variable (D : Set (NegativeCurvaturePoint n)) (f : NegativeCurvaturePoint n → ℝ)
(x s d : ℕ → NegativeCurvaturePoint n)
(backtrackingExponent : ℕ → ℕ) (x₀ : NegativeCurvaturePoint n) (ρ γ : ℝ)
variable (hD : IsOpen D) (hC2 : ContDiffOn ℝ 2 f D)
variable (hLevelSetCompact : IsCompact (negativeCurvatureLevelSet D f x₀))
variable (hx_mem : ∀ k, x k ∈ D)
variable (hs_bounded : Bornology.IsBounded (Set.range s))
variable (hd_bounded : Bornology.IsBounded (Set.range d))
variable (hLineSearch :
IsNegativeCurvatureLineSearchSequence f x s d backtrackingExponent x₀ ρ γ)
variable (hDescentPair : ∀ k, IsDescentPairAt f (x k) (s k) (d k))
variable (c₁ c₂ c₃ : ℝ) (leastEigenvalueSeq : ℕ → ℝ)
variable (hc₁ : 0 < c₁) (hc₂ : 0 < c₂) (hc₃ : 0 < c₃)
variable (hStepNormLowerBound :
∀ k, c₃ * ‖gradient f (x k)‖ ≤ ‖s k‖)
variable (hLeastEigenvalue :
∀ k,
IsLeast
{μ : ℝ |
Module.End.HasEigenvalue (Matrix.toEuclideanLin (hessianMatrixAt f (x k))) μ}
(leastEigenvalueSeq k))
variable (hLeastEigenDirection :
∀ k, hessianAt f (x k) (d k) = leastEigenvalueSeq k • d k)
variable (hDirectionUnit : ∀ k, ‖d k‖ = 1)
variable (hCurvatureUpperBound :
∀ k, hessianQuadraticAt f (x k) (d k) ≤ c₂ * leastEigenvalueSeq k)
variable (hDescentLowerBound :
∀ k, c₁ * ‖s k‖ * ‖gradient f (x k)‖ ≤ -inner ℝ (s k) (gradient f (x k)))
include D f x s d backtrackingExponent x₀ ρ γ
hD hC2 hLevelSetCompact hx_mem hs_bounded hd_bounded hLineSearch hDescentPair
c₁ c₂ c₃ leastEigenvalueSeq hc₁ hc₂ hc₃ hStepNormLowerBound
hLeastEigenvalue hLeastEigenDirection hDirectionUnit
hCurvatureUpperBound hDescentLowerBound
variable {xStar : NegativeCurvaturePoint n} {φ : ℕ → ℕ}
variable (hφ : StrictMono φ) (hxStar : Tendsto (x ∘ φ) atTop (nhds xStar))
include hφ hxStar
theorem accumulationPoint_hasPositiveSemidefiniteHessianAt :
HasPositiveSemidefiniteHessianAt f xStar
Theorem 3.5.8
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Theorem 3.5.8 (1): formalized on a real inner product space E, assume f has two continuous derivatives on the open set D, and the level set {x ∈ D | f x ≤ f x₀} is compact. If a source-faithful run of the negative-curvature direction method satisfies the additional quantitative bounds (3.5.47) and (3.5.48), then s_k → 0.
open Filter
open scoped Topology
variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
-- Domain sampling pass:
-- * primary domain: smooth unconstrained optimization with negative-curvature backtracking
-- line search on a real Hilbert space;
-- * sampled owner declarations in this domain:
-- `negativeCurvatureLevelSet` and `IsNegativeCurvatureLineSearchSequence` from
-- `Theorem_3_5_6`,
-- and `IsDescentPairAt.inner_left_nonpos` / `IsDescentPairAt.hessianQuadratic_nonpos` from
-- `Definition_3_5_1`;
-- * owner abstraction used here: the canonical sequence owner from `Theorem_3_5_6`;
-- * primitive data added by Theorem 3.5.8: only the quantitative bounds `(3.5.47)` and
-- `(3.5.48)`;
-- * derived API: the two norm-convergence consequences `s_k → 0` and `d_k → 0`.
variable (D : Set E) (f : E → ℝ) (x s d : ℕ → E) (backtrackingExponent : ℕ → ℕ)
(x₀ : E) (ρ γ : ℝ)
variable (hD : IsOpen D) (hC2 : ContDiffOn ℝ 2 f D)
variable (hLevelSetCompact : IsCompact (negativeCurvatureLevelSet D f x₀))
variable (hx_mem : ∀ k, x k ∈ D)
variable (hs_bounded : Bornology.IsBounded (Set.range s))
variable (hd_bounded : Bornology.IsBounded (Set.range d))
variable (hLineSearch :
IsNegativeCurvatureLineSearchSequence f x s d backtrackingExponent x₀ ρ γ)
variable (hDescentPair : ∀ k, IsDescentPairAt f (x k) (s k) (d k))
include D f x s d backtrackingExponent x₀ ρ γ
hD hC2 hLevelSetCompact hx_mem hs_bounded hd_bounded hLineSearch hDescentPair
theorem negativeCurvatureDirectionMethod_s_tendsto_zero
(c₁ : ℝ)
(hc₁ : 0 < c₁)
(hDescentLowerBound :
∀ k, c₁ * ‖s k‖ ^ 2 ≤ -inner ℝ (s k) (gradient f (x k))) :
Tendsto s atTop (nhds 0)
Theorem 3.5.9
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Theorem 3.5.9 (1): in addition to the assumptions of Chapter03 Theorem 3.5.8, assume that f has only finitely many stationary points in the level set L(x₀). Then the entire sequence generated by the second-order Armijo steplength algorithm (3.5.45) and (3.5.46) converges to some xStar ∈ L(x₀).
open Filter
open scoped Topology
variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
-- Domain sampling pass:
-- * primary domain: global convergence of negative-curvature direction sequences on a real
-- Hilbert space;
-- * sampled source/core owners: `negativeCurvatureLevelSet` from `Theorem_3_5_6` and
-- `negativeCurvatureStationaryPointsInLevelSet` below, together with
-- `IsStationaryPoint` from `Chapter01.Definition_1_4_7`, and
-- `IsNegativeCurvatureLineSearchSequence` from `Theorem_3_5_6`;
-- * source-facing layer refined here: the primitive sequence data from Theorems 3.5.6 and
-- 3.5.8, plus the finite-stationary-set hypothesis.
variable (D : Set E) (f : E → ℝ) (x s d : ℕ → E) (backtrackingExponent : ℕ → ℕ)
(x₀ : E) (ρ γ c₁ c₂ : ℝ)
variable (hD : IsOpen D) (hC2 : ContDiffOn ℝ 2 f D)
variable (hLevelSetCompact : IsCompact (negativeCurvatureLevelSet D f x₀))
variable (hx_mem : ∀ k, x k ∈ D)
variable (hs_bounded : Bornology.IsBounded (Set.range s))
variable (hd_bounded : Bornology.IsBounded (Set.range d))
variable (hLineSearch :
IsNegativeCurvatureLineSearchSequence f x s d backtrackingExponent x₀ ρ γ)
variable (hDescentPair : ∀ k, IsDescentPairAt f (x k) (s k) (d k))
variable (hc₁ : 0 < c₁) (hc₂ : 0 < c₂)
variable (hDescentLowerBound :
∀ k, c₁ * ‖s k‖ ^ 2 ≤ -inner ℝ (s k) (gradient f (x k)))
variable (hCurvatureUpperBound :
∀ k, hessianQuadraticAt f (x k) (d k) ≤ -c₂ * ‖d k‖ ^ 2)
variable (hStationaryFinite :
Set.Finite (negativeCurvatureStationaryPointsInLevelSet D f x₀))
include D f x s d backtrackingExponent x₀ ρ γ c₁ c₂
hD hC2 hLevelSetCompact hx_mem hs_bounded hd_bounded hLineSearch hDescentPair
hc₁ hc₂ hDescentLowerBound hCurvatureUpperBound hStationaryFinite
theorem negativeCurvatureLineSearchMethod_tendsto_of_finiteStationaryPoints
:
∃ xStar : E, xStar ∈ negativeCurvatureLevelSet D f x₀ ∧
Tendsto x atTop (nhds xStar)
Theorem 3.5.10
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Theorem 3.5.10 (1): if the negative curvature direction iterates stay in a compact level set and satisfy the step conditions (3.5.50)-(3.5.52), then g_kᵀ s_k ⟶ 0.
open Filter
open scoped Topology
variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
-- This item reuses the Chapter 3 quadratic search-path owner and adds the
-- stagewise conditions `(3.5.50)`-`(3.5.52)` attached to that path.
theorem negativeCurvatureDirection_firstOrderPairing_tendsto_zero
{D : Set E} {f : E → ℝ} {x₀ : E} {x s d : ℕ → E} {α : ℕ → ℝ}
{ρ σ : ℝ}
(hD : IsOpen D)
(hC2 : ContDiffOn ℝ 2 f D)
(hLevelCompact : IsCompact {y : E | y ∈ D ∧ f y ≤ f x₀})
(hSeq : IsNegativeCurvatureDirectionSequenceOn f D x₀ x s d α ρ σ) :
Tendsto (fun k ↦ inner ℝ (s k) (gradient f (x k))) atTop (𝓝 0)
Theorem 3.5.11
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Theorem 3.5.11 (1): let f : ℝ^n → ℝ have twice continuous derivatives on the open set D, let x₀ ∈ D, and assume that the level set L(x₀) = {x ∈ D | f x ≤ f x₀} is compact. If f has only finitely many stationary points in L(x₀) and {x_k} is generated by the second-order step rule (3.5.50)-(3.5.52), then the whole sequence converges to some limit point x*.
open Filter
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
theorem secondOrderStepRule_tendsto_of_finiteStationaryPoints
{D : Set Point} {f : Point → ℝ} {x s d : ℕ → Point} {α : ℕ → ℝ} {x₀ : Point} {ρ σ : ℝ}
(hD : IsOpen D)
(hC2 : ContDiffOn ℝ 2 f D)
(hLevelCompact : IsCompact (negativeCurvatureLevelSet D f x₀))
(hStationaryFinite : Set.Finite (negativeCurvatureStationaryPointsInLevelSet D f x₀))
(hSeq : IsNegativeCurvatureDirectionSequenceOn f D x₀ x s d α ρ σ) :
∃ xStar : Point, xStar ∈ negativeCurvatureLevelSet D f x₀ ∧
Tendsto x atTop (nhds xStar)
Algorithm 3.5.extra.1
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
The source trial arc x_k(α) = x_k + α • s_k + α^2 • d_k used in Algorithm 3.5-extra-1.
variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
def negativeCurvatureArcTrialPoint (x s d : E) (α : ℝ) : E :=
x + α • s + (α ^ (2 : ℕ)) • d
Remark 3.5.extra.2
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
A source-facing encoding of the Bunch-Parlett requirement that D_k be block diagonal with contiguous diagonal blocks of size 1 or 2. The monotone block map records which indices belong to the same diagonal block after the omitted permutations have been fixed.
open scoped BigOperators
variable {n : ℕ}
local notation "Vec" => EuclideanSpace ℝ (Fin n)
local notation "Mat" => Matrix (Fin n) (Fin n) ℝ
-- Semantic recall: `lean_leansearch` surfaced spectral-decomposition and eigenvector-basis
-- APIs for symmetric operators. This remark stays at a source-facing matrix recipe layer,
-- because the textbook item records one concrete construction of `(s_k, d_k)` rather than
-- a canonical mathlib owner.
structure IsBunchParlettBlockDiagonal (D : Mat) where
blockCount : ℕ
blockOf : Fin n → Fin blockCount
blockOf_monotone : Monotone blockOf
block_card_eq_one_or_two :
∀ b : Fin blockCount,
(Finset.univ.filter fun i ↦ blockOf i = b).card = 1 ∨
(Finset.univ.filter fun i ↦ blockOf i = b).card = 2
zero_of_ne_block : ∀ ⦃i j : Fin n⦄, blockOf i ≠ blockOf j → D i j = 0
3.6 — Inexact Newton’s Method
Lemma 3.6.1
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Lemma 3.6.1 (1): if F is C¹ at xStar and fderiv 𝕜 F xStar is invertible, then the nearby derivatives fderiv 𝕜 F y remain invertible and their inverses are uniformly bounded in operator norm.
variable {𝕜 E : Type*}
variable [NontriviallyNormedField 𝕜]
variable [NormedAddCommGroup E] [NormedSpace 𝕜 E] [CompleteSpace E]
-- Source/core/bridge triage:
-- * source-facing: local inverse-derivative regularity near a regular point in Chapter 3.6
-- * core/canonical: `ContDiffAt 𝕜 1 F xStar` and `ContinuousLinearMap.IsInvertible`
-- * bridge/view: the nearby invertibility and local inverse-norm bound for `fderiv 𝕜 F`
--
-- Semantic recall: mathlib already owns the inverse-map regularity API via
-- `ContinuousLinearMap.IsInvertible.contDiffAt_map_inverse`, so this file keeps the Chapter 3.6
-- lemmas at that owner level instead of restating them through a neighborhood `ContDiffOn`
-- witness on a concrete Euclidean model.
theorem exists_isInvertible_fderiv_near
(F : E → E) (xStar : E)
(h_contDiff : ContDiffAt 𝕜 1 F xStar)
(h_invertible : (fderiv 𝕜 F xStar).IsInvertible) :
∃ δ > 0, ∃ ξ > 0, ∀ ⦃y : E⦄, ‖y - xStar‖ < δ →
(fderiv 𝕜 F y).IsInvertible ∧ ‖(fderiv 𝕜 F y).inverse‖ ≤ ξTheorem 3.6.2
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Theorem 3.6.2: if xStar is a regular zero of F : ℝⁿ → ℝⁿ in the sense of (A1)-(A3), and the forcing sequence ηSeq of an inexact Newton sequence x, s, r, ηSeq satisfies ηSeq k ≤ η < t < 1, then for some ε > 0, every initial iterate with ‖x 0 - xStar‖ ≤ ε generates a sequence converging to xStar, and the convergence is linear in the source norm y ↦ ‖fderiv ℝ F xStar y‖.
open Filter
variable {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E]
-- Semantic recall: the Chapter 3.6 algorithm file already owns the source-facing
-- `IsInexactNewtonSequence` predicate, so this theorem file reuses that owner and only
-- adds the regular-zero hypothesis and convergence packaging it needs.
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
theorem inexactNewton_converges_linearly
(F : Point → Point) (xStar : Point) (η t : ℝ)
(h_regular : IsRegularZero F xStar)
(hη_nonneg : 0 ≤ η)
(hη_lt_t : η < t)
(ht_lt_one : t < 1) :
∃ ε > 0, ∀ x s r : ℕ → Point, ∀ ηSeq : ℕ → ℝ,
‖x 0 - xStar‖ ≤ ε →
IsInexactNewtonSequence F x s r ηSeq →
(∀ k : ℕ, ηSeq k ≤ η) →
InexactNewtonLinearConvergence F xStar t xLemma 3.6.3
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Lemma 3.6.3: if xStar is a regular zero of F, so in particular fderiv ℝ F xStar is invertible, and β = ‖(fderiv ℝ F xStar).inverse‖, α = max (‖fderiv ℝ F xStar‖ + 1 / (2 * β)) (2 * β), then ‖F y‖ is bounded above and below by constant multiples of ‖y - xStar‖ for y sufficiently close to xStar. This is the generic real-normed-space bridge theorem; the source ℝⁿ statement is obtained by specialization.
open scoped Topology
open Filter
variable {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E]
-- Source/core/bridge triage:
-- * source-facing: the Chapter 3.6 owner `IsRegularZero`
-- * core/canonical: `ContinuousLinearMap.IsInvertible` and local inverse-function APIs
-- * bridge/view: this explicit two-sided norm comparison near a regular zero
theorem norm_image_bounds_near_root_of_invertible_fderiv
(F : E → E) (xStar : E)
(h_regular : IsRegularZero F xStar) :
let β : ℝ := ‖(fderiv ℝ F xStar).inverse‖
let α : ℝ := max (‖fderiv ℝ F xStar‖ + 1 / (2 * β)) (2 * β)
∃ δ > 0, ∀ ⦃y : E⦄, ‖y - xStar‖ < δ →
(1 / α) * ‖y - xStar‖ ≤ ‖F y‖ ∧ ‖F y‖ ≤ α * ‖y - xStar‖Theorem 3.6.4
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Theorem 3.6.4: for an inexact Newton sequence x at a regular zero xStar, if the forcing sequence is bounded by η < 1 and x ⟶ xStar, then the residual condition ‖r k‖ = o(‖F (x k)‖) is equivalent to Q-superlinear convergence of x to xStar, expressed by the canonical owners HasInexactNewtonForcingBound ηSeq η and HasSuperlinearConvergenceTo x xStar.
open Filter
variable {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E]
-- Domain sampling:
-- * `Theorem_3_6_2`: `IsRegularZero`
-- * `Algorithm_3_6_extra_2`: `IsInexactNewtonSequence`
-- * `Theorem_3_6_6`: `HasInexactNewtonForcingBound`
-- * `Theorem_3_4_4`: `HasSuperlinearConvergenceTo`
-- * `Mathlib.Analysis.Asymptotics.Lemmas`: `=o[atTop]`
--
-- Source/core/bridge triage:
-- * source-facing: the theorem's residual-vs-superlinear equivalence
-- * core/canonical: `IsRegularZero`, `IsInexactNewtonSequence`,
-- `HasInexactNewtonForcingBound`, `HasSuperlinearConvergenceTo`, and the
-- asymptotic `=o` owner
-- * bridge/view: under the ambient convergence hypothesis `hx`, the source-side
-- `Q`-superlinear rate is expressed by the canonical owner
-- `HasSuperlinearConvergenceTo x xStar`
theorem inexactNewton_residual_isLittleO_iff_qSuperlinear
(F : E → E) (xStar : E) (η : ℝ)
(h_regular : IsRegularZero F xStar)
(hη_lt_one : η < 1)
(x s r : ℕ → E) (ηSeq : ℕ → ℝ)
(h_inexact : IsInexactNewtonSequence F x s r ηSeq)
(hη_bound : HasInexactNewtonForcingBound ηSeq η)
(hx : Tendsto x atTop (nhds xStar)) :
((fun k ↦ ‖r k‖) =o[atTop] fun k ↦ ‖F (x k)‖) ↔
HasSuperlinearConvergenceTo x xStar
Corollary 3.6.5
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Corollary 3.6.5: under the assumptions of Theorem 3.6.4 for an inexact Newton sequence x converging to xStar, if the forcing sequence ηSeq tends to 0, then x converges to xStar Q-superlinearly.
open Filter Asymptotics
variable {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E]
-- Domain sampling:
-- * `Theorem_3_6_2`: `IsRegularZero`
-- * `Algorithm_3_6_extra_2`: `IsInexactNewtonSequence`
-- * `Theorem_3_6_6`: `HasInexactNewtonForcingBound`
-- * `Theorem_3_6_4`: `inexactNewton_residual_isLittleO_iff_qSuperlinear`
-- * `Mathlib.Analysis.Asymptotics.Lemmas`: `=o[atTop]`
--
-- Source/core/bridge triage:
-- * source-facing: the forcing-to-superlinear corollary
-- * core/canonical: `IsRegularZero`, `IsInexactNewtonSequence`,
-- `HasInexactNewtonForcingBound`, and the asymptotic `=o` owner
-- * bridge/view: reuse of the upstream Chapter 3.6 owners on the corollary surface
theorem inexactNewton_qSuperlinear_of_forcing_tendsto_zero
(F : E → E) (xStar : E) (η : ℝ)
(h_regular : IsRegularZero F xStar)
(hη_lt_one : η < 1)
(x s r : ℕ → E) (ηSeq : ℕ → ℝ)
(h_inexact : IsInexactNewtonSequence F x s r ηSeq)
(hη_bound : HasInexactNewtonForcingBound ηSeq η)
(hx : Tendsto x atTop (nhds xStar))
(hηSeq_tendsto_zero : Tendsto ηSeq atTop (nhds 0)) :
HasSuperlinearConvergenceTo x xStar
Theorem 3.6.6
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Theorem 3.6.6 (1): if (A1)-(A3) hold at the regular zero xStar, 0 ≤ ηSeq k ≤ η < 1, and the initial iterate is sufficiently near xStar, then the inexact Newton iterates converge to xStar and eventually satisfy the linear rate ‖x (k + 1) - xStar‖ ≤ c * ‖x k - xStar‖ for some 0 < c < 1.
open Filter
open scoped Topology
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
-- Semantic recall: the generic Chapter 3.6 owners `IsRegularZero` and
-- `IsInexactNewtonSequence` already live upstream on intrinsic normed-space declarations.
-- This file keeps the bounded-forcing and eventual-linear convergence owners intrinsic, then
-- specializes the labeled source theorem to `ℝⁿ`.
theorem inexactNewton_tendsto_root_and_eventually_linear_of_forcing_bounded
(F : Point → Point) (xStar : Point) (η : ℝ)
(h_regular : IsRegularZero F xStar)
(hη_lt_one : η < 1) :
∃ ε > 0, ∀ x s r : ℕ → Point, ∀ ηSeq : ℕ → ℝ,
‖x 0 - xStar‖ < ε →
IsInexactNewtonSequence F x s r ηSeq →
HasInexactNewtonForcingBound ηSeq η →
HasEventuallyLinearConvergenceTo x xStar
Theorem 3.6.7
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Theorem 3.6.7 (1): if ∇ f is continuously differentiable on an open neighborhood U of a local minimizer xStar, hessianQuadraticAt f xStar is positive definite, and x, s, r, and ηSeq form an inexact Newton sequence with 0 ≤ ηSeq k ≤ η < 1, then every sufficiently close initial iterate generates a sequence converging Q-linearly to xStar.
open Filter
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
-- Source/core/bridge triage:
-- * source-facing: the three textbook local-convergence consequences for the inexact Newton
-- method applied to `gradient f`
-- * core/canonical: `IsRegularZero`, `IsInexactNewtonSequence`, and the Chapter 3.6 convergence
-- theorems
-- * bridge/view: local minimizer plus Hessian positivity at `xStar` upgrades the gradient map to
-- a regular zero of the canonical Chapter 3.6 owner
--
-- Domain sampling:
-- * `Chapter03/Definition_3_5_1.lean`: `hessianAt`, `hessianQuadraticAt`
-- * `Chapter03/Algorithm_3_6_extra_2.lean`: `IsInexactNewtonSequence`
-- * `Chapter03/Theorem_3_6_2.lean`: `IsRegularZero`
-- * `Chapter03/Theorem_3_6_6.lean`: canonical local convergence theorems for inexact Newton
--
-- Primitive data: the source assumptions are a local minimizer `xStar`, an open neighborhood
-- `U` with `C¹` gradient regularity, and positive definiteness of the Hessian quadratic form at
-- `xStar`. The regular-zero package for `gradient f` is derived from those data, so it should not
-- stay as a parallel primitive surface in this file.
theorem inexactNewton_qLinearlyConvergesTo_of_contDiffGradient_posDef
(f : Point → ℝ) (xStar : Point) (U : Set Point)
(hMin : IsLocalMin f xStar)
(hxStar_mem : xStar ∈ U)
(hU_open : IsOpen U)
(hC1Grad : ContDiffOn ℝ 1 (gradient f) U)
(hPosDef : ∀ y : Point, y ≠ 0 → 0 < hessianQuadraticAt f xStar y)
(η : ℝ)
(hη_lt_one : η < 1) :
∃ ε > 0, ∀ x s r : ℕ → Point, ∀ ηSeq : ℕ → ℝ, ‖x 0 - xStar‖ < ε →
IsInexactNewtonSequence (gradient f) x s r ηSeq →
HasInexactNewtonForcingBound ηSeq η →
HasEventuallyLinearConvergenceTo x xStar
Assumption 3.6.extra.1
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Assumption 3.6-extra-1: the source-facing hypotheses (A1)-(A3) for the nonlinear equation F x = 0 are exactly the existence of a regular zero in the canonical Chapter 3.6 sense.
variable {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E]
variable (F : E → E)
theorem exists_regularZero_iff_exists_textbook_assumptions :
(∃ xStar : E, IsRegularZero F xStar) ↔
∃ xStar : E,
F xStar = 0 ∧
(∃ s ∈ nhds xStar, ContDiffOn ℝ 1 F s) ∧
(fderiv ℝ F xStar).IsInvertibleAlgorithm 3.6.extra.2
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter03 Algorithm 3.6-extra-2: sequences x k, s k, r k, and ηSeq k are generated by the inexact Newton method for F : E → E when F is Fréchet differentiable at each iterate x k, the inexact Newton equation fderiv ℝ F (x k) (s k) = -F (x k) + r k holds, the residual bound ‖r k‖ ≤ ηSeq k * ‖F (x k)‖ is satisfied, and the update is x (k + 1) = x k + s k.
open Filter Asymptotics
variable {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E]
-- Source/core/bridge triage:
-- * source-facing: `IsInexactNewtonSequence`
-- * core/canonical: `HasFDerivAt`, `fderiv`, and the ambient normed-space Newton equation
-- * bridge/view: accessor lemmas extracting the derivative, residual, and update data
--
-- Domain sampling:
-- * `Mathlib.Analysis.Calculus.FDeriv.Basic`: `HasFDerivAt.fderiv`
-- * `Chapter03/Theorem_3_2_2.lean`: `IsNewtonMethodSequence`
-- * `Chapter03/Algorithm_3_2_3.lean`: `NewtonMethodWithLineSearch`
--
-- The primitive Chapter 3.6 data are the four sequences `x`, `s`, `r`, and `ηSeq`. The
-- derivative, linear-system, residual-bound, and update conditions are logical constraints on
-- that data, so the source-facing owner is the sequence predicate rather than a wrapper
-- structure with duplicated fields.
def IsInexactNewtonSequence
(F : E → E) (x s r : ℕ → E) (ηSeq : ℕ → ℝ) : Prop :=
(∀ k : ℕ, HasFDerivAt F (fderiv ℝ F (x k)) (x k)) ∧
(∀ k : ℕ, fderiv ℝ F (x k) (s k) = -F (x k) + r k) ∧
(∀ k : ℕ, ‖r k‖ ≤ ηSeq k * ‖F (x k)‖) ∧
∀ k : ℕ, x (k + 1) = x k + s kSupporting modules
These source modules support the indexed items and are listed separately so the chapter inventory remains complete.
-
Theorem_3_1_5/Index.lean(Documentation) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
-
Theorem_3_1_5/KantorovichLocal.lean(Documentation) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
-
Theorem_3_2_2/ConvergenceRates.lean(Documentation) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.