Weak duality with a polyhedral constraint set
ProvedLinearOptimization.lp_general_weak_dualitydualitylagrangean-dualitylinear-programmingweak-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
Preamble
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`. -/
Formal statement
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
Source
Bertsimas & Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997, Theorem 4.17, p. 184