Lemma 1 (Single-Location Inventory Problem): canonical optimality, a cost transfer with , and the bound
ProvedOWMR.single_location_lemmaLet the one-period demand have law on with , let be convex, coercive ( as ) and globally Lipschitz, and fix a setup cost . In the single-location inventory problem with cost , in each period the position may be raised by at cost , the post-action position incurs , and an i.i.d. demand then reduces it. Its value (slValue) is the infimum, over all nonanticipative policies that may randomize independently of demand, of the long-run average cost
from initial position . Then is a finite number with , and:
- Initial position. The same infimum from any initial position equals .
- Optimal rules. If and the policy started at has long-run average cost , then from every initial position the rule that orders up to whenever the pre-action position is at most , and does not order otherwise, has long-run average cost .
- Positive setup cost. If , there are such that the policy started at has long-run average cost and the canonical conditions hold:
Its post-action positions lie in , and its cycle length has for every . 4. Zero setup cost. If , there is a minimizer of with , and base stock at has long-run average cost . 5. Cost transfers. There is a measurable function with oscillation , and if , such that
- Finite horizons. Let be i.i.d. random elements (for example, demand vectors of a network), independent of auxiliary randomness , with distributed as . For every policy whose order is a measurable function of and , and every initial position , the post-action positions satisfy
This is Lemma 1 of the source. It combines the classical average-cost optimality of policies (Iglehart 1963; Zheng 1991; Feinberg and Lewis 2018), here for real positions and every demand law with finite positive mean, with the bounded cost-transfer function and the finite-horizon bound used for the shared-cost lower bound (Proposition 3), where the history may include network demand and auxiliary randomness.
Formalization note. In item 2 the rule is stated recursively on the history: the order in period is if the pre-action position is at most , and otherwise; the long-run average cost is that of the deterministic policy. In item 3 the moments are taken under the product law of (Measure.infinitePi). In item 6 the left side is read as , the right side being nonnegative, and the expectation is over and .
import Definitions.Def_owmr_single_location import Mathlib.Probability.ProductMeasure open MeasureTheory open scoped ENNReal NNReal
namespace OWMR
theorem single_location_lemma (ρ : Measure ℝ≥0) [IsProbabilityMeasure ρ]
(hρ0 : 0 < ∫⁻ x, (x : ℝ≥0∞) ∂ρ) (hρ1 : ∫⁻ x, (x : ℝ≥0∞) ∂ρ < ∞)
(f : ℝ → ℝ) (hf0 : ∀ y, 0 ≤ f y) (hfcv : ConvexOn ℝ Set.univ f)
(hfco : ∀ C : ℝ, ∃ R : ℝ, ∀ y, R ≤ |y| → C ≤ f y) (hfL : ∃ L : ℝ≥0, LipschitzWith L f)
(K : ℝ) (hK : 0 ≤ K) :
∃ J : ℝ, 0 ≤ J ∧ slValue ρ f K = ENNReal.ofReal J ∧
(∀ y0 : ℝ, (⨅ (U : Type) (_ : MeasurableSpace U) (ν : Measure U)
(_ : IsProbabilityMeasure ν) (q : SLPolicy U) (_ : SLAdmissible q),
slAvgCost ρ f K y0 q ν) = slValue ρ f K) ∧
(∀ s S : ℝ, s ≤ S → ssAvgCost ρ f K s S = slValue ρ f K → ∀ y0 : ℝ,
∃ q : SLPolicy Unit, SLAdmissible q ∧
(∀ (t : ℕ) (d : ℕ → ℝ≥0), q t () d = if slPos y0 q () d t - q t () d ≤ s
then S - (slPos y0 q () d t - q t () d) else 0) ∧
slAvgCost ρ f K y0 q (Measure.dirac ()) = slValue ρ f K) ∧
(0 < K → ∃ s S : ℝ, IsCanonicalOptimum ρ f K s S ∧
(∀ (d : ℕ → ℝ≥0) (t : ℕ), s < ssPost s S d t ∧ ssPost s S d t ≤ S) ∧
∀ m : ℕ, ∫⁻ d, (⨅ (t : ℕ) (_ : 1 ≤ t ∧ ssPre s S d t ≤ s), (t : ℝ≥0∞)) ^ m
∂(Measure.infinitePi fun _ : ℕ => ρ) < ∞) ∧
(K = 0 → ∃ x : ℝ, (∀ y, f x ≤ f y) ∧ J = f x ∧ ssAvgCost ρ f K x x = slValue ρ f K) ∧
(∃ u : ℝ → ℝ, Measurable u ∧ (∀ y z, u y - u z ≤ K) ∧ (K = 0 → ∀ y, u y = 0) ∧
∀ y, J + max (f y - J) 0 ≤ f y + ∫ d, u (y - (d : ℝ)) ∂ρ - u y) ∧
(∀ {α U : Type} [MeasurableSpace α] [Zero α] [MeasurableSpace U]
(μ : Measure α) [IsProbabilityMeasure μ] (ν : Measure U) [IsProbabilityMeasure ν]
(g : α → ℝ≥0), Measurable g → μ.map g = ρ →
∀ q : ℕ → U → (ℕ → α) → ℝ,
(∀ (t : ℕ) (u : U) (d d' : ℕ → α), (∀ r < t, d r = d' r) → q t u d = q t u d') →
(∀ t, Measurable fun ω : U × (ℕ → α) => q t ω.1 ω.2) → (∀ t u d, 0 ≤ q t u d) →
∀ (y0 : ℝ) (T : ℕ), 1 ≤ T →
ENNReal.ofReal (T * J - K) ≤ ∫⁻ ω, ∑ t ∈ Finset.range T, ENNReal.ofReal
(K * (if 0 < q t ω.1 (padHist T ω.2) then 1 else 0)
+ f (y0 + ∑ s ∈ Finset.range (t + 1), q s ω.1 (padHist T ω.2)
- ∑ s ∈ Finset.range t, (g (padHist T ω.2 s) : ℝ)))
∂(ν.prod (Measure.pi fun _ : Fin T => μ))) := by sorry
end OWMRConfirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.