Theorem 3 (ii) — if , the sign of or certifies infeasibility
ProvedSelfDualLP.Complexity.theorem_3_iidualitylinear-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) with . Then , which implies
i.e. at least one of and is strictly less than zero. Moreover
- if then (LD) is infeasible;
- if then (LP) is infeasible;
so if both are negative, both (LP) and (LD) are infeasible.
This is the infeasibility certificate the algorithm returns when the original pair has no optimal solution.
Preamble
import Mathlib import Definitions.Def_SelfDualLP_Complexity_LPData import Definitions.Def_SelfDualLP_Complexity_HLP open Matrix
Formal statement
namespace SelfDualLP.Complexity
/-- Theorem 3 (ii) (p. 58), under the choice (7). Let `(y*, x*, τ*, θ* = 0, s*, κ*)` be a
strictly self-complementary solution of (HLP) with `τ* = 0`. Then `κ* > 0`, hence
`cᵀx* − bᵀy* < 0`, i.e. at least one of `cᵀx*` and `−bᵀy*` is negative; if `cᵀx* < 0` then
(LD) is infeasible, if `−bᵀy* < 0` then (LP) is infeasible (so if both, both are). -/
theorem theorem_3_ii {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ) (c : Fin n → ℝ)
(z : HLPPoint m n) (hz : StrictlySelfComplementary7 A b c z) (hτ : z.τ = 0) :
0 < z.κ ∧ c ⬝ᵥ z.x - b ⬝ᵥ z.y < 0 ∧ (c ⬝ᵥ z.x < 0 ∨ -(b ⬝ᵥ z.y) < 0) ∧
(c ⬝ᵥ z.x < 0 → ¬ LDIsFeasible A c) ∧
(-(b ⬝ᵥ z.y) < 0 → ¬ LPIsFeasible A b c) := 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 (ii)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.