Dual optimal solutions are exactly the subgradients of the optimal cost function
ProvedLinearOptimization.lp_dual_optimal_iff_subgradient(Theorem 5.2, p. 216 — GOAL) Suppose that the linear programming problem of minimizing subject to and is feasible and that the optimal cost is finite.
Then, a vector is an optimal solution to the dual problem if and only if it is a subgradient of the optimal cost function at the point .
import Mathlib.LinearAlgebra.LinearIndependent.Defs import Definitions.Def_LinearOptimization_OptimalCostFunction import Definitions.Def_LinearOptimization_Subgradient open Matrix /-- **Bertsimas & Tsitsiklis, Theorem 5.2 (p. 216).** For a standard form problem feasible at `b*` with finite optimal cost (rows of `A` linearly independent), `p` is an optimal solution of the dual `max p'b*, p'A ≤ c'` if and only if `p` is a subgradient of the optimal cost function `F` at `b*` relative to the set `S` of feasible right-hand sides. -/
theorem LinearOptimization.lp_dual_optimal_iff_subgradient {m n : ℕ}
(A : Matrix (Fin m) (Fin n) ℝ) (c : Fin n → ℝ) (bstar : Fin m → ℝ)
(F : (Fin m → ℝ) → ℝ) (p : Fin m → ℝ)
(hrank : LinearIndependent ℝ (fun i => A i))
(hfeas : (stdPolyhedron A bstar).Nonempty)
(hfin : lpOptimalCostRhs A c bstar ≠ ⊥)
(hF : ∀ b ∈ feasibleRhsSet A, ((F b : ℝ) : EReal) = lpOptimalCostRhs A c b) :
IsLpDualOptimal bstar (dualFeasibleStd A c) p ↔
IsSubgradientOn F (feasibleRhsSet A) p bstar := by
sorry
Read-back
What the Lean code literally says, in plain math · claude-fable-5
Data: , an real matrix , cost , a point , a function , and . Hypotheses: (a) the rows of are linearly independent; (b) is nonempty; (c) in the extended reals (with (b) this makes the value at a finite real); (d) for every in , the real equals (as an extended real) — forcing that value to be finite on all of , with arbitrary off . Conclusion, an equivalence: [ maximizes over the dual feasible set, i.e. componentwise and for every with ] iff [ and for every , i.e. is a subgradient of on at in the bundle's sense].
Confirmed by the mission captain (proposal self-audit).