§2 (2.17), p. 5, at — on
ProvedSlowConvergence.Newton.p_second_deriv_boundhermite-interpolationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1worst-case-complexity
Let and let , and be as in the case of §2. Then for every and every
The last bound is of (2.17) with .
This is the uniform bound on the second derivative of the first-coordinate function , half of the statement that has a uniformly bounded Hessian (p. 8).
Formalization Note Only the outer inequalities of the printed chain (2.17) are stated. Its middle line, , is not true as printed (by (2.14) the left side equals ), but the bound itself holds.
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, §2, (2.17), p. 5, in the case `α_k = 1` used for
`f_{2,1} = f_1` (§3, p. 7): for all `k ≥ 0` and all `t ∈ [0, µ_k]`,
`|p_k''(t)| ≤ 1 + 150|φ_k| ≤ 1 + 150 max[1, ᾱ]/α̲`, and with `α_k ≡ 1` (so `α̲ = ᾱ = 1`) the last
bound is `151`.
Formalization Note: only the outer inequalities of the printed chain are stated; the middle line
`2|c_{2,k}| + 6|c_{3,k}|µ_k + 12|c_{4,k}|µ_k² + 20|c_{5,k}|µ_k³ ≤ 1 + 150|φ_k|` is not true as printed
(the left side equals `1 + 168|φ_k|`), but the end-to-end bound is. -/
theorem p_second_deriv_bound (τ : ℝ) (hτ0 : 0 < τ) (hτ1 : τ < 1) (k : ℕ) :
(∀ t ∈ Set.Icc (0 : ℝ) (mu τ k), |deriv (deriv (p τ k)) t| ≤ 1 + 150 * |phi τ k|) ∧
1 + 150 * |phi τ k| ≤ 151 := 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. 5, §2, (2.17); used at α_k = 1 in §3, pp. 7–8
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.