The Properties Of Discrete M-/L-convex Functions And Their Applications

Duality theorem plays an important role in general convex analysis theorem, many nonlinear programming problems may get solution by solving their dual problems. but things seems not so easy while applying the continuous to discrete function theory, because of the lack of definitions like neighbourhood、local minimum and so on, Thus, much of proper-ties don’t hold already, besides, we can’t explain the duality theorem, it is difficult to solve discrete nonlinear programming problems.Thus, discrete convex analysis become be taken seriously by people. Murota put for-ward the definition of M-convex and L-convex which is based on submodular and exchange axiom. It is defined on integer lattice, and different from the general convex functions. People was happy to find that they parallels the ordinary convex analysis, containing properties such as conjugacy, subdifference, separating theorem and Lagrange duality theorem etc which is analogues to the ordinary convex analysis. Besides, M-/L-convex functions are close to submodular functions, especially L-convex function. At the supposition of submodular and multimodular, we can get the local optimal conditions.Later people find that discrete convex functions could extend to polyhedral convex func-tions and quadratic functions, even to more general M/L-convex functions, and they have good duality properties, being the same form with duality theorem of continuous convex functions. Unfortunately, the proof can’t be extended so directly, but we now have strictly proved the conclusion. More important, discrete convex functions is widely used in real life such as mathematical economical models, discrete inventory models of logistics manage-ment etc. People can use M/L-convex and their generated discrete convex functions to solve practical problems.This article mainly summarized results obtained by Murota and Shioura, introduced definitions of discrete convex functions and their primly properties such as biconjugate, conjugacy between M-convex functions and L-convex functions and the separating theo-rem、week duality. At the end of this article, we put several examples about discrete convex functions.