Theorem 22.8 — a strictly complementary solution of the self-dual embedding solves the LP or certifies infeasibility
ProvedVanderbeiLP.SelfDual.self_dual_embedding_solutionLet be a real matrix, , , and consider the primal problem (22.1) s.t. , , its dual (22.2) s.t. , , and the self-dual embedding (22.21)
Suppose that is a strictly complementary feasible solution of (22.21): for all , for all , and .
- If , then is optimal for the primal problem (22.1) and is optimal for its dual (22.2).
- If , then either or (possibly both), and
- (a) if , then the dual problem is infeasible;
- (b) if , then the primal problem is infeasible.
This is what makes the homogeneous self-dual method a complete algorithm for linear programming: a strictly complementary solution of one auxiliary problem, which always has feasible solutions, either yields a primal–dual optimal pair or proves that one of the two problems is infeasible.
Formalization Note The book's parenthetical "(hence, optimal)" in the hypothesis is not formalized: every feasible solution of (22.21) is optimal, its objective being . "Either … or" in (2) is the inclusive or, as the book's proof says. Division by is written as scalar multiplication by and only occurs under .
import Mathlib import Definitions.Def_VanderbeiLP_SelfDual_SelfDualEmbedding open Matrix
namespace VanderbeiLP.SelfDual
/-- Theorem 22.8 (Vanderbei, p. 334). Let `(x̄, ȳ, φ̄, z̄, w̄, ψ̄)` be a strictly complementary
feasible solution of the self-dual embedding (22.21) of the primal (22.1)
`max cᵀx, Ax ≤ b, x ≥ 0` and its dual (22.2) `min bᵀy, Aᵀy ≥ c, y ≥ 0`.
(1) If `φ̄ > 0`, then `x̄/φ̄` is optimal for (22.1) and `ȳ/φ̄` is optimal for (22.2).
(2) If `φ̄ = 0`, then `cᵀx̄ > 0` or `bᵀȳ < 0`; (a) if `cᵀx̄ > 0` the dual is infeasible;
(b) if `bᵀȳ < 0` the primal is infeasible. -/
theorem self_dual_embedding_solution {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ)
(b : Fin m → ℝ) (c : Fin n → ℝ)
(x : Fin n → ℝ) (y : Fin m → ℝ) (φ : ℝ) (z : Fin n → ℝ) (w : Fin m → ℝ) (ψ : ℝ)
(hfeas : EmbeddingFeasible A b c x y φ z w ψ)
(hsc : EmbeddingStrictlyComplementary x y φ z w ψ) :
(0 < φ → VanderbeiLP.StrictComp.PrimalOptimal A b c (φ⁻¹ • x) ∧ VanderbeiLP.StrictComp.DualOptimal A b c (φ⁻¹ • y)) ∧
(φ = 0 →
(0 < c ⬝ᵥ x ∨ b ⬝ᵥ y < 0) ∧
(0 < c ⬝ᵥ x → ¬ ∃ y' : Fin m → ℝ, DualFeasible A c y') ∧
(b ⬝ᵥ y < 0 → ¬ ∃ x' : Fin n → ℝ, PrimalFeasible A b x')) := by sorry
end VanderbeiLP.SelfDual
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.