Proof of Theorem 6 — a predictor step from N(1/4) lands in N(1/2) and shrinks θ by 1 − 8^{−1/4}/√(n+1)
ProvedSelfDualLP.Output.predictor_stepinterior-point-methodslinear-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1predictor-correctorself-dual-embedding
Work with (HLP) under the choice (7). Let , let solve the linear system (11)–(12) at with , and let
(assumed to be attained). Then lies in and
This is the predictor half of the Mizuno–Todd–Ye analysis applied to (HLP). It guarantees that each predictor step keeps the iterate near the central path and reduces by a fixed factor.
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 6, predictor-step claim (p. 62), under (7). Let `zᵏ ∈ 𝒩(1/4)`, let `d`
solve (11)–(12) at `zᵏ` with `γ = 0`, and let `ᾱ = max {α : zᵏ + αd ∈ 𝒩(1/2)}` (13) (assumed
attained). Then `zᵏ⁺¹ = zᵏ + ᾱd ∈ 𝒩(1/2)` and
`θᵏ⁺¹/θᵏ = ((xᵏ⁺¹)ᵀsᵏ⁺¹ + τᵏ⁺¹κᵏ⁺¹)/((xᵏ)ᵀsᵏ + τᵏκᵏ) ≤ 1 − 8^{−1/4}/√(n + 1)`. -/
theorem predictor_step {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ)
(c : Fin n → ℝ) (z d : HLPPoint m n) (αbar : ℝ)
(hz : Nbhd A b c (1 / 4) z) (hd : IsPCDirection A b c z d 0)
(hα : IsGreatest {a : ℝ | Nbhd A b c (1 / 2) (z.move d a)} αbar) :
Nbhd A b c (1 / 2) (z.move d αbar) ∧
(z.move d αbar).θ / z.θ = gap (z.move d αbar) / gap z ∧
gap (z.move d αbar) / gap z ≤ 1 - (8 : ℝ) ^ (-(1 / 4 : ℝ)) / Real.sqrt ((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. 62, proof of Theorem 6 (predictor-step claim); DOI 10.1287/moor.19.1.53
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.