A note on discrete convexity and local optimality. (English) Zbl 1105.90073

Summary: One of the most important properties of a convex function is that a local optimum is also a global optimum. This paper explores the discrete analogue of this property. We consider arbitrary locality in a discrete space and the corresponding local optimum of a function over the discrete space. We introduce the corresponding notion of discrete convexity and show that the local optimum of a function satisfying the discrete convexity is also a global optimum. The special cases include discretely-convex, integrally-convex, \(M\)-convex, \(M^\#\)-convex, \(L\)-convex, and \(L^\#\)-convex functions.


90C27 Combinatorial optimization
91A40 Other game-theoretic models
Full Text: DOI


[1] E. Altman, B. Gaujal and A. Hordijk, Multimodularity, convexity, and optimization properties. Mathematics of Operations Research,25 (2000), 324–347. · Zbl 0977.90005
[2] M. Avriel, W.E. Diewert, S. Schaible and I. Zang, Generalized Concavity. Plenum Press, New York, 1988.
[3] P. Favati and F. Tardella, Convexity in nonlinear integer programming. Ricerca Operativa,53 (1990), 3–44.
[4] S. Fujishige and K. Murota, Notes on L-/M-convex functions and the separation theorems. Mathematical Programming,88 (2000), 129–146. · Zbl 0974.90019
[5] B.L. Miller, On minimizing nonseparable functions defined on the integers with an inventory application. SIAM Journal on Applied Mathematics,21 (1971), 166–185. · Zbl 0224.90049
[6] D. Monderer and L.S. Shapley, Potential games. Games and Economic Behavior,14 (1996), 124–143. · Zbl 0862.90137
[7] K. Murota, Convexity and Steinitz’s exchange property. Advances in Mathematics,124 (1996), 272–311. · Zbl 0867.90092
[8] K. Murota, Discrete convex analysis. Mathematical Programming,83 (1998), 313–371. · Zbl 0920.90103
[9] K. Murota, Algorithms in discrete convex analysis. IEICE Transactions on Systems and Information,E83-D (2000), 344–352.
[10] K. Murota, Discrete Convex Analysis, SIAM, Philadelphia, 2003. · Zbl 1029.90055
[11] K. Murota, Note on multimodularity and L-convexity. Mathematics of Operations Research, (2005), in press. · Zbl 1082.90071
[12] K. Murota and A. Shioura, M-convex function on generalized polymatroid. Mathematics of Operations Research,24 (1999), 95–105. · Zbl 0977.90044
[13] K. Murota and A. Shioura, Quasi M-convex and L-convex functions: Quasiconvexity in discrete optimization. Discrete Applied Mathematics,131 (2003), 467–494. · Zbl 1030.90085
[14] T. Ui, Discrete concavity for potential games. Working Paper, Yokohama National University, 2004.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.