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

Ui, Takashi

Japan J. Ind. Appl. Math. 23, No. 1, 21-29 (2006).

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.

MSC:

90C27	Combinatorial optimization
91A40	Other game-theoretic models

Keywords:

discrete optimization; convex function; quasiconvex function; Nash equilibrium; potential game

References:

[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.