Proposition 6.1.1 — weak duality for (P) and (D)
ProvedMatousekLP.Duality.weak_dualitydualitylinear-programmingp2o-batch-b23bp2o-gran-per-chapterp2o-plan-bookp2o-v1
Consider the linear programs (P) maximize subject to , , and (D) minimize subject to , , with a real matrix, , . Then:
- for every feasible solution of (P) and every feasible solution of (D),
- if (P) is unbounded, then (D) has no feasible solution;
- if (D) is unbounded from below, then (P) has no feasible solution.
Every dual feasible solution thus certifies an upper bound on the objective of (P). This is the half of the duality theorem that rules out three of the nine combinations of feasible-bounded, unbounded and infeasible for (P) and (D).
Formalization Note Feasibility, unboundedness of (P) (arbitrarily large objective values) and unboundedness of (D) (arbitrarily small objective values) are the notions of the definition module MatousekLP.Duality.PrimalDual.
Preamble
import Mathlib import Definitions.Def_MatousekLP_Duality_PrimalDual
Formal statement
namespace MatousekLP.Duality
open Matrix
/-- Matoušek & Gärtner, Proposition 6.1.1 (p. 83), weak duality for (P) and (D):
for every feasible `x` of (P) and feasible `y` of (D), `cᵀx ≤ bᵀy`; in particular, if (P) is
unbounded then (D) is infeasible, and if (D) is unbounded (from below) then (P) is infeasible. -/
theorem weak_duality {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ) (c : Fin n → ℝ) :
(∀ x y, IsPrimalFeasible A b x → IsDualFeasible A c y → c ⬝ᵥ x ≤ b ⬝ᵥ y) ∧
(PrimalUnbounded A b c → ¬ ∃ y, IsDualFeasible A c y) ∧
(DualUnbounded A b c → ¬ ∃ x, IsPrimalFeasible A b x) := by sorry
end MatousekLP.Duality
Source
Matoušek & Gärtner, Understanding and Using Linear Programming, Springer 2007, p. 83, Proposition 6.1.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.