§5, p. 13 — and (5.4) gives (5.1):
ProvedSlowConvergence.ARC.gradient_formulalower-boundp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1worst-case-complexity
Let and . Then
and the prescribed gradients of (5.4) satisfy (5.1):
This is the rate that, through the iteration count, makes ARC need about iterations.
Formalization Note The paper says "for any "; the construction needs , which is assumed here as everywhere in the mission.
Preamble
import Mathlib import Definitions.Def_SlowConvergence_ARC_Data
Formal statement
namespace SlowConvergence.ARC
/-- Cartis, Gould & Toint, preprint 15 Oct 2009, §5, p. 13: "where now η = η(τ) def= ½(2/(3 − 2τ) − 2/3)
= 2τ/(9 − 6τ) > 0. Observe that (5.4) gives (5.1) by construction." For `0 < τ < 1`,
`η = 2τ/(9 − 6τ) > 0`, `2/3 + 2η = 2/(3 − 2τ)`, and the prescribed gradients `g_k` of (5.4) satisfy
(5.1): `|g_k| = (1/(k+1))^{2/(3−2τ)}` for all `k ≥ 0`. -/
theorem gradient_formula (τ : ℝ) (hτ0 : 0 < τ) (hτ1 : τ < 1) :
eta τ = 2 * τ / (9 - 6 * τ) ∧ 0 < eta τ ∧ 2 / 3 + 2 * eta τ = 2 / (3 - 2 * τ) ∧
∀ k : ℕ, |gk τ k| = (1 / ((k : ℝ) + 1)) ^ (2 / (3 - 2 * τ)) := 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, p. 13, §5, (5.1), (5.4) and η(τ)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.