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 ( s , S ) {\displaystyle (s,S)} policy in inventory control theory. The policy is characterized by two numbers s and S, S ≥ 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.

Two equivalent definitions are as follows:

Let K be a non-negative real number. A function g : R → R {\displaystyle g:\mathbb {R} \rightarrow \mathbb {R} } is K-convex if

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

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

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

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

for all x ≤ y , λ ∈ [ 0 , 1 ] {\displaystyle x\leq y,\lambda \in [0,1]} , where λ ¯ = 1 − λ {\displaystyle {\bar {\lambda }}=1-\lambda } .

This definition admits a simple geometric interpretation related to the concept of visibility.^[3] Let a ≥ 0 {\displaystyle a\geq 0} . A point ( x , f ( x ) ) {\displaystyle (x,f(x))} is said to be visible from ( y , f ( y ) + a ) {\displaystyle (y,f(y)+a)} if all intermediate points ( λ x + λ ¯ y , f ( λ x + λ ¯ y ) ) , 0 ≤ λ ≤ 1 {\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 g {\displaystyle g} is K-convex if and only if ( x , g ( x ) ) {\displaystyle (x,g(x))} is visible from ( y , g ( y ) + K ) {\displaystyle (y,g(y)+K)} for all y ≥ x {\displaystyle y\geq x} .

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 . {\displaystyle \lambda =z/(b+z),\quad x=u-b,\quad y=u+z.}

^[4]

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

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

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

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

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

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

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