Complementary slackness
ProvedLinearOptimization.lp_complementary_slackness(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 .
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`. -/
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
Read-back
What the Lean code literally says, in plain math · claude-fable-5
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. Here “ is primal-optimal” means: is feasible for and for every feasible (a global minimizer of the primal objective), and “ is dual-optimal” means: is dual-feasible and for every dual-feasible (a global maximizer of ). The theorem asserts: for every general-form LP , every primal-feasible , and every dual-feasible , the following equivalence holds: [ is primal-optimal and is dual-optimal] iff [for every row , , and for every column , ] — i.e. vanishes whenever row is slack at , and vanishes whenever the -th dual constraint is slack. Both directions of the iff are asserted, under the standing feasibility of the given and .
Confirmed by the mission captain (proposal self-audit).