We consider the problem where there is an amount of stock at time . You can perform the action to order units of stock. Further the demand at time is . We assume is independent over . The change in the amount of stock follows the dynamic:
It is possible for to be negative, which corresponds to backordered stock.
There is a cost for ordering units of stock:
Note here if . There is a cost for holding stock when or for unmet demand when . Specifically
for positive constants and . If we consider the minimization problem over time steps then we have a dynamic program:
The Bellman equation for this optimization problem is
Here . If we define as follows
then (removing the subscript for now) notice the above Bellman Equation becomes
There exists an explicit closed form solution to this optimization. Specifically there exists values and such that if the stock level goes below then we order enough to have units of stock. (We will show that minimizes and is such that .)
We give a proof for the case where . This gives the necessary intuition for the more general case where , which we subsequently discuss. (The formal argument is given in a series of exercises: Ex 2–Ex 4.)
We consider the equation with . Notice if is convex and as then , the minimum of , is finite. Thus from it holds that:
Notice if is convex then relatively straight forward to check that is convex and and (see Ex [sS:Ex0]). Also see the following Figure:
Further, if, given the function above, we now update by taking
then it is straight-forward to check that the new function is also convex and as (see Ex [sS:Ex0]).
Thus (putting sub-script back and noting that is convex) we see that the sequence of functions and are convex and that , the minimum of , defines the optimal control
- If then order so you have units of stock, .
- If then do nothing.
We consider the equation with . That is
In general will not be convex, but let’s assume it is for a moment in order to gain intuition. Again let be the minimum of . In this case the minimization over above is solved at if and if . (Note if in it is obviously better to take rather than .) So we have that
Now assuming is continuous then there will be a value of such that This will be the point for which for then is the minimum in , while for , will be the minimum in . I.e. In this case the optimal control will be
For a convex function we plot in Figure [sS:Fig2]. Notice that is clearly not convex. Essentially, the additional term has introduced a “bump” of size . So rather than assume convexity motivates, this motivates the idea of -convexity.
Definition [-convex] A function is -convex if
Remark. The definition above is not terribly intuitive. It can be shown that -convexity means that for the line segment from to does not intersect for any value of between and . I.e. if you are standing at point you have an unobstructed view of .
If is -convex then we can show that is solved by , just like in the convex case. (This is Ex [sS:Ex1].) Further, we can show that if is -convex then defined by is -convex. (This is Ex [sS:Ex3]). Thus it can be shown that when we update according to the rule
then is also -convex. (This is Ex [sS:Ex2].)
Ex 1. a) Given is convex and for , show that
is such that is convex and for .
b) Given is convex and for , show that
is such that is convex and for .
Ex 2. We let be -convex, continuous with as . Also let and is the smallest number such that .
a) Show that, for , .
(Hint: show .)
b) Show that for , .
(Hint: consider two cases and .)
c) Show that :
is solved by :
The following exercise establishes some properties of -convex functions
Ex 3. Show that
a) The sum of -convex functions is -convex.
b) A convex function is -convex.
c) If is -convex then so is is -convex.
d) The convex combination of -convex functions is -convex.
e) If is -convex then is -convex.
Ex 4. If we let
where minimizes and is the smallest value such that . We will show that is -convex:
Verifying by moving through the following cases:
The idea of -convexity is due to Scarf. A full account of all the calculations above is given in the excellent text of Bertsekas.
Scarf, Herbert. “The optimality of (5, 5) policies in the dynamic inventory problem.” Optimal pricing, inflation, and the cost of price adjustment (1959).
Bertsekas, Dimitri P. Dynamic programming and optimal control. Vol. 1. No. 2. Belmont, MA: Athena scientific, 1995.