K-convex function

From HandWiki

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 [math]\displaystyle{ (s,S) }[/math] policy in inventory control theory. The policy is characterized by two numbers s and S, [math]\displaystyle{ S \geq s }[/math], such that when the inventory level falls below level s, an order is issued for a quantity that brings the inventory up to level S, 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 [math]\displaystyle{ g: \mathbb{R}\rightarrow\mathbb{R} }[/math] is K-convex if

[math]\displaystyle{ g(u)+z\left[\frac{g(u)-g(u-b)}{b}\right] \leq g(u+z) + K }[/math]

for any [math]\displaystyle{ u, z\geq 0, }[/math] and [math]\displaystyle{ b\gt 0 }[/math].

Definition 2 (Definition with geometric interpretation)

A function [math]\displaystyle{ g: \mathbb{R}\rightarrow\mathbb{R} }[/math] is K-convex if

[math]\displaystyle{ g(\lambda x+\bar{\lambda} y) \leq \lambda g(x) + \bar{\lambda} [g(y)+K] }[/math]

for all [math]\displaystyle{ x\leq y, \lambda \in [0,1] }[/math], where [math]\displaystyle{ \bar{\lambda}=1-\lambda }[/math].

This definition admits a simple geometric interpretation related to the concept of visibility.[3] Let [math]\displaystyle{ a \geq 0 }[/math]. A point [math]\displaystyle{ (x,f(x)) }[/math] is said to be visible from [math]\displaystyle{ (y,f(y)+a) }[/math] if all intermediate points [math]\displaystyle{ (\lambda x+\bar{\lambda} y, f(\lambda x+\bar{\lambda} y)), 0\leq \lambda \leq 1 }[/math] lie below the line segment joining these two points. Then the geometric characterization of K-convexity can be obtain as:

A function [math]\displaystyle{ g }[/math] is K-convex if and only if [math]\displaystyle{ (x,g(x)) }[/math] is visible from [math]\displaystyle{ (y,g(y)+K) }[/math] for all [math]\displaystyle{ y\geq x }[/math].

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

[math]\displaystyle{ \lambda = z/(b+z),\quad x=u-b,\quad y=u+z. }[/math]

Properties

[4]

Property 1

If [math]\displaystyle{ g: \mathbb{R}\rightarrow\mathbb{R} }[/math] is K-convex, then it is L-convex for any [math]\displaystyle{ L\geq K }[/math]. In particular, if [math]\displaystyle{ g }[/math] is convex, then it is also K-convex for any [math]\displaystyle{ K\geq 0 }[/math].

Property 2

If [math]\displaystyle{ g_1 }[/math] is K-convex and [math]\displaystyle{ g_2 }[/math] is L-convex, then for [math]\displaystyle{ \alpha \geq 0, \beta \geq 0,\; g=\alpha g_1 +\beta g_2 }[/math] is [math]\displaystyle{ (\alpha K+\beta L) }[/math]-convex.

Property 3

If [math]\displaystyle{ g }[/math] is K-convex and [math]\displaystyle{ \xi }[/math] is a random variable such that [math]\displaystyle{ E|g(x-\xi)|\lt \infty }[/math] for all [math]\displaystyle{ x }[/math], then [math]\displaystyle{ Eg(x-\xi) }[/math] is also K-convex.

Property 4

If [math]\displaystyle{ g: \mathbb{R}\rightarrow\mathbb{R} }[/math] is K-convex, restriction of [math]\displaystyle{ g }[/math] on any convex set [math]\displaystyle{ \mathbb{D}\subset\mathbb{R} }[/math] is K-convex.

Property 5

If [math]\displaystyle{ g: \mathbb{R}\rightarrow\mathbb{R} }[/math] is a continuous K-convex function and [math]\displaystyle{ g(y)\rightarrow \infty }[/math] as [math]\displaystyle{ |y|\rightarrow \infty }[/math], then there exit scalars [math]\displaystyle{ s }[/math] and [math]\displaystyle{ S }[/math] with [math]\displaystyle{ s\leq S }[/math] such that

  • [math]\displaystyle{ g(S)\leq g(y) }[/math], for all [math]\displaystyle{ y\in \mathbb{R} }[/math];
  • [math]\displaystyle{ g(S)+K=g(s)\lt g(y) }[/math], for all [math]\displaystyle{ y\lt s }[/math];
  • [math]\displaystyle{ g(y) }[/math] is a decreasing function on [math]\displaystyle{ (-\infty, s) }[/math];
  • [math]\displaystyle{ g(y)\leq g(z)+K }[/math] for all [math]\displaystyle{ y, z }[/math] with [math]\displaystyle{ s\leq y\leq z }[/math].

References

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

External links