Lemma 1, p. 938 — if f(v) is L♮-convex, so is ψ(v, ζ) = f(v − ζe)
ProvedZipkinLostSales.LNatural.lemma_1l-natural-convexityoperations-researchp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1submodularity
Let and let be the cone of nonnegative vectors with nonincreasing components. Let denote the all-ones vector.
If is L♮-convex, then the function
is L♮-convex on , that is, is submodular on the set of with and .
The lemma lets L♮-convexity pass from the next period's cost to functions of the state and the order, as in the proof of Theorem 4.
Formalization Note. L♮-convexity is LNatConvexOn of the mission's definitions file: on it is the paper's definition (submodularity of on ), and on the shift acts on all coordinates, so the domain is (the set used in the proof of Lemma 2). Functions are total on , but only their values on enter.
Preamble
import Mathlib import Definitions.Def_ZipkinLostSales_LNatural_Model open MeasureTheory
Formal statement
namespace ZipkinLostSales.LNatural
/-- Lemma 1 (Zipkin 2008, p. 938): if `f(v)` is L♮-convex on `V`, so is
`ψ(v, ζ) = f(v − ζe)` on `V × ℜ⁻`. -/
theorem lemma_1 (L : ℕ) (hL : 0 < L) (f : (Fin L → ℝ) → ℝ) (hf : LNatConvexOn (V L) f) :
LNatConvexOn (VxNeg L) (liftG (fun v ζ => f (fun i => v i - ζ))) := by sorry
end ZipkinLostSales.LNatural
Source
Zipkin, On the Structure of Lost-Sales Inventory Models, Oper. Res. 56 (2008), p. 938 (PDF p. 3), Lemma 1; proof on p. 939
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.