Corollary 4: positive κ at an HLP optimum detects infeasibility
ProvedSelfDualLP.Regularity.corollary_4interior-point-methodslinear-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1self-dual-embedding
Use the paper's choice and . Let be any optimal solution of (HLP). If , then
The disjunction is inclusive. Theorem 2(iv) supplies at an optimal solution; it is not an additional assumption here.
This result distinguishes certificates of infeasibility from the case in which both original programs have feasible points.
Preamble
import Definitions.Def_SelfDualLP_Regularity_HLP
Formal statement
namespace SelfDualLP.Regularity
/-- Ye--Todd--Mizuno (1994), Corollary 4, p. 59. -/
theorem corollary_4 {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ)
(b : Fin m → ℝ) (c : Fin n → ℝ) (w : HLPPoint m n)
(hw : IsSelfComplementary A b c w) (hκ : 0 < w.κ) :
(¬ ∃ x, PrimalFeasible A b c x) ∨
(¬ ∃ y, DualFeasible A c y) := by sorry
end SelfDualLP.Regularity
Source
Ye, Todd, Mizuno, An O(√nL)-Iteration Homogeneous and Self-Dual Linear Programming Algorithm, Math. Oper. Res. 19(1) (1994), p. 59, Corollary 4; DOI 10.1287/moor.19.1.53
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.