Theorem 2.1 (2.13) — unsuccessful iterations are bounded by successful ones and
ProvedAdaptiveCubic.Cauchy.theorem_2_1Consider a run of the ARC algorithm with parameters , , . Fix and let and be the successful and unsuccessful iterations among . Assume that for some , every very successful iteration has
and let satisfy for all . Then
Every unsuccessful iteration multiplies by at least and every successful one by at least , so an upper bound on caps the number of unsuccessful iterations. This is the step that converts a count of successful iterations into a count of all iterations.
Formalization Note The paper assumes (2.12), , only for . Its proof bounds (the factor of iteration acts on ), and as printed the statement fails for with iteration unsuccessful and (). The hypothesis is therefore taken for ; every application in the paper supplies this.
import Mathlib import Definitions.Def_AdaptiveCubic_Cauchy_IsARCRun open scoped RealInnerProductSpace
namespace AdaptiveCubic.Cauchy
/-- Theorem 2.1, (2.13), p. 5 (Cartis, Gould & Toint, ARC Part II, preprint rev. 15 Sep 2009).
For any fixed `j ≥ 0`, with `S_j` the successful and `U_j` the unsuccessful iterations `k ≤ j`
(2.9), assume (2.10) (`σ_{k+1} ≥ γ₃ σ_k` on every very successful `k ≤ j`, `γ₃ ∈ (0, 1]`) and let
`σ̄ > 0` bound `σ_k`. Then `|U_j| ≤ ⌈−(log γ₃ / log γ₁)|S_j| + (1/log γ₁) log(σ̄/σ₀)⌉`.
Correction: the page assumes (2.12) `σ_k ≤ σ̄` only for `k ≤ j`; the proof uses `σ_{j+1} ≤ σ̄`
((2.15) bounds `σ_{j+1}`), and the printed statement fails for `j = 0`, iteration `0` unsuccessful,
`σ̄ = σ₀`. The hypothesis is posed for `k ≤ j + 1`. -/
theorem theorem_2_1 {n : ℕ} (f : EuclideanSpace ℝ (Fin n) → ℝ) (γ₁ γ₂ η₁ η₂ : ℝ)
(x s : ℕ → EuclideanSpace ℝ (Fin n)) (σ : ℕ → ℝ)
(B : ℕ → EuclideanSpace ℝ (Fin n) →L[ℝ] EuclideanSpace ℝ (Fin n))
(hrun : IsARCRun f γ₁ γ₂ η₁ η₂ x s σ B)
(j : ℕ) (γ₃ : ℝ) (hγ₃ : 0 < γ₃) (hγ₃' : γ₃ ≤ 1)
(h210 : ∀ k ≤ j, η₂ < rho f (B k) (σ k) (x k) (s k) → γ₃ * σ k ≤ σ (k + 1))
(σbar : ℝ) (hσbar : 0 < σbar) (h212 : ∀ k ≤ j + 1, σ k ≤ σbar) :
(((Finset.range (j + 1)).filter
(fun k => rho f (B k) (σ k) (x k) (s k) < η₁)).card : ℤ) ≤
⌈-(Real.log γ₃ / Real.log γ₁) *
(((Finset.range (j + 1)).filter
(fun k => η₁ ≤ rho f (B k) (σ k) (x k) (s k))).card : ℝ) +
1 / Real.log γ₁ * Real.log (σbar / σ 0)⌉ := by sorry
end AdaptiveCubic.Cauchy
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.