Weak duality
ProvedLinearOptimization.lp_weak_duality(Theorem 4.3, weak duality) If is a feasible solution to the primal problem and is a feasible solution to the dual problem, then
import Definitions.Def_LinearOptimization_DualLP open Matrix /-- **Bertsimas & Tsitsiklis, Theorem 4.3 (p. 146).** Weak duality for the general-form primal/dual pair: any primal-feasible `x` and dual-feasible `p` satisfy `p'b ≤ c'x`. -/
theorem LinearOptimization.lp_weak_duality {m n : ℕ} (P : GeneralFormLP m n)
(x : Fin n → ℝ) (hx : x ∈ generalFeasibleSet P)
(p : Fin m → ℝ) (hp : p ∈ generalFeasibleSet (dualLP P)) :
p ⬝ᵥ P.b ≤ P.c ⬝ᵥ x := by
sorry
Read-back
What the Lean code literally says, in plain math · claude-fable-5
Weak duality. Here a general-form linear program with rows and variables ( arbitrary natural numbers) is a data record consisting of an real matrix , vectors and , a relation symbol from attached to each row , and a sign restriction from {nonnegative, nonpositive, free} attached to each variable . A point is feasible for iff for every row the number (dot product of row with ) stands in that row's relation to (, , or ), and every coordinate obeys its sign restriction (, , or unrestricted). The dual of is again a general-form LP: matrix ( rows, variables), right-hand side , cost vector ; its row carries relation / / according as variable of is nonnegative / nonpositive / free, and its variable is nonnegative / nonpositive / free according as row of has relation / / . Unwinding, is dual-feasible iff for every : when variable of is nonnegative, when nonpositive, when free (the row constraint of the dual literally reads ); and for every : when row of is a -row, when a -row, unrestricted when an -row. The theorem asserts: for every , every general-form LP as above, every feasible for , and every feasible for the dual of , one has (non-strict). Nothing is asserted about optimality, attainment, or the values of the programs; when either feasible set is empty the statement is vacuous for that side.
Confirmed by the mission captain (proposal self-audit).