Lemma 1.2 — uniform linearization error near
ProvedGlobalInexactNewton.Backtracking.lemma_1_2inexact-newtonnonlinear-equationsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a finite-dimensional real normed space and continuously differentiable. For every and there is such that
whenever and .
The derivative is taken at the base point , not at the centre . The lemma controls the error of the local linear model uniformly on a neighbourhood and is used to show that inexact Newton steps eventually give sufficient decrease.
Formalization Note is the open ball of radius about . Continuous differentiability is the paper's standing assumption (p. 395).
Preamble
import Mathlib import Definitions.Def_GlobalInexactNewton_Backtracking_Method open Filter Topology
Formal statement
namespace GlobalInexactNewton.Backtracking
/-- Eisenstat–Walker (1994), pp. 395–396, Lemma 1.2: for any `x` and `ε > 0` there is `δ > 0`
such that `‖F(z) - F(y) - F'(y)(z - y)‖ ≤ ε ‖z - y‖` whenever `y, z ∈ N_δ(x)`.
Standing assumption (p. 395): `F` is continuously differentiable. -/
theorem lemma_1_2 {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] [FiniteDimensional ℝ E]
(F : E → E) (hF : ContDiff ℝ 1 F) (x : E) (ε : ℝ) (hε : 0 < ε) :
∃ δ > 0, ∀ y ∈ Metric.ball x δ, ∀ z ∈ Metric.ball x δ,
‖F z - F y - fderiv ℝ F y (z - y)‖ ≤ ε * ‖z - y‖ := by sorry
end GlobalInexactNewton.Backtracking
Source
Eisenstat and Walker, Globally Convergent Inexact Newton Methods, SIAM J. Optim. 4(2) (1994), pp. 395–396, Lemma 1.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.