# On the Optimality of(s,S) Inventory Policies: A Quasivariational Approach

Authors: Lakdere Benkherouf
Journal: Journal of Applied Mathematics and Stochastic Analysis
 (2008)

---

## Abstract

This paper revisits the classical discrete-time stationary inventory model. A new proof, based on the theory of
quasivariational inequality (QVI), of the optimality of(s,S) policy
is presented. This proof reveals a number of interesting properties of the optimal cost function. Further, the proof could be used as a tutorial for applications of QVI to inventory control.


---

## Body

## 1. Introduction

Consider an
inventory model which consists in controlling the level of stock of a single
product where the demandsD1,D2,… for the product in periods 1,2,… are independently and identically distributed
(i.i.d) random variables with density function ψ,
and finite mean μ<∞.Assume that at the beginning of each period the system
is reviewed and we are allowed to increase the level of stock to any level we
wish. Orders are assumed to be delivered immediately.Letf be a real-valued function representing the
holding and shortage cost with f(0)=0 and f(x)>0 for x≠0. The cost c(x) of ordering an amount x is given by (1.1)c(x)={k+cx,x>0,0,x=0, where c is the unit cost of the item and k is the set-up cost (c>0,k>0).
Costs are assumed to be additive and geometrically discounted at a rate α,0<α<1,
and that unmet demand is completely backlogged.An admissible replenishment policy consists of a
sequence(ti,ξi),i=1,…,  where ti represents the ith time of ordering and ξi>0 represents the quantity ordered at time ti.
Write(1.2)Vn={(ti,ξi),i=1,…n},V∞=lim⁡n→∞⁢Vn=V.Letx(n) denote the level of stock at time n,n=0,1,…,  and let ℱn=σ{x(s),s≤n} be the σ-algebra generated by the history of the inventory
level up to time n.
Assume that for each n∈ℕ,𝒱n  is ℱn-measurable. Then for a given initial
inventory level x and an ordering policy 𝒱,
the infinite horizon discounted cost is defined by(1.3)y(x,V):=EV{∑t=0∞αtf(x(t))+∑i=1nαtic(ξi)},where the expectation is taken
with respect to all possible realizations of the process x(t) under policy 𝒱.
Set(1.4)y(x):=inf⁡Vy(x,V).The objective is to find an
admissible policy 𝒱∗ such that y(x,𝒱∗)=y(x).Scarf [1] considered a finite horizon version of the problem
described in (1.3). He showed using dynamic programming that if the one period
expected holding plus shortage cost function is convex, then the optimal policy
for period n is an (sn,Sn) policy. The principal tool used by Scarf was a
concept of K-convexity which he introduced in the same
paper. Subsequently, Iglehart [2] extended Scarf's result to the infinite horizon case
by showing that the property of K-convexity holds for the infinite period
stationary model. Veinott [3] replaced the requirement of the convexity of the one
period expected holding plus shortage cost by a quasiconvexity requirement and
added other conditions. Again using dynamic programming, he showed the
optimality of an (s,S) policy.In this paper, we approach the problem of determining
the optimal inventory policy as an impulse control problem, the theory which
has been developed by Bensoussan and Lions [4]. Under this theory, the Bellman equation of dynamic
programming for the inventory problem leads to a set of quasivariational
inequalities (QVIs) whose solution leads to the optimal inventory policy. This approach
leads to a new proof of the result which does not use K-convexity and is based on the examination of
some properties of an integral equation. Previous applications of QVI to inventory control revolved
around diffusion processes from which the machinery needed to
prove optimality of (s,S) policy was not simple. This paper we
hope can serve as a tutorial of applications of QVI to inventory
control. Readers interested in applications of
QVI to inventory control may consult [5–8].Before we embark on the proof we will first
formulate the problem described in (1.3) as a QVI.Recall thatx(t) refers to the level of stock at time t,
and consider all possible actions at time t.(i) If no order is made, then it follows from (1.3)
and (1.4) that(1.5)y(x(t))≤E[f(x(t)−D)]+αE[y(x(t)−D)]or(1.6)y(x(t))−αE[y(x(t)−D)]≤E[f(x(t)−D)],where D refers to the demand in a period.(ii) If an order of sizeξ is made, then the level of stock jumps from x(t) to x(t)+ξ,
and(1.7)y(x(t))≤k+inf⁡ξ>0[cξ+y(x(t)+ξ)].For x∈ℝ,
define the operators A and M by(1.8)(Ay)(x):=y(x)−αE[y(x−D)],(My)(x):=k+inf⁡ξ>0[cξ+y(x+ξ)].It follows that the problem of
finding the optimal solution to (1.3) reduces to solving the following QVI
problem:(1.9)Ay≤F,y≤My,(Ay−F)(y−My)=0,where(1.10)F(x):=E[f(x−D)].To solve the QVI given in (1.9),
we examine an integral equation problem related to the QVI. This is done in
Section 2. The properties obtained of the integral equation are then used to
show the optimality of (s,S) policy in Section 3.


## 2. An Integral Equation Problem

Consider the space of continuous functionsC(ℝ).
Assume that we are given a nonnegative function h in C(ℝ).Further,
suppose that(A1)
there
existsγh,−∞<γh<∞,
such that h is decreasing on (−∞,γh] and nondecreasing on [γh,∞);(A2)
h(x)→∞,
as |x|→∞.ForL in C(ℝ),
define the convolution operator ∗ by(2.1)(ψ∗L)(x)=∫0∞L(x−t)ψ(t)dt.Now, consider the integral
equation(2.2)L(x)−α(ψ∗L)(x)=h(x),x>s,L(x)=11−αh(s),x≤s.Here, s<γh,
and it is a free parameter.Under assumption thath is in C(ℝ),
the integral equation (2.2) has a unique solution in C(ℝ) (see [9]). Let Ls denote this solution. In what follows, there
is a list of properties of Ls which will prove useful in showing the
optimality of the (s,S) policy: (2.3)Ls(x)=11−αh(s)∀x≤s,(2.4)Ls⁢isdecreasingon(s,γh],(2.5)Ls(x)≥11−αh(γh)∀x⁢inℝ,(2.6)Ls(x)⟶∞asx⟶∞.Property (2.3) is the boundary condition of
(2.2).Proof of Property (2.4).
To show
(2.4) argue by contradiction. Assume that Ls initially does not decrease. In other words,
there exists Δ, s<Δ<γh such that Ls is nondecreasing on [s,Δ).
It follows that for x and t satisfying s≤x≤Δ and t≥0, Ls(x)−Ls(x−t)≥0;
but (2.2) gives(2.7)(1−α)Ls(Δ)+α∫0∞(Ls(Δ)−Ls(Δ−t))ψ(t)dt=h(Δ).Therefore, (1−α)Ls(Δ)≤h(Δ) or Ls(Δ)≤(1/(1−α))h(Δ).
This leads to Ls(Δ)<(1/(1−α))h(s) by Assumption (A1).
Property (2.3) then
implies that Ls(Δ)<Ls(s),
which leads to a contradiction.
To complete the
proof, we again argue by contradiction and assume that there existsη,
and Δ, s<η<Δ<γh,
such that Ls is decreasing on [s,η] and nondecreasing on [η,Δ).
Let x be such that η<x<Δ,
and Ls(x)<Ls(s).
We claim that for t≥0,  (2.8)Ls(x)−Ls(x−t)≥Ls(η)−Ls(η−t).We have by (2.2)(2.9)(1−α)Ls(x)+α∫0∞(Ls(x)−Ls(x−t))ψ(t)dt=h(x).Now, use (2.8) and the fact that Ls(x)≥Ls(η) to get from (2.9) that(2.10)h(x)≥(1−α)Ls(η)+α∫0∞(Ls(η)−Ls(η−t))ψ(t)dt=h(η),but h(x)<h(η) by Assumption (A1). This leads to a
contradiction. This ends the proof.Proof of Property (2.5).
Assume that Property (2.5) is not true. Using Property
(2.4)
and the fact that Ls is continuous, let x∗ be the first (smallest) solution of Ls(x∗)=(1/(1−α))h(γh).
Clearly, x∗>s,
and Ls attains its minimum at x∗ on (−∞,x∗].
Using (2.2), Assumption (A1), and recalling that ψ is a density function, we get(2.11)Ls(x∗)=h(x∗)+α∫0∞Ls(x∗−t)ψ(t)dt>h(x∗)+αLs(x∗).Therefore, Ls(x∗)>(1/(1−α))h(γh).
This leads to a contradiction. Whence Property (2.4) holds.Proof of Property (2.6).
Using
(2.2), we get(2.12)Ls(x)=h(x)+α∫0∞Ls(x−t)ψ(t)dt≥h(x)+α1−αh(γh).The last inequality follows from
Property (2.5). The result is then immediate from Assumption (A2)  by
taking the limit as x→∞.
This completes the proof.We will next present further properties ofLs.Theorem 2.1.
For a givens<γh,
there exists an  S(s),γh<S(s)<∞,
which minimizes Ls(x) for x in ℝ.Proof.
The proof follows from Properties
(2.3)–(2.6) and the continuity of Ls.We remark here thatS(s) may not be unique.Fors<γh,
define(2.13)K(s)=Ls(s)−min⁡x∈ℝLs(x).Clearly, K is a well-defined function on (−∞,γh) and is nonnegative.Lemma 2.2.
The functionK is decreasing in s.Proof.
Lett<s<γh,
and for x in ℝ,
define(2.14)D(x):=Lt(x)−Ls(x).It is easy to show that D is a solution of (2.2) with the right-hand
side changed to g(x)={h(t)−h(s),x≤t,h(x)−h(s),t≤x≤s,0,x>s. The function g is constant on (−∞,t],
decreasing on [t,s], and is equal to zero for x>s.
Therefore, a similar argument to that used to show properties (2.4)
and (2.5)
shows that D is decreasing on ℝ and is nonnegative. Since S(s)>s>t,
it follows from Theorem 2.1 that(2.15)Lt(t)−Ls(t)≥Lt(S(s))−Ls(S(s))≥Lt(S(t))−Ls(S(s)),but Ls(t)=Ls(s).
Therefore, Lt(t)−Lt(S(t))≥Ls(s)−Ls(S(s)),
which leads to the required result.Lemma 2.3.
The functionK is continuous.Proof.
Fixϵ>0.
Since h is continuous, there exists δ>0 such that |h(s)−h(t)|<((1−α)/2)ϵ whenever |s−t|<δ.
Pick t<γh such that |s−t|<δ.
To make things simple, assume t<s.
It was shown in the proof of Theorem 2.1 that Lt(S(t))−Ls(S(s))≤Lt(t)−Ls(s).
Now, use the definition of Lt(t) and Ls(s) to get that Lt(S(t))−Ls(S(s))≤(1/(1−α))(h(t)−h(s))<ϵ/2;
but(2.16)|K(t)−K(s)|≤|Lt(S(t))−Ls(S(s))|+|Lt(t)−Ls(s)|<ϵ2+ϵ2=ϵ.Therefore, K is continuous.Lemma 2.4.
(i)K(s)→0ass→γh.
(ii)K(s)→∞ass→−∞.Proof.
(i) Recall thatK(s)≥0 and that Ls(x)≥(1/(1−α))h(γh) by
Property
(2.5). In particular, Ls(S(s))≥(1/(1−α))h(γh).
It follows that Ls(s)−(1/(1−α))h(γh)≥K(s)≥0 or (1/(1−α))(h(s)−h(γh))≥K(s)≥0.
The result is then immediate from the continuity of h and Assumption (A2) by letting s→γh.
(ii) Define(2.17)Ls(x):=gs(x), where
(2.18)gs(x)={h(x)+α1−αh(s),x>s,11−αh(s),x≤s.
The function Ls is decreasing on (−∞,γh].
Therefore, for x in (−∞,γh],(2.19)Ls(x)<∫0∞Ls(x−t)ψ(t)dt.Write(2.20)Gs:=Ls−Ls.It is not difficult to show that Gs satisfies the following:(2.21)Gs(x)−α(ψ∗Gs)(x)=α1−αh(s)−α(ψ∗Ls)(x),x>s,⁢Gs(x)=0,x≤s.
Again, a similar argument used to prove
Property
(2.4)
can be used to show that Gs is increasing on (−∞,γh).
Therefore, Gs(γh)≥Gs(s)=0.
This in turn leads to Ls(γh)≥Ls(γh).
Now,(2.22)K(s)=Ls(s)−Ls(S(s))≥Ls(s)−Ls(γh)≥Ls(s)−Ls(γh).The right-hand side of (2.22) is
equal to h(s)−h(γh) with limit ∞ as s→−∞.
This completes the proof of the lemma.Now consider the problem of finding a solutions to the problem(2.23)K(s)=k.Theorem 2.5.
There exits a unique numbers<γh such that K(s)=k.Proof.
The proof is immediate from Theorem2.1 and Lemmas 2.2–2.4.


## 3. Optimality of(s,S) Policy

Recall the definitions of the functionsy and F in (1.9) and let(3.1)L(x):=y(x)+cx,h(x):=(1−α)cx+F(x)+αcμ.It is an easy exercise to see
that for x>s,Ay=F is equivalent to AL=h,
which is the integral equation (2.2) for x>s.Assume thath satisfies Assumptions (A1) and (A2) and let s<0 be the unique solution of (2.23). This value
of s leads to a value of S(s) which minimizes Ls (this may not be unique). Further, let S denote the generic value of S(s).
We will next show that the policy which asserts that if the level of stock x<s,
order up to level S:
else do not order, solves the QVI given by (1.9). The proof of optimality relies
on the concept of non-k-decreasing functions which may be found in
[10, page 137].Definition 3.1.
A functionv:ℝ→ℝ is non-k-decreasing if x≤y implies that(3.2)v(x)≤k+v(y).Note that the concept of non-k-decreasing is weaker than the concept of k-convexity which is a standard tool for
showing optimality of (s,S) policy; see [10] for more details.Our objective is to show that the functionLs is non-k-decreasing. Note from Properties (2.3)–(2.6)
that Ls is constant on (−∞,s],
then decreases at least down to γh,
reaches its minimum at some S,
and eventually goes to ∞ as x→∞.
Non-k-decreasing means that the function Ls cannot have a drop bigger
than k beyond S.
Let(3.3)Δh=min⁡{x>γh,⁢Ls(x)=Ls(s)}.Note thatΔ exists and is unique. Set(3.4)K(s)=Ls(s)−min⁡x≤Δh⁢Ls(x).Theorem 3.2.
Fors<γh, the solution Ls of (2.2) satisfies(3.5)Ls(x)−Ls(y)≤K(s)∀x≤y.Proof.
The proof is by contradiction and
only a sketch of the proof will be given. Consider the set(3.6)ℛ(K(s))={x≥Δh,Ls(x)−Ls(y)>K(s),forsomey≥x}.If ℛ(s) is empty, there is nothing to prove and
theorem is true. Assume that ℛ(𝒦(s)) is not empty, in which case it can be shown
that there exists a triplet (S1,S2,S3) such that γh<S1<Δ<S2<S3 such that on the interval [s,S3],Ls attains its minimum at S1, and its maximum at S2 (as shown in Figure 1) with(3.7)Ls(s)−Ls(S1)=Ls(S2)−Ls(S3):=K(s).We will next show that this
cannot happen. Using (2.2), we get(3.8)Ls(S2)=h(S2)+α∫0∞Ls(S2−t)ψ(t)dt,(3.9)Ls(S3)=h(S3)+α∫0∞Ls(S3−t)ψ(t)dt.It follows that for t≥0,(3.10)Ls(S2−t)−Ls(S3−t)≤K(s).Using (3.7)–(3.9), we
get(3.11)K(s)=h(S2)−h(S3)+α∫0∞(Ls(S2−t)−Ls(S3−t))ψ(t)dt≤h(S2)−h(S3)+αK(s).This leads to (1−α)𝒦(s)≤h(S2)−h(S3)<0 since h is increasing on (γh,∞) by Assumption (A1). Therefore, we have a
contradiction that 𝒦(s)>0.
Therefore, R(s) is empty. This completes the proof.Figure 1
Plot of the
functionLs.As a corollary of Theorem3.2, we have the following.Corollary 3.3.
Fors<γh,
a solution S(s) of the equation Ls(s)−Ls(S(s))=k is a global minimum of the function Ls.Note that the proof of Theorem3.2 revealed that the
value of S belongs to some interval (γh,Δh).
Further, the results of the previous section should make a numerical search for
the value (s,S) an easy exercise.Theorem 3.4.
The functionLs defined from the pair (s,S) which solves (2.23) solves (1.9).Proof.
We need to show thaty<My for x≥s and Ay≤F for x≤s.
To show Ay≤F for x≤s,
let x≤s;
therefore, Ls(x)=Ls(s),
and Ay(x)≤F(x) is equivalent to ALs≤h(x);
but Ls(s)=(1/(1−α))h(s).
Therefore, ALs(s)≤h(x) is equivalent to h(s)≤h(x),
which is true since h is decreasing for x≤γh.
To show thaty≤My(x) for x≥s,
note that(3.12)My(x)=k+c(S−x)+y(S)fors≤x≤S,My(x)=k+y(x)forx≥S.If s≤x≤S,
then y(x)≤My(x) can be written as Ls(x)≤k+Ls(S).
This is true since Ls is non-k-decreasing. This completes the proof.It is worth noting that Assumption (A1) is equivalent
to saying thath is quasiconvex. Also, Assumption (A2) can be weakened by replacing it by lim|x|→∞h(x)>h(γh)+k.
The limit when x→−∞ can be inferred from (2.22) and the limit when x→∞ can be obtained from the proof of Property
(2.6). The optimality of (s,S) policy remains true.In this short paper, an alternative proof of the
optimality of(s,S) policy was given. The proof also revealed that
finding optimal values of (s,S) is a simple exercise in numerical analysis. It
is hoped that this new proof will lead to new insights in the examination of
some stochastic inventory models.



---

*Source: 158193-2008-09-03.xml*