Lemma 2.3 — the subdifferential of an LP value function is the set of optimal dual solutions
ProvedKallMayerSLP.Recourse.lemma_2_3kall-mayer-slplinear-programmingp2o-gran-per-chapterp2o-plan-bookp2o-v1stochastic-programmingtwo-stage-recourse
Let , , and assume that the linear program
is solvable for every right-hand side . Let be its optimal value. Then is convex on , it is subdifferentiable at every , and its subdifferential is the set of optimal dual solutions at :
Here means for all . Applied to the recourse LP, this lemma yields the subdifferential formula of Theorem 2.2.
Formalization Note is the published KallMayer.Recourse.LPValue (an EReal infimum, finite here by solvability), "solvable ∀b" is KallMayer.Recourse.SolvableEveryRHS, the argmax set is KallMayer.Recourse.DualOptimizers, and is the published StochasticProg.RecourseKKT.subdifferential.
Differences from the source:
- encoding: subdifferential of a convex function ℝⁿ → ℝ (Chapter 1, Def. 3.2, p.61); 'subdifferentiable at b' → the published
StochasticProg.RecourseKKT.subdifferentialof theERealfunction (requires the value at the point to be finite); nonempty subdifferential; reason: the functions are finite here, where the two notions agree - encoding: the optimal value φ(b) and '(obviously convex in b)' →
LPValue A c b(EReal); convexity stated for its real part as the first conjunct; reason: φ is finite for every b by the solvability hypothesis
Preamble
import Mathlib import Definitions.Def_KallMayer_Recourse_LPValue import Definitions.Def_StochasticProg_RecourseKKT_subdifferential open KallMayer.Recourse (LPValue SolvableEveryRHS DualOptimizers) open StochasticProg.RecourseKKT (subdifferential) open Matrix
Formal statement
namespace KallMayerSLP.Recourse
/-- Lemma 2.3 (Kall & Mayer, Stochastic Linear Programming (2005), Chapter 3, Lemma 2.3, p.206,
PDF 215): assume that the LP `min{cᵀx | Ax = b, x ≥ 0}` is solvable `∀ b ∈ ℝᵐ`. Then its optimal value
`φ(b)` (obviously convex in `b`) is subdifferentiable at any `b`, and the subdifferential is given as
`∂φ(b) = argmax{bᵀu | Aᵀu ≤ c}`, the set of optimal dual solutions at `b`.
**Formalization Note.** `φ = KallMayer.Recourse.LPValue A c` (an `EReal` infimum), "solvable ∀b" is
`KallMayer.Recourse.SolvableEveryRHS A c`, and the argmax set is `KallMayer.Recourse.DualOptimizers`,
all published. The subdifferential is the published `StochasticProg.RecourseKKT.subdifferential`
(`g ∈ ∂φ(b)` iff `φ(b)` is a real number and `gᵀ(z − b) ≤ φ(z) − φ(b)` for all `z`), which is
Chapter 1, Def. 3.2 (p.61) for the real-valued `φ` of this lemma. The parenthetical convexity claim
is the first conjunct, for the real function `b ↦ φ(b)`. -/
theorem lemma_2_3 {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (c : Fin n → ℝ)
(hsolv : SolvableEveryRHS A c) :
ConvexOn ℝ Set.univ (fun b : Fin m → ℝ => (LPValue A c b).toReal) ∧
∀ b : Fin m → ℝ, (subdifferential (LPValue A c) b).Nonempty ∧
subdifferential (LPValue A c) b = DualOptimizers A c b := by sorry
end KallMayerSLP.Recourse
Source
Kall & Mayer, Stochastic Linear Programming (2005), Chapter 3, Lemma 2.3, p.206 (PDF 215); subgradient: Chapter 1, Def. 3.2, p.61
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.