Lemma 4 — under (11) the value iterates of (10) satisfy 0 ≤ W_n(i, x) ≤ W^B(x) for a nondecreasing W^B
ProvedSongZipkinFluct.FixedCost.lemma4dynamic-programminginventoryp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1value-iteration
Assume the standing hypotheses of the model and Assumption 1, . Let be a fixed order cost and a terminal cost such that, for some nondecreasing function ,
Then there is a nondecreasing function such that the iterates of the recursion (10) satisfy, for all , all and all ,
The bound is uniform in the world state and in ; it is what makes the series in (10) converge and the limits finite, both for the linear model (, ) and for the fixed-cost model ( of the linear model).
Formalization Note "Finite" is automatic for real-valued functions. The statement holds for every and every satisfying (11).
Preamble
import Mathlib import Definitions.Def_SongZipkinFluct_FixedCost_Bounds open Filter Topology
Formal statement
namespace SongZipkinFluct.FixedCost
open Model
/-- Lemma 4 (p. 356) of Song and Zipkin, *Inventory Control in a Fluctuating Demand
Environment*, Oper. Res. 41(2):351–370 (1993). Under the standing hypotheses and Assumption 1
(`αc̄ < p`, p. 356), for any fixed cost `K ≥ 0` and any terminal cost `W₀` with
`0 ≤ W₀(i, x) ≤ W^B_0(x)` for all `i` (11), where `W^B_0` is nondecreasing, there is a
nondecreasing `W^B` with `0 ≤ W_n(i, x) ≤ W^B(x)` for all `n ≥ 1` and all `i` (12).
Formalization Note: "finite" is automatic for real-valued functions. The lemma is stated for
the general recursion (10) and any `K ≥ 0`; it covers both the linear model (`K = 0`,
`W₀ ≡ 0`, which makes `Wlin` honest) and the fixed-cost model (`K = K̄F̃_L(α)`,
`W₀ = Wlin`). -/
theorem lemma4 {I : Type*} [Countable I] [Nonempty I] [DecidableEq I] (M : Model I)
(hM : M.Standing) (hA1 : M.α * M.cbar < M.p) (K : ℝ) (hK : 0 ≤ K)
(W₀ : I → ℤ → ℝ) (WB₀ : ℤ → ℝ) (hWB₀ : Monotone WB₀)
(h11 : ∀ i x, 0 ≤ W₀ i x ∧ W₀ i x ≤ WB₀ x) :
∃ WB : ℤ → ℝ, Monotone WB ∧
∀ n : ℕ, 1 ≤ n → ∀ i x, 0 ≤ W M K W₀ n i x ∧ W M K W₀ n i x ≤ WB x := by sorry
end SongZipkinFluct.FixedCost
Source
Song and Zipkin, Inventory Control in a Fluctuating Demand Environment, Oper. Res. 41(2):351–370 (1993), DOI 10.1287/opre.41.2.351, p. 356, Lemma 4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.