Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§3, (3.5)–(3.8), pp. 6–7 — the prescribed data are generated by Newton's method

Proved
SlowConvergence.Newton.newton_step_conditions

by mikedeng1 · Oct 8, 2026 · Mathlib 0df444a (Lean v4.33.1)

newton-methodp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1worst-case-complexity

Let 0<τ<10 < \tau < 10<τ<1 and let xkx_kxk​, fkf_kfk​, gkg_kgk​, HkH_kHk​, sks_ksk​ and the model mkm_kmk​ be the data (3.2)–(3.5) and (1.2) of the example. Then for every k≥0k \ge 0k≥0:

  1. sk=xk+1−xk=(μk,1)Ts_k = x_{k+1} - x_k = (\mu_k, 1)^Tsk​=xk+1​−xk​=(μk​,1)T with μk=(1/(k+1))12+η∈(0,1]\mu_k = (1/(k+1))^{\frac12+\eta} \in (0,1]μk​=(1/(k+1))21​+η∈(0,1];
  2. (3.6)   gkTsk+skTHksk=0\; g_k^T s_k + s_k^T H_k s_k = 0gkT​sk​+skT​Hk​sk​=0;
  3. (3.7)   Hk\; H_kHk​ is positive definite: vTHkv>0v^T H_k v > 0vTHk​v>0 for all v≠0v \neq 0v=0;
  4. Hksk=−gkH_k s_k = -g_kHk​sk​=−gk​, so sks_ksk​ is the exact global minimizer of the quadratic model (1.2), i.e. the unit Newton step;
  5. (3.8)   mk(xk+sk)=fk+1\; m_k(x_k + s_k) = f_{k+1}mk​(xk​+sk​)=fk+1​:
fk+gkTsk+12skTHksk=fk+1.f_k + g_k^T s_k + \tfrac12 s_k^T H_k s_k = f_{k+1}.fk​+gkT​sk​+21​skT​Hk​sk​=fk+1​.

Together with (3.1) these identities say that, on any function f2f_2f2​ matching the data at the iterates, Newton's method started at x0=0x_0 = 0x0​=0 produces exactly the iterates xkx_kxk​, and every step decreases f2f_2f2​ by exactly the model decrease.

Formalization Note The page writes "for all k≥1k \ge 1k≥1"; the verification is identical at k=0k = 0k=0 and Newton's method starts there, so the statement is for all k≥0k \ge 0k≥0. 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
  • Endorsed by Shuze Chen · Oct 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 8, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me