Theorem 2 (ii) — is a strictly feasible point of (HLP)
ProvedSelfDualLP.Complexity.theorem_2_iiinterior-point-methodslinear-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1self-dual-embedding
Let , , , and let , and be the starting triple from which (HLP) is built. Then (HLP) has the strictly feasible point
that is, this point lies in .
This is what lets the algorithm start at a known interior point without any big- parameter; under the choice (7) it is the initial iterate .
Preamble
import Mathlib import Definitions.Def_SelfDualLP_Complexity_HLP open Matrix
Formal statement
namespace SelfDualLP.Complexity
/-- Theorem 2 (ii) (p. 57). For any `x⁰ > 0`, `s⁰ > 0` and `y⁰`, (HLP) has the strictly
feasible point `(y, x, τ, θ, s, κ) = (y⁰, x⁰, 1, 1, s⁰, 1)`. -/
theorem theorem_2_ii {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ) (c : Fin n → ℝ)
(x0 : Fin n → ℝ) (y0 : Fin m → ℝ) (s0 : Fin n → ℝ)
(hx0 : ∀ j, 0 < x0 j) (hs0 : ∀ j, 0 < s0 j) :
HLPStrictlyFeasible A b c x0 y0 s0 ⟨y0, x0, 1, 1, s0, 1⟩ := 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. 57, Theorem 2 (ii)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.