Lemma 2, p. 939 — if g(v, ζ) is L♮-convex, so is f(v) = min_{ζ≤0} g(v, ζ)
ProvedZipkinLostSales.LNatural.lemma_2l-natural-convexityoperations-researchp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1submodularity
Let , let be the cone of nonnegative vectors with nonincreasing components, and let .
If is L♮-convex on and, for every , the values are bounded below, then
is L♮-convex on .
This is the step that carries L♮-convexity from to in the proof of Theorem 4.
Formalization Note. The paper writes . The formalization takes the infimum over and assumes it is over a set bounded below (which holds whenever the minimum exists); without that assumption Lean's real infimum would return the junk value . L♮-convexity on is LNatConvexOn (VxNeg L) applied to viewed on Fin (L+1) → ℝ with as the last coordinate.
Preamble
import Mathlib import Definitions.Def_ZipkinLostSales_LNatural_Model open MeasureTheory
Formal statement
namespace ZipkinLostSales.LNatural
/-- Lemma 2 (Zipkin 2008, p. 939): if `g(v, ζ)` is L♮-convex on `V × ℜ⁻`, so is
`f(v) = min_{ζ ≤ 0} g(v, ζ)` on `V`. The "min" is the infimum over `ζ ≤ 0`, assumed bounded
below for every `v ∈ V`. -/
theorem lemma_2 (L : ℕ) (hL : 0 < L) (g : (Fin L → ℝ) → ℝ → ℝ)
(hg : LNatConvexOn (VxNeg L) (liftG g))
(hbdd : ∀ v ∈ V L, BddBelow (g v '' Set.Iic 0)) :
LNatConvexOn (V L) (fun v => ⨅ ζ : Set.Iic (0 : ℝ), g v ζ) := by sorry
end ZipkinLostSales.LNatural
Source
Zipkin, On the Structure of Lost-Sales Inventory Models, Oper. Res. 56 (2008), p. 939 (PDF p. 4), Lemma 2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.