(15) — one iteration of Algorithm 2 gives
ProvedAdaptiveStepIPM.WideNbhd.eq_15interior-point-methodslinear-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , with , and let be or . If is obtained from by one iteration of Algorithm 2 with neighbourhood and parameter (a solution of (2), the largest step keeping on , and ), then with and ,
This is inequality (15): every iteration of Algorithm 2 reduces the duality gap by a factor , which is the per-iteration content of Theorem 2.
Formalization Note The paper writes (15) as along a run; it is stated here for a single iteration, which is how it is used. An iteration includes (the step is admissible).
Preamble
import Mathlib import Definitions.Def_AdaptiveStepIPM_WideNbhd_Neighborhoods import Definitions.Def_AdaptiveStepIPM_WideNbhd_Algorithm2
Formal statement
namespace AdaptiveStepIPM.WideNbhd
open Matrix
/-- Inequality (15) in the proof of Theorem 2 of Mizuno–Todd–Ye (p. 10): for `β, γ ∈ (0, 1)` with
`γ ≤ 2(1 − β)` and `N = N_∞(β)` or `N_∞⁻(β)`, one iteration `(x, s) ↦ (x⁺, s⁺)` of Algorithm 2
satisfies `μ⁺ ≤ (1 − 4βγ(1 − γ)/n) μ`, where `μ = xᵀs/n`, `μ⁺ = (x⁺)ᵀs⁺/n`. -/
theorem eq_15 {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 β) (x s x' s' : Fin n → ℝ)
(hstep : Alg2Step A N γ x s x' s') :
AdaptiveStepIPM.PredCorr.mu x' s' ≤ (1 - 4 * β * γ * (1 - γ) / n) * AdaptiveStepIPM.PredCorr.mu x s := by sorry
end AdaptiveStepIPM.WideNbhd
Source
Mizuno, Todd, Ye, On adaptive-step primal-dual interior-point algorithms for linear programming, Cornell ORIE Technical Report No. 944 (1990, rev. 1991), p. 10, proof of Theorem 2, (15)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.