Concavity of the optimal cost in the cost vector
ProvedLinearOptimization.lp_optimal_cost_concave_in_cost(Theorem 5.3, p. 217) Consider a feasible linear programming problem in standard form.
- (a) The set of all for which the optimal cost is finite, is convex.
- (b) The optimal cost is a concave function of on the set .
- (c) If for some value of the primal problem has a unique optimal solution , then is linear in the vicinity of and its gradient is equal to .
import Mathlib.Analysis.Convex.Function import Mathlib.LinearAlgebra.LinearIndependent.Defs import Definitions.Def_LinearOptimization_OptimalCostFunction open Matrix /-- **Bertsimas & Tsitsiklis, Theorem 5.3 (p. 217).** For a feasible standard form problem (rows of `A` linearly independent): (a) the set `T` of cost vectors with finite optimal cost is convex; (b) the optimal cost `G(c)` is concave on `T`; (c) if the primal has a unique optimal solution `x*` for the cost vector `c`, then `G` is linear in a vicinity of `c` with gradient `x*`. -/
theorem LinearOptimization.lp_optimal_cost_concave_in_cost {m n : ℕ}
(A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ) (G : (Fin n → ℝ) → ℝ)
(hrank : LinearIndependent ℝ (fun i => A i))
(hfeas : (stdPolyhedron A b).Nonempty)
(hG : ∀ c ∈ finiteCostSet A b, ((G c : ℝ) : EReal) = lpOptimalCostCost A b c) :
Convex ℝ (finiteCostSet A b) ∧
ConcaveOn ℝ (finiteCostSet A b) G ∧
∀ (c xstar : Fin n → ℝ),
IsLpOptimal c (stdPolyhedron A b) xstar →
(∀ y, IsLpOptimal c (stdPolyhedron A b) y → y = xstar) →
∃ ε > (0 : ℝ), ∀ c' : Fin n → ℝ, (∀ j, |c' j - c j| < ε) →
c' ∈ finiteCostSet A b ∧ G c' = G c + (c' - c) ⬝ᵥ xstar := by
sorry
Read-back
What the Lean code literally says, in plain math · claude-fable-5
Data: , an real matrix , right-hand side , and a function . Write and, for a cost vector , in the extended reals; let . Hypotheses: (a) the rows of are linearly independent; (b) is nonempty; (c) for every , the real equals (as extended reals); is unconstrained outside . Conclusion, a conjunction of three claims: (1) is a convex subset of ; (2) is concave on (again in the sense that bundles convexity of with for , , ); (3) for every cost and point : if minimizes over (i.e. and for all ) and every such minimizer equals (uniqueness), then there exists such that every with for all coordinates satisfies both and the exact equality — i.e. on this sup-norm ball is affine with gradient .
Confirmed by the mission captain (proposal self-audit).