Complementary slackness
ProvedLinearOptimization.lp_complementary_slacknesscomplementary-slacknessdualitylinear-programmingoptimality
(Theorem 4.5, complementary slackness) Let and be feasible solutions to the primal and the dual problem, respectively. The vectors and are optimal solutions for the two respective problems if and only if:
- for all , and
- for all .
Preamble
import Definitions.Def_LinearOptimization_DualLP open Matrix /-- **Bertsimas & Tsitsiklis, Theorem 4.5 (p. 151).** Complementary slackness: feasible `x` and `p` are simultaneously optimal iff `pᵢ(aᵢ'x − bᵢ) = 0` for every constraint `i` and `(cⱼ − p'Aⱼ)xⱼ = 0` for every variable `j`. -/
Formal statement
theorem LinearOptimization.lp_complementary_slackness {m n : ℕ} (P : GeneralFormLP m n)
(x : Fin n → ℝ) (hx : x ∈ generalFeasibleSet P)
(p : Fin m → ℝ) (hp : p ∈ generalFeasibleSet (dualLP P)) :
(IsLpOptimal P.c (generalFeasibleSet P) x ∧
IsLpDualOptimal P.b (generalFeasibleSet (dualLP P)) p) ↔
((∀ i, p i * (P.A i ⬝ᵥ x - P.b i) = 0) ∧
∀ j, (P.c j - p ⬝ᵥ (fun i => P.A i j)) * x j = 0) := by
sorry
Source
Bertsimas & Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997, Theorem 4.5, p. 151