§3, p. 9 — the third derivative of along each step is at most 858
ProvedSlowConvergence.Newton.third_deriv_along_steplipschitz-hessianp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1worst-case-complexity
Let , and let , , and be as in the example. On the segment , the point () has first coordinate at offset in the interval of and second coordinate at offset in the interval of , so the third derivative of along the unit direction there is
For every and every ,
The paper deduces from this bound, by the mean-value theorem, that has Lipschitz continuous second derivatives on each segment of the piecewise linear path .
Formalization Note The page writes with one letter for both pieces; the argument of is the rescaled offset , with . The page bounds the signed quantity; the absolute value is stated here.
Preamble
import Mathlib import Definitions.Def_SlowConvergence_Newton_Data import Definitions.Def_SlowConvergence_Newton_Pieces open scoped RealInnerProductSpace
Formal statement
namespace SlowConvergence.Newton
/-- Cartis, Gould & Toint, preprint 15 Oct 2009, §3, p. 9: the third derivative of `f_2` along the
step, in the `k`-th interval, is at most `858`. At the point `x_k + t s_k`, `t ∈ [0, 1]`, of the
segment `[x_k, x_{k+1}]`, the first coordinate lies at offset `t µ_k` in the interval of `p_k` and the
second at offset `t` in the interval of `q_k`, so the third derivative of `f_2` in the unit direction
`s_k/‖s_k‖` is `(p_k'''(t µ_k) µ_k³ + q_k'''(t)) / ‖s_k‖³`. For all `k ≥ 0` and `t ∈ [0, 1]` its absolute
value is at most `858`.
Formalization Note: the page writes `p_k'''(t)(s_k)_1³` with one letter `t` for both pieces; the
argument of `p_k'''` is the rescaled offset `t µ_k` (with `(s_k)_1 = µ_k`). The page's chain bounds the
signed quantity; the absolute value is stated here, which is what Lipschitz continuity needs. -/
theorem third_deriv_along_step (τ : ℝ) (hτ0 : 0 < τ) (hτ1 : τ < 1) (k : ℕ) :
∀ t ∈ Set.Icc (0 : ℝ) 1,
|iteratedDeriv 3 (p τ k) (t * mu τ k) * mu τ k ^ 3 + iteratedDeriv 3 (q k) t|
/ ‖sk τ k‖ ^ 3 ≤ 858 := by sorry
end SlowConvergence.Newton
Source
Cartis, Gould & Toint, On the complexity of steepest descent, Newton's and regularized Newton's methods, preprint 15 Oct 2009, p. 9, §3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.