Directed discrete midpoint convexity

摘要

For continuous functions, midpoint convexity characterizes convex functions. By considering discrete versions of midpoint convexity, several types of discrete convexities of functions, including integral convexity, L.-convexity and global/local discrete midpoint convexity, have been studied. We propose a new type of discrete midpoint convexity that lies between L.-convexity and integral convexity and is independent of global/local discrete midpoint convexity. The new convexity, named DDM-convexity, has nice properties satisfied by L.-convexity and global/local discrete midpoint convexity. DDM-convex functions are stable under scaling, satisfy the so-called parallelogram inequality and a proximity theorem with the same small proximity bound as that for L.-convex functions. Several characterizations of DDMconvexity are given and algorithms for DDM-convex function minimization are developed. We also propose DDM-convexity in continuous variables and give proximity theorems on these functions.