Proof of Theorem 2 — , hence
ProvedAdaptiveStepIPM.WideNbhd.theta2_lower_boundinterior-point-methodslinear-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , with , let with , let solve (2) at with parameter , and let be the scaled vectors (6). Then
where and are the step bounds of Lemma 5.
Since , this covers every iterate of Algorithm 2 with either neighbourhood, and gives a step length of order .
Formalization Note The paper writes this in the proof of Theorem 2 without a condition on . The bound needs , which holds for because , but can fail for (e.g. , ). For Algorithm 2 makes no iteration at all (the largest step does not exist), so the hypothesis loses nothing for Theorem 2. A zero norm makes the corresponding bound , as in Lemma 5.
Preamble
import Mathlib import Definitions.Def_AdaptiveStepIPM_WideNbhd_Neighborhoods import Definitions.Def_AdaptiveStepIPM_WideNbhd_Algorithm2
Formal statement
namespace AdaptiveStepIPM.WideNbhd
open Matrix
/-- Proof of Theorem 2 of Mizuno–Todd–Ye (p. 10): for `β, γ ∈ (0, 1)` with `γ ≤ 2(1 − β)`,
`(x, s) ∈ N_∞⁻(β)` and a solution `d` of (2) at `(x, s)` with `γ`,
`‖AdaptiveStepIPM.PredCorr.Pq‖⁻_∞ ≤ ‖AdaptiveStepIPM.PredCorr.Pq‖_∞ ≤ ‖r‖²/4 ≤ nμ/4`, hence `θ₂⁻ ≥ θ₂ ≥ 4βγ/n`. The last step needs `n ≥ 2`. -/
theorem theta2_lower_bound {n m : ℕ} (hn : 2 ≤ 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 - β)) (x s : Fin n → ℝ) (hN : (x, s) ∈ NinfMinus A b c β)
(dx : Fin n → ℝ) (dy : Fin m → ℝ) (ds : Fin n → ℝ) (hd : IsDirection A x s γ dx dy ds) :
normInfNeg (AdaptiveStepIPM.PredCorr.Pq x s dx ds) ≤ normInf (AdaptiveStepIPM.PredCorr.Pq x s dx ds) ∧
normInf (AdaptiveStepIPM.PredCorr.Pq x s dx ds) ≤ norm2 (rvec γ x s) ^ 2 / 4 ∧
norm2 (rvec γ x s) ^ 2 / 4 ≤ (n : ℝ) * AdaptiveStepIPM.PredCorr.mu x s / 4 ∧
stepBound β γ (AdaptiveStepIPM.PredCorr.mu x s) (normInf (AdaptiveStepIPM.PredCorr.Pq x s dx ds)) ≤
stepBound β γ (AdaptiveStepIPM.PredCorr.mu x s) (normInfNeg (AdaptiveStepIPM.PredCorr.Pq x s dx ds)) ∧
4 * β * γ / n ≤ stepBound β γ (AdaptiveStepIPM.PredCorr.mu x s) (normInf (AdaptiveStepIPM.PredCorr.Pq x s dx ds)) := 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
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.