K-convex function

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 ${\displaystyle (s,S)}$ policy in inventory control theory. The policy is characterized by two numbers s and S, ${\displaystyle S\geq s}$, 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 ${\displaystyle g:\mathbb {R} \rightarrow \mathbb {R} }$ is K-convex if

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

for any ${\displaystyle u,z\geq 0,}$ and ${\displaystyle b>0}$.

Definition 2 (Definition with geometric interpretation)

A function ${\displaystyle g:\mathbb {R} \rightarrow \mathbb {R} }$ is K-convex if

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

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

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

A function ${\displaystyle g}$ is K-convex if and only if ${\displaystyle (x,g(x))}$ is visible from ${\displaystyle (y,g(y)+K)}$ for all ${\displaystyle 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

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

Properties

^[4]

Property 1

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

Property 2

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

Property 3

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

Property 4

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

Property 5

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

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

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 ℜⁿ. 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.

Further reading

• Gallego, G.; Sethi, S. P. (2005). "${\displaystyle {\mathcal {K}}}$-convexity in ${\displaystyle {\mathfrak {R}}^{n}}$" (PDF). Journal of Optimization Theory and Applications. 127 (1): 71–88. doi:10.1007/s10957-005-6393-4. MR 2174750.