Theorem 5 (ii) — directions in the null space satisfy
ProvedSelfDualLP.Complexity.theorem_5_iiinterior-point-methodslinear-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1self-dual-embedding
Work under the choice (7). Let lie in the null space of the constraint matrix of (HLP) after adding the surplus variables and , i.e.
Then
This orthogonality is what makes the predictor–corrector analysis of the standard primal–dual setting apply verbatim to (HLP).
Preamble
import Mathlib import Definitions.Def_SelfDualLP_Complexity_HLP import Definitions.Def_SelfDualLP_Complexity_Neighborhood open Matrix
Formal statement
namespace SelfDualLP.Complexity
/-- Theorem 5 (ii) (p. 59), under the choice (7). If `(d_y, d_x, d_τ, d_θ, d_s, d_κ)` lies in the
null space `Q` of the constraint matrix of (HLP) after adding surplus variables `s` and `κ`, then
`(d_x)ᵀd_s + d_τ d_κ = 0`. -/
theorem theorem_5_ii {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ) (c : Fin n → ℝ)
(d : HLPPoint m n) (hd : InQ7 A b c d) :
d.x ⬝ᵥ d.s + d.τ * d.κ = 0 := by sorry
end SelfDualLP.Complexity
Source
Ye, Todd, Mizuno, An O(√nL)-Iteration Homogeneous and Self-Dual Linear Programming Algorithm, Math. Oper. Res. 19(1) (1994), p. 59, Theorem 5 (ii)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.