Proof of Theorem 8 — κᵏ ≤ (n + 1) + (n + 1)θᵏ ≤ 2(n + 1) for all k
ProvedSelfDualLP.Output.kappa_upper_boundinterior-point-methodslinear-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1predictor-correctorself-dual-embedding
Work with (HLP) under the choice (7) and let , , be a predictor–corrector sequence. Then for every
This follows the paper's remark "from relation (9)"; it is the upper bound on behind the leftmost inequality of Theorem 8.
Preamble
import Mathlib import Definitions.Def_SelfDualLP_Complexity_LPData import Definitions.Def_SelfDualLP_Output_HLP import Definitions.Def_SelfDualLP_Output_Neighborhood import Definitions.Def_SelfDualLP_Output_PCSequence open Matrix
Formal statement
namespace SelfDualLP.Output
/-- Proof of Theorem 8 (p. 63): along every predictor–corrector sequence, relation (9) gives
`κᵏ ≤ (n + 1) + (n + 1)θᵏ ≤ 2(n + 1)` for all `k`. -/
theorem kappa_upper_bound {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ)
(c : Fin n → ℝ) (z : ℕ → HLPPoint m n) (hz : IsPCSequence A b c z) :
∀ k, (z k).κ ≤ ((n : ℝ) + 1) + ((n : ℝ) + 1) * (z k).θ ∧
((n : ℝ) + 1) + ((n : ℝ) + 1) * (z k).θ ≤ 2 * ((n : ℝ) + 1) := by sorry
end SelfDualLP.Output
Source
Ye, Todd, Mizuno, An O(√nL)-Iteration Homogeneous and Self-Dual Linear Programming Algorithm, Math. Oper. Res. 19(1) (1994), p. 63, proof of Theorem 8 (last sentence); DOI 10.1287/moor.19.1.53
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.