Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

(3), p. 1257 — f* satisfies f(x) = min_{z≥0}{q(x,z) + γE[f(x_+)]}, the minimum is attained, and f* is the least solution

Proved
LostSalesOldNew.LeadTime.optimality_equation

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

bellman-equationdynamic-programminglost-salesp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Consider the lost-sales system of Zipkin (2008), §2, with lead time L≥1L \ge 1L≥1, cost data c,h^,p≥0c,\hat h,p \ge 0c,h^,p≥0, discount factor γ∈[0,1)\gamma \in [0,1)γ∈[0,1), and i.i.d. demand with law DDD on [0,∞)[0,\infty)[0,∞) with finite mean. Let f∗Lf^{*L}f∗L be the infinite-horizon optimal cost, the limit of the finite-horizon optimal costs of recursion (2) as the horizon grows, let q(x,z)=qL(x,z)q(x,z) = q^L(x,z)q(x,z)=qL(x,z) be the transformed one-period cost and x+=([x0−d]++x1,x2,…,xL−1,z)x_+ = ([x_0-d]^+ + x_1, x_2, \dots, x_{L-1}, z)x+​=([x0​−d]++x1​,x2​,…,xL−1​,z) the next state. Then:

  1. for every state x≥0x \ge 0x≥0,
f∗L(x)=inf⁡z≥0{q(x,z)+γ E[f∗L(x+)]};f^{*L}(x) = \inf_{z \ge 0}\Bigl\{ q(x,z) + \gamma\, E\bigl[f^{*L}(x_+)\bigr] \Bigr\};f∗L(x)=z≥0inf​{q(x,z)+γE[f∗L(x+​)]};
  1. if c>0c > 0c>0 or h^>0\hat h > 0h^>0, the infimum is a minimum: for every x≥0x \ge 0x≥0 there is an order z∗(x)≥0z^*(x) \ge 0z∗(x)≥0 with f∗L(x)=q(x,z∗(x))+γE[f∗L(x+)]f^{*L}(x) = q(x,z^*(x)) + \gamma E[f^{*L}(x_+)]f∗L(x)=q(x,z∗(x))+γE[f∗L(x+​)], the next state taken with z=z∗(x)z = z^*(x)z=z∗(x);
  2. f∗Lf^{*L}f∗L is the least solution: every function ggg with values in [0,∞][0,\infty][0,∞] that satisfies the equation of item 1 at every x≥0x \ge 0x≥0 satisfies f∗L(x)≤g(x)f^{*L}(x) \le g(x)f∗L(x)≤g(x) for every x≥0x \ge 0x≥0.

This is the functional equation (3) of the paper: the optimal cost of the infinite-horizon problem satisfies the Bellman equation with a minimizing order, and it is singled out among the solutions. The lead-time bound (6) is obtained by substituting into it.

Formalization Note. The paper says the optimal cost "uniquely satisfies" (3), calls f∗f^*f∗ "the solution" and z∗(x)z^*(x)z∗(x) "an optimal policy", without naming a function class for uniqueness. Uniqueness in an unspecified class is not formalized; item 3 states the class-free part of it, that f∗Lf^{*L}f∗L is the least nonnegative solution. Attainment (item 2) is stated under c>0c > 0c>0 or h^>0\hat h > 0h^>0: when c=h^=0c = \hat h = 0c=h^=0 and demand has unbounded support, f∗L≡0f^{*L} \equiv 0f∗L≡0 but every order leaves a positive expected penalty, so the paper's min⁡\minmin is not attained in that degenerate case. The optimal cost is defined as sup⁡nTn0\sup_n T^n 0supn​Tn0 (value iteration from the terminal condition fT+1=0f_{T+1} = 0fT+1​=0 of (2)), with values in [0,∞][0,\infty][0,∞]. The equation is stated at nonnegative states, the states the system visits.

Preamble
import Mathlib
import Definitions.Def_LostSalesOldNew_LeadTime_Model
Formal statement
namespace LostSalesOldNew.LeadTime

open MeasureTheory

theorem optimality_equation (K : Costs) (D : Measure ℝ) [IsProbabilityMeasure D]
    (hD : LostSalesOldNew.StateReduction.IsDemand D) (hmean : Integrable (fun d : ℝ => d) D)
    (L : ℕ) (hL : 1 ≤ L) :
    (∀ x : Fin L → ℝ, (∀ i, 0 ≤ x i) → fStar K D L x = bellman K D L (fStar K D L) x) ∧
    ((0 < K.c ∨ 0 < K.hhat) → ∀ x : Fin L → ℝ, (∀ i, 0 ≤ x i) → ∃ z : ℝ, 0 ≤ z ∧
      fStar K D L x = ENNReal.ofReal (qL K D L (Fin.snoc (α := fun _ => ℝ) x z))
        + ENNReal.ofReal K.γ * ∫⁻ d, fStar K D L (LostSalesOldNew.StateReduction.next x z d) ∂D) ∧
    (∀ g : (Fin L → ℝ) → ENNReal,
      (∀ x : Fin L → ℝ, (∀ i, 0 ≤ x i) → g x = bellman K D L g x) →
      ∀ x : Fin L → ℝ, (∀ i, 0 ≤ x i) → fStar K D L x ≤ g x) := by sorry

end LostSalesOldNew.LeadTime
Source
Zipkin, Old and New Methods for Lost-Sales Inventory Systems, Operations Research 56(5) (2008), (3), p. 1257
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