Weak duality with a polyhedral constraint set
ProvedLinearOptimization.lp_general_weak_duality(Theorem 4.17, Weak duality — Bertsimas & Tsitsiklis, p. 184.) Consider the primal problem: minimize subject to , , where is the polyhedron , and define the dual objective (Eq. 4.7)
the dual problem is: maximize subject to .
If is primal feasible ( and ), and is dual feasible (), then
import Definitions.Def_LinearOptimization_LagrangeanDual
open Matrix
/-- **Bertsimas & Tsitsiklis, Theorem 4.17 (p. 184).** Weak duality for the general dual: if
`Ax ≥ b`, `x ∈ {y | Dy ≥ d}`, and `p ≥ 0`, then
`g(p) = inf_{y ∈ P} [c'y + p'(b − Ay)] ≤ c'x`. -/
theorem LinearOptimization.lp_general_weak_duality {m₁ m₂ n : ℕ}
(A : Matrix (Fin m₁) (Fin n) ℝ) (b : Fin m₁ → ℝ) (c : Fin n → ℝ)
(D : Matrix (Fin m₂) (Fin n) ℝ) (d : Fin m₂ → ℝ)
(x : Fin n → ℝ) (hxA : b ≤ A.mulVec x) (hxP : x ∈ polyhedron D d)
(p : Fin m₁ → ℝ) (hp : 0 ≤ p) :
lagrangeanObjective A b c (polyhedron D d) p ≤ ((c ⬝ᵥ x : ℝ) : EReal) := by
sorry
Read-back
What the Lean code literally says, in plain math · claude-fable-5
Fix real matrices () and (), vectors , , ; a point satisfying both (componentwise) and (membership in the polyhedron of ); and a multiplier with componentwise. The conclusion is the single inequality, in the extended reals,
i.e. the Lagrangean objective at , where the infimum runs over the whole polyhedron (no integrality — even though the ambient development defines an integer version, this statement uses the continuous set), is at most the primal objective value of the given feasible . Since itself lies in the infimum's index set and , this is the standard weak-duality inequality; the statement asserts exactly the displayed and nothing more.
Confirmed by the mission captain (proposal self-audit).