Theorem 1 — predictor-corrector termination in O(√n·t) iterations
ProvedAdaptiveStepIPM.PredCorr.theorem_1Let and let be a real precision parameter. Start Algorithm 1 at with . At every iteration whose gap is greater than , take the predictor step at to the greatest step whose entire prefix lies in , followed by one full corrector step at . Then for some iteration ,
Thus Algorithm 1 attains precision in the iteration scale stated in Theorem 1.
Formalization Note The explicit ceiling is the count yielded by the paper's contraction factor , with natural logarithm. The run relation uses an attained greatest predictor step. At inputs where no greatest step exists, such as , it has no successor; the statement keeps the report's range, although those runs cannot continue above the stopping threshold. No sign condition on is imposed: for the starting pair already satisfies and the bound is met at .
import Mathlib import Definitions.Def_AdaptiveStepIPM_PredCorr_Algorithm open Matrix
namespace AdaptiveStepIPM.PredCorr
/-- Theorem 1, printed p. 8, with the explicit count from its proof. -/
theorem theorem_1 {m n : ℕ} (hn : 1 ≤ n)
(A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ) (c : Fin n → ℝ)
(t : ℝ) (x s : ℕ → Fin n → ℝ)
(hinit : N2 A b c (1 / 4) (x 0) (s 0))
(hgap : x 0 ⬝ᵥ s 0 ≤ (2 : ℝ) ^ t)
(hrun : ∀ k : ℕ, (2 : ℝ) ^ (-t) < x k ⬝ᵥ s k →
Alg1Step A b c (x k) (s k) (x (k + 1)) (s (k + 1))) :
∃ k : ℕ,
k ≤ ⌈2 * Real.log 2 * (8 : ℝ) ^ (1 / 4 : ℝ) *
Real.sqrt (n : ℝ) * t⌉₊ ∧
x k ⬝ᵥ s k ≤ (2 : ℝ) ^ (-t) := by sorry
end AdaptiveStepIPM.PredCorr
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.