Theorem 3 (i) — (LP) has a solution iff τ* > 0, and then x*/τ* and (y*/τ*, s*/τ*) are optimal
ProvedSelfDualLP.Output.theorem_3_iinterior-point-methodslinear-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1self-dual-embedding
Work with (HLP) under the choice (7). Let be a strictly self-complementary solution of (HLP). Then
- (LP) has a solution (feasible and bounded) if and only if ;
- in this case is an optimal solution of (LP) and is an optimal solution of (LD).
This is how the self-dual embedding recovers optimal solutions of the original pair from a solution of (HLP).
Formalization Note "(LP) has a solution (feasible and bounded)" is formalized as "(LP) has an optimal solution". For linear programs the two are equivalent, but the equivalence is itself a theorem.
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
/-- 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) :
(SelfDualLP.Complexity.LPHasSolution A b c ↔ 0 < z.τ) ∧
(0 < z.τ → SelfDualLP.Complexity.LPOptimal A b c (z.τ⁻¹ • z.x) ∧ SelfDualLP.Complexity.LDOptimal A b c (z.τ⁻¹ • z.y) (z.τ⁻¹ • z.s)) := 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, Theorem 3 (i); DOI 10.1287/moor.19.1.53
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.