Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§5, (5.5)–(5.8), pp. 13–14 — the data (5.2)–(5.4) may be generated by ARC, every iteration very successful

Proved
SlowConvergence.ARC.arc_step_conditions

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

cubic-regularizationlower-boundp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1worst-case-complexity

Let 0<τ<10<\tau<10<τ<1, and let xk,sk,f4,k,gk,Hk=0,σk=1x_k, s_k, f_{4,k}, g_k, H_k = 0, \sigma_k = 1xk​,sk​,f4,k​,gk​,Hk​=0,σk​=1 and the cubic model mkm_kmk​ be the data of the example. Then for every k≥0k\ge0k≥0:

  1. (5.5) gksk+skHksk+σk∣sk∣3=0g_k s_k + s_k H_k s_k + \sigma_k|s_k|^3 = 0gk​sk​+sk​Hk​sk​+σk​∣sk​∣3=0;
  2. (5.6) skHksk+σk∣sk∣3≥0s_k H_k s_k + \sigma_k|s_k|^3 \ge 0sk​Hk​sk​+σk​∣sk​∣3≥0;
  3. (5.7) σk>0\sigma_k>0σk​>0 and σk+1≤σk\sigma_{k+1}\le\sigma_kσk+1​≤σk​;
  4. mk(xk+sk)=f4,k−23(1k+1)1+3ηm_k(x_k+s_k) = f_{4,k} - \tfrac23\big(\tfrac1{k+1}\big)^{1+3\eta}mk​(xk​+sk​)=f4,k​−32​(k+11​)1+3η, and hence (5.8) f4,k+1=mk(xk+sk)f_{4,k+1} = m_k(x_k+s_k)f4,k+1​=mk​(xk​+sk​);
  5. the cubic model is globally minimized exactly at sks_ksk​:
mk(xk+sk)≤mk(xk+s)for every s∈R;m_k(x_k+s_k)\le m_k(x_k+s)\qquad\text{for every } s\in\mathbb R;mk​(xk​+sk​)≤mk​(xk​+s)for every s∈R;
  1. sk=xk+1−xk∈(0,1]s_k = x_{k+1}-x_k \in (0,1]sk​=xk+1​−xk​∈(0,1].

Items 4 and 5 say that the ratio of achieved to predicted decrease is 111 and the predicted decrease is positive, so every iteration of ARC on a function with these values, gradients and Hessians at the iterates is very successful, whatever the algorithm's parameters.

Formalization Note The paper writes "for all k≥1k\ge1k≥1"; the same computation holds at k=0k=0k=0, which the goal needs, so the statement is for all k≥0k\ge0k≥0. "Globally minimized exactly" (the paper's reading of (5.5)–(5.6) in one dimension) is stated directly as item 5. The model uses the prescribed values f4,kf_{4,k}f4,k​, gkg_kgk​, HkH_kHk​ in place of f4(xk)f_4(x_k)f4​(xk​), f4′(xk)f_4'(x_k)f4′​(xk​), f4′′(xk)f_4''(x_k)f4′′​(xk​), as condition (3.1) requires.

Preamble
import Mathlib
import Definitions.Def_SlowConvergence_ARC_Data
Formal statement
namespace SlowConvergence.ARC

/-- Cartis, Gould & Toint, preprint 15 Oct 2009, §5, (5.5)–(5.8), pp. 13–14: the sequences (5.2)–(5.4)
may be generated by the ARC algorithm, every iteration being very successful. For `0 < τ < 1` and every
`k ≥ 0`, with `m_k` the cubic model (1.3) built from the prescribed data:
* (5.5) `g_k s_k + s_k H_k s_k + σ_k |s_k|³ = 0`;
* (5.6) `s_k H_k s_k + σ_k |s_k|³ ≥ 0`;
* (5.7) `σ_k > 0` and `σ_{k+1} ≤ σ_k`;
* p. 14: `m_k(x_k + s_k) = f_{4,k} − ⅔(1/(k+1))^{1+3η}`, and (5.8) `f_{4,k+1} = m_k(x_k + s_k)`;
* the cubic model is globally minimized exactly by `s_k`: `m_k(x_k + s_k) ≤ m_k(x_k + s)` for every `s`;
* `s_k = x_{k+1} − x_k ∈ (0, 1]`. -/
theorem arc_step_conditions (τ : ℝ) (hτ0 : 0 < τ) (hτ1 : τ < 1) (k : ℕ) :
    gk τ k * sk τ k + sk τ k * Hk k * sk τ k + sigk k * |sk τ k| ^ 3 = 0 ∧
      0 ≤ sk τ k * Hk k * sk τ k + sigk k * |sk τ k| ^ 3 ∧
      0 < sigk k ∧ sigk (k + 1) ≤ sigk k ∧
      dataModel τ k (sk τ k) = fk τ k - 2 / 3 * (1 / ((k : ℝ) + 1)) ^ (1 + 3 * eta τ) ∧
      fk τ (k + 1) = dataModel τ k (sk τ k) ∧
      (∀ s : ℝ, dataModel τ k (sk τ k) ≤ dataModel τ k s) ∧
      sk τ k = xk τ (k + 1) - xk τ k ∧ 0 < sk τ k ∧ sk τ k ≤ 1 := by sorry

end SlowConvergence.ARC
Source
Cartis, Gould & Toint, On the complexity of steepest descent, Newton's and regularized Newton's methods, preprint 15 Oct 2009, pp. 13–14, §5, (5.5)–(5.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