Theorem 2 — Algorithm 2 in or with reaches precision in steps
ProvedAdaptiveStepIPM.WideNbhd.theorem_2Consider the linear program (P) s.t. , , and its dual (D), with variables. Let and be constants with , and let be or .
Algorithm 2. Given with , set . While : compute from (2), compute the largest such that for all , set and .
Theorem. Every run of Algorithm 2 reaches for some
so the algorithm terminates in iterations.
This is the classical bound of Kojima, Mizuno and Yoshise, obtained for an adaptive-step method in the wide neighbourhoods, which with close to cover almost all strictly feasible pairs.
Formalization Note The paper states " iterations"; is the explicit count that its inequality (15), , gives: once . A run is any pair of sequences that starts as required and makes one Algorithm 2 iteration from every iterate with ; what happens after the stopping test is met is unconstrained. "The largest " is encoded as a greatest element, so a run exists only while such a maximum exists (for it never does, and the theorem holds trivially). No sign condition on is imposed: for the starting pair already satisfies and . The two neighbourhoods are handled by a hypothesis or .
import Mathlib import Definitions.Def_AdaptiveStepIPM_WideNbhd_Neighborhoods import Definitions.Def_AdaptiveStepIPM_WideNbhd_Algorithm2
namespace AdaptiveStepIPM.WideNbhd
open Matrix
/-- Theorem 2 of Mizuno–Todd–Ye (p. 10): let `β, γ ∈ (0, 1)` with `γ ≤ 2(1 − β)`. Algorithm 2 with
`N = N_∞(β)` or `N_∞⁻(β)`, started at `(x⁰, s⁰) ∈ N` with `(x⁰)ᵀs⁰ ≤ 2^t`, reaches
`(x^k)ᵀs^k ≤ 2^{−t}` within `K = ⌈ln 2 · n · t / (2βγ(1 − γ))⌉` iterations — the explicit count
behind the paper's `O(nt)`, from (15). A run is any sequence of pairs that starts as required
and makes an Algorithm 2 step from every iterate with `(x^k)ᵀs^k > 2^{−t}`. -/
theorem theorem_2 {n m : ℕ} (hn : 1 ≤ n) (A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ)
(c : Fin n → ℝ) (β γ : ℝ) (hβ0 : 0 < β) (hβ1 : β < 1) (hγ0 : 0 < γ) (hγ1 : γ < 1)
(hγβ : γ ≤ 2 * (1 - β)) (N : Set ((Fin n → ℝ) × (Fin n → ℝ)))
(hN : N = Ninf A b c β ∨ N = NinfMinus A b c β) (t : ℝ) (x s : ℕ → Fin n → ℝ)
(h0 : (x 0, s 0) ∈ N) (h0t : x 0 ⬝ᵥ s 0 ≤ (2 : ℝ) ^ t)
(hrun : ∀ k, (2 : ℝ) ^ (-t) < x k ⬝ᵥ s k → Alg2Step A N γ (x k) (s k) (x (k + 1)) (s (k + 1))) :
∃ k ≤ ⌈Real.log 2 * n * t / (2 * β * γ * (1 - γ))⌉₊, x k ⬝ᵥ s k ≤ (2 : ℝ) ^ (-t) := by sorry
end AdaptiveStepIPM.WideNbhd
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.