K-convex function explained

K-convex functions, first introduced by Scarf,^[1] are a special weakening of the concept of convex function which is crucial in the proof of the optimality of the

(s,S) policy in inventory control theory. The policy is characterized by two numbers and, S \geq s , such that when the inventory level falls below level, an order is issued for a quantity that brings the inventory up to level, and nothing is ordered otherwise. Gallego and Sethi ^[2] have generalized the concept of K-convexity to higher dimensional Euclidean spaces.

Definition

Two equivalent definitions are as follows:

Definition 1 (The original definition)

Let K be a non-negative real number. A function

g: R → R is K-convex ifg(u) + z\left[ (g(u) - g(u - b))/(b) \right] \leq g(u + z) + K for any u, z\geq 0 , and b> 0 .

Definition 2 (Definition with geometric interpretation)

A function

g: R → R is K-convex ifg( λ x + \bar{ λ } y) \leq λ g(x) + \bar{ λ } [g(y) + K] for all x\leq y, λ \in [ 0 , 1 ] , where \bar{ λ } =1-λ .

This definition admits a simple geometric interpretation related to the concept of visibility.^[3] Let

a \geq 0 . A point (x,f(x)) is said to be visible from (y,f(y) + a) if all intermediate points ( λ x + \bar{ λ } y, f( λ x + \bar{ λ } y)), 0 \leq λ \leq 1 lie below the line segment joining these two points. Then the geometric characterization of K-convexity can be obtain as:

A function

g is K-convex if and only if (x,g(x)) is visible from (y,g(y) + K) for all y\geq x .

Proof of Equivalence

It is sufficient to prove that the above definitions can be transformed to each other. This can be seen by using the transformation

λ = z/(b + z), x = u - b, y = u + z.

Properties

^[4]

Property 1

If

g: R → R is K-convex, then it is L-convex for any L\geq K . In particular, if g is convex, then it is also K-convex for any K\geq 0 .

Property 2

If

g _{1} is K-convex and g _{2} is L-convex, then for \alpha \geq 0 , \beta \geq 0 , g = \alpha g _{1} + \beta g _{2} is (\alpha K + \beta L) -convex.

Property 3

If

g is K-convex and \xi is a random variable such that E|g(x - \xi)|< inf ty for all x , then Eg(x - \xi) is also K-convex.

Property 4

If

g: R → R is K-convex, restriction of g on any convex set D \subset R is K-convex.

Property 5

If

g: R → R is a continuous K-convex function and g(y) → inf ty as |y| → inf ty , then there exit scalars s and S with s\leq S such thatg(S)\leq g(y) , for all y\in R ;g(S) + K = g(s)<g(y) , for all y<s ;g(y) is a decreasing function on ( -inf ty, s) ;g(y)\leq g(z) + K for all y, z with s\leq y\leq z .

Further reading

• Gallego . G. . Sethi . S. P. . 10.1007/s10957-005-6393-4 . 1 . Journal of Optimization Theory and Applications . 2174750 . 71–88 . l{K} -convexity in ak{R} ^{n} . 127 . 2005.

Notes and References

1. Book: Scarf. H.. The Optimality of (S, s) Policies in the Dynamic Inventory Problem. 1960. Stanford University Press. Stanford, CA. Chapter 13.
2. Gallego, G. and Sethi, S. P. (2005). K-convexity in ℜⁿ. Journal of Optimization Theory & Applications, 127(1):71-88.
3. Book: Kolmogorov. A. N.. Fomin. S. V.. Introduction to Real Analysis. 1970. Dover Publications Inc.. New York.
4. Sethi S P, Cheng F. Optimality of (s, S) Policies in Inventory Models with Markovian Demand. INFORMS, 1997.