Proof of Theorem 8 — every predictor–corrector iterate lies in N(2β), and θᵏ ≤ 1
ProvedSelfDualLP.Output.sequence_in_neighborhoodinterior-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 ,
The first part is the opening sentence of the proof of Theorem 8 ("the sequence generated by the predictor-corrector algorithm is in "). Both facts feed every inequality in Theorem 8: membership in gives , and gives the upper bound .
Formalization Note The second conjunct is not printed as a separate sentence; it is read from the step ratios on p. 62 ( for predictor steps, for corrector steps) together with , and it is the inequality used on p. 63.
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, first sentence (p. 63): every iterate of the predictor–corrector
algorithm lies in `𝒩(2β)`, `2β = 1/2`. The second conjunct, `θᵏ ≤ 1 = θ⁰`, is the monotonicity
of `θᵏ` given by the step ratios of p. 62 (`θᵏ⁺¹/θᵏ ≤ 1 − 8^{−1/4}/√(n+1)` on predictor steps,
`= 1` on corrector steps); the proof of Theorem 8 uses it in `κᵏ ≤ (n+1) + (n+1)θᵏ ≤ 2(n+1)`. -/
theorem sequence_in_neighborhood {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, Nbhd A b c (2 * beta) (z k) ∧ (z k).θ ≤ 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 (first sentence); p. 62, step ratios; DOI 10.1287/moor.19.1.53
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.