Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4, p. 939 — for all t, the lost-sales cost functions f̄_t(v) and ḡ_t(v, ζ) are L♮-convex

Proved
ZipkinLostSales.LNatural.theorem_4

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

dynamic-programminginventoryl-natural-convexitylost-salesoperations-researchp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Theorem 4 (Karlin and Scarf 1958 and Morton 1969). Consider the standard single-item lost-sales inventory system in discrete time: lead time L≥1L\ge1L≥1; independent nonnegative demands with a common law μ\muμ of finite mean; unit procurement cost c≥0c\ge0c≥0, holding cost h^≥0\hat h\ge0h^≥0, lost-sales penalty p≥0p\ge0p≥0; discount factor 0<γ≤10<\gamma\le10<γ≤1. In the transformed state v∈Vv\in Vv∈V (partial sums of the pipeline, vl=∑k≥lxkv_l=\sum_{k\ge l}x_kvl​=∑k≥l​xk​) and transformed order ζ=−z≤0\zeta=-z\le0ζ=−z≤0, let

gˉt(v,ζ)=−γLcζ+q^0(v0−v1)+γE[fˉt+1(v+)],fˉt(v)=min⁡ζ≤0gˉt(v,ζ),fˉT+L+1≡0,\bar g_t(v,\zeta)=-\gamma^Lc\zeta+\hat q^0(v_0-v_1)+\gamma E\big[\bar f_{t+1}(v_+)\big],\qquad \bar f_t(v)=\min_{\zeta\le0}\bar g_t(v,\zeta),\qquad \bar f_{T+L+1}\equiv0,gˉ​t​(v,ζ)=−γLcζ+q^​0(v0​−v1​)+γE[fˉ​t+1​(v+​)],fˉ​t​(v)=ζ≤0min​gˉ​t​(v,ζ),fˉ​T+L+1​≡0,

with q^0(y)=E[h^(y−d)++p(y−d)−]\hat q^0(y)=E[\hat h(y-d)^+ + p(y-d)^-]q^​0(y)=E[h^(y−d)++p(y−d)−] and v+=([v0−v1−d]++v1,v2,…,vL−1,0)−ζev_+=([v_0-v_1-d]^+ +v_1,v_2,\dots,v_{L-1},0)-\zeta ev+​=([v0​−v1​−d]++v1​,v2​,…,vL−1​,0)−ζe.

Then for all ttt, the functions fˉt(v)\bar f_t(v)fˉ​t​(v) and gˉt(v,ζ)\bar g_t(v,\zeta)gˉ​t​(v,ζ) are L♮-convex: fˉt(v−ζe)\bar f_t(v-\zeta e)fˉ​t​(v−ζe) is submodular in (v,ζ)(v,\zeta)(v,ζ) on V×ℜ−V\times\Re^-V×ℜ−, and gˉt((v,ζ)−ξ(e,1))\bar g_t\big((v,\zeta)-\xi(e,1)\big)gˉ​t​((v,ζ)−ξ(e,1)) is submodular in (v,ζ,ξ)(v,\zeta,\xi)(v,ζ,ξ) for v∈Vv\in Vv∈V, ζ≤ξ≤0\zeta\le\xi\le0ζ≤ξ≤0.

L♮-convexity is the structural property from which the paper derives that the optimal order is monotone in the transformed state with limited sensitivity (Corollary 5), and from which convexity of fˉt\bar f_tfˉ​t​ follows.

Formalization Note. Data are stationary, so fˉt\bar f_tfˉ​t​ depends on ttt only through the number of periods to go k=T+L+1−tk=T+L+1-tk=T+L+1−t; the statement is for every k≥0k\ge0k≥0, pairing fbar … k with gbar … k (whose continuation is fbar … k), which covers every ttt of every horizon TTT. Vectors are indexed 0,…,L−10,\dots,L-10,…,L−1 with vL=0v_L=0vL​=0. The paper's "min" over ζ≤0\zeta\le0ζ≤0 is an infimum; under the hypotheses all costs are nonnegative, so it is not Lean's junk value. The cost hypotheses read the paper's "unit cost" and "discount rate"; nonnegative independent demand is the paper's, with one law because data are stationary; finite mean demand is added so that q^0\hat q^0q^​0 is finite. Expectations are Bochner integrals.

Preamble
import Mathlib
import Definitions.Def_ZipkinLostSales_LNatural_Model
open MeasureTheory
Formal statement
namespace ZipkinLostSales.LNatural

/-- Theorem 4 (Karlin and Scarf 1958 and Morton 1969; Zipkin 2008, p. 939): for all `t`, the
functions `f̄_t(v)` and `ḡ_t(v, ζ)` are L♮-convex. With `k` the number of periods to go,
`fbar … k` is L♮-convex on `V` and `gbar … k` is L♮-convex on `V × ℜ⁻`, for every `k`. -/
theorem theorem_4 (L : ℕ) (hL : 0 < L) (μ : Measure ℝ) [IsProbabilityMeasure μ]
    (hμ : μ (Set.Iio 0) = 0) (hμint : Integrable id μ)
    (c hh p γ : ℝ) (hc : 0 ≤ c) (hhh : 0 ≤ hh) (hp : 0 ≤ p) (hγ0 : 0 < γ) (hγ1 : γ ≤ 1) (k : ℕ) :
    LNatConvexOn (V L) (fbar c hh p γ μ k) ∧
      LNatConvexOn (VxNeg L) (liftG (gbar c hh p γ μ k)) := by sorry

end ZipkinLostSales.LNatural
Source
Zipkin, On the Structure of Lost-Sales Inventory Models, Oper. Res. 56 (2008), p. 939 (PDF p. 4), Theorem 4; model §2 (1)–(2), pp. 937–938, and §3 transformation, p. 938
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me