§3, (3.5)–(3.8), pp. 6–7 — the prescribed data are generated by Newton's method
ProvedSlowConvergence.Newton.newton_step_conditionsnewton-methodp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1worst-case-complexity
Let and let , , , , and the model be the data (3.2)–(3.5) and (1.2) of the example. Then for every :
- with ;
- (3.6) ;
- (3.7) is positive definite: for all ;
- , so is the exact global minimizer of the quadratic model (1.2), i.e. the unit Newton step;
- (3.8) :
Together with (3.1) these identities say that, on any function matching the data at the iterates, Newton's method started at produces exactly the iterates , and every step decreases by exactly the model decrease.
Formalization Note The page writes "for all "; the verification is identical at and Newton's method starts there, so the statement is for all . Item 4 is stated in addition to (3.6): in two dimensions it is what "the quadratic model (1.2) is globally minimized exactly" means.
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, (3.5)–(3.8), pp. 6–7: the data (3.2)–(3.4) are
generated by Newton's method. For every `k ≥ 0` the step is `s_k = x_{k+1} − x_k = (µ_k, 1)ᵀ` with
`µ_k ∈ (0, 1]`, and
* (3.6) `g_kᵀ s_k + s_kᵀ H_k s_k = 0`,
* (3.7) `H_k` is positive definite,
* `H_k s_k = −g_k`, i.e. the quadratic model (1.2) is globally minimized exactly at `s_k`,
* (3.8) `m_k(x_k + s_k) = f_{k+1}`, the prescribed next function value.
Formalization Note: the page says "for all k ≥ 1"; the verification is identical at `k = 0` and the
algorithm starts there, so the statement is for all `k ≥ 0`. -/
theorem newton_step_conditions (τ : ℝ) (hτ0 : 0 < τ) (hτ1 : τ < 1) (k : ℕ) :
sk τ k = !₂[mu τ k, 1] ∧ 0 < mu τ k ∧ mu τ k ≤ 1 ∧
⟪gk τ k, sk τ k⟫ + ⟪Hk k (sk τ k), sk τ k⟫ = 0 ∧
(∀ v : EuclideanSpace ℝ (Fin 2), v ≠ 0 → 0 < ⟪Hk k v, v⟫) ∧
Hk k (sk τ k) = -gk τ k ∧
model τ k (xk τ k + sk τ k) = fk τ (k + 1) := 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, pp. 6–7, §3, (3.5)–(3.8)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.