Theorem 2.2 — at most successful iterations decrease the model by
ProvedAdaptiveCubic.Cauchy.theorem_2_2Consider a run of the ARC algorithm with parameters , , , and suppose for all . Let , and . Fix a horizon such that the model decreases on every iteration up to it,
and let be any set of successful iterations with
Then
Each such iteration lowers by at least , and never increases along the run, so the total available decrease caps their number. This is the generic counting step behind every complexity bound of the paper.
Formalization Note The paper assumes (2.6) on every iteration (p. 4) and sums over all of "with say as the largest index". Here the statement is posed for each finite horizon , with (2.6) assumed up to ; the infinite case follows by letting grow. The optimality measure and the set of (2.16)–(2.17) only restrict which are allowed; since is arbitrary, allowing every set of successful iterations is the same theorem.
import Mathlib import Definitions.Def_AdaptiveCubic_Cauchy_IsARCRun open scoped RealInnerProductSpace
namespace AdaptiveCubic.Cauchy
/-- Theorem 2.2, (2.19), p. 6 (Cartis, Gould & Toint, ARC Part II, preprint rev. 15 Sep 2009),
finite-horizon form. Let `f(x_k) ≥ f_low` for all `k`, `ϵ > 0`, `α > 0`, `p > 0`. Fix a horizon `j`
on which (2.6) `m_k(s_k) < f(x_k)` holds for every `k ≤ j`, and let `S_o` be any set of successful
iterations `k ≤ j` with (2.18) `f(x_k) − m_k(s_k) ≥ α ϵ^p` for `k ∈ S_o`. Then
`|S_o| ≤ ⌈κ_p ϵ^{−p}⌉` with `κ_p = (f(x_0) − f_low)/(η₁ α)`.
The paper assumes (2.6) on every iteration (p. 4, last paragraph); here it is assumed up to the
horizon, which is the "largest index `j_m`" of the page's proof. The optimality measure `F_k` and
`S^ϵ_F` of (2.16)–(2.17) only constrain which `S_o` are allowed; since `F_k ≥ 0` is arbitrary, the
statement for all successful `S_o` is the same theorem. -/
theorem theorem_2_2 {n : ℕ} (f : EuclideanSpace ℝ (Fin n) → ℝ) (γ₁ γ₂ η₁ η₂ : ℝ)
(x s : ℕ → EuclideanSpace ℝ (Fin n)) (σ : ℕ → ℝ)
(B : ℕ → EuclideanSpace ℝ (Fin n) →L[ℝ] EuclideanSpace ℝ (Fin n))
(hrun : IsARCRun f γ₁ γ₂ η₁ η₂ x s σ B)
(flow : ℝ) (hlow : ∀ k, flow ≤ f (x k))
(ε : ℝ) (hε : 0 < ε) (α p : ℝ) (hα : 0 < α) (hp : 0 < p) (j : ℕ)
(h26 : ∀ k ≤ j, model f (B k) (σ k) (x k) (s k) < f (x k))
(So : Finset ℕ)
(hSo : So ⊆ (Finset.range (j + 1)).filter (fun k => η₁ ≤ rho f (B k) (σ k) (x k) (s k)))
(h218 : ∀ k ∈ So, α * ε ^ p ≤ f (x k) - model f (B k) (σ k) (x k) (s k)) :
(So.card : ℤ) ≤ ⌈(f (x 0) - flow) / (η₁ * α) * ε ^ (-p)⌉ := by sorry
end AdaptiveCubic.Cauchy
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.