Theorem 3 (i) — (LP) has a solution iff , and then and are optimal
ProvedSelfDualLP.Complexity.theorem_3_idualitylinear-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1self-dual-embedding
Work under the choice (7). Let be a strictly self-complementary solution for (HLP). Then
- (LP) has a solution (an optimal solution) if and only if ;
- in this case is an optimal solution for (LP) and is an optimal solution for (LD).
This is how a solution of the artificial program solves the original pair.
Formalization Note "(LP) has a solution (feasible and bounded)" is read as "(LP) has an optimal solution" (for linear programs these are equivalent, but the equivalence is not assumed).
Preamble
import Mathlib import Definitions.Def_SelfDualLP_Complexity_LPData import Definitions.Def_SelfDualLP_Complexity_HLP open Matrix
Formal statement
namespace SelfDualLP.Complexity
/-- Theorem 3 (i) (p. 58), under the choice (7). Let `(y*, x*, τ*, θ* = 0, s*, κ*)` be a
strictly self-complementary solution of (HLP). Then (LP) has a solution (an optimal solution)
if and only if `τ* > 0`; in this case `x*/τ*` is optimal for (LP) and `(y*/τ*, s*/τ*)` is
optimal for (LD). -/
theorem theorem_3_i {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ) (c : Fin n → ℝ)
(z : HLPPoint m n) (hz : StrictlySelfComplementary7 A b c z) :
(LPHasSolution A b c ↔ 0 < z.τ) ∧
(0 < z.τ → LPOptimal A b c (z.τ⁻¹ • z.x) ∧ LDOptimal A b c (z.τ⁻¹ • z.y) (z.τ⁻¹ • z.s)) := 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. 58, Theorem 3 (i)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.