Equation (9) — eᵀx + eᵀs + τ + κ − (n + 1)θ = n + 1 on F_h
ProvedSelfDualLP.Output.equation_9interior-point-methodslinear-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1self-dual-embedding
Work with (HLP) under the choice (7): , . Every feasible point satisfies the normalizing equation
It is the last equality constraint of (HLP), rewritten with the definitions of the slacks and . Since at every optimal solution, (9) normalizes the optimal solutions; in the proof of Theorem 8 it bounds from above.
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
/-- Equation (9) (p. 58): under the choice (7), every feasible point of (HLP) satisfies the
normalizing constraint `eᵀx + eᵀs + τ + κ − (n + 1)θ = n + 1`. -/
theorem equation_9 {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ) (c : Fin n → ℝ)
(z : HLPPoint m n) (hz : HLPFeasible7 A b c z) :
ones n ⬝ᵥ z.x + ones n ⬝ᵥ z.s + z.τ + z.κ - ((n : ℝ) + 1) * z.θ = (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. 58, equation (9); DOI 10.1287/moor.19.1.53
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.