Theorem 2.1, (2.13) — unsuccessful iterations are bounded by successful ones
ProvedAdaptiveCubic.FirstOrder.theorem_2_1Consider a run of ARC (Algorithm 2.1) with parameters . For let and be the successful and the unsuccessful iterations up to (2.9). Let and suppose (2.10): for every very successful iteration . If satisfies for all , then
The weight is multiplied by at least on each unsuccessful iteration and by at least on each successful one, so an upper bound on caps the number of unsuccessful iterations in terms of the successful ones. This converts a bound on successful iterations into a bound on all iterations.
Formalization Note The page assumes (2.12), , only for . The proof bounds ((2.15)), and the printed statement is false for with iteration unsuccessful and (). The hypothesis is therefore posed for .
import Mathlib import Definitions.Def_AdaptiveCubic_Cauchy_IsARCRun open scoped RealInnerProductSpace
namespace AdaptiveCubic.FirstOrder
/-- 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 : AdaptiveCubic.Cauchy.IsARCRun f γ₁ γ₂ η₁ η₂ x s σ B)
(j : ℕ) (γ₃ : ℝ) (hγ₃ : 0 < γ₃) (hγ₃' : γ₃ ≤ 1)
(h210 : ∀ k ≤ j, η₂ < AdaptiveCubic.Cauchy.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 => AdaptiveCubic.Cauchy.rho f (B k) (σ k) (x k) (s k) < η₁)).card : ℤ) ≤
⌈-(Real.log γ₃ / Real.log γ₁) *
(((Finset.range (j + 1)).filter
(fun k => η₁ ≤ AdaptiveCubic.Cauchy.rho f (B k) (σ k) (x k) (s k))).card : ℝ) +
1 / Real.log γ₁ * Real.log (σbar / σ 0)⌉ := by sorry
end AdaptiveCubic.FirstOrder
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.