“sidca2003/9
page xPreface“Discrete Convex Analysis” is aimed at establishing a novel theoretical framework for solvable discrete optimization problems by means of a combination of theideas in continuous optimization and combinatorial optimization. The theoreticalframework of convex analysis is adapted to discrete settings and the mathematical results in matroid/submodular function theory are generalized. Viewed fromthe continuous side, the theory can be classified as a theory of convex functions
f : Rn → R that have additional combinatorial properties. Viewed from the discrete side, it is a theory of discrete functions f : Zn → Z that enjoy certain niceproperties comparable to convexity. Symbolically,
Discrete Convex Analysis = Convex Analysis + Matroid Theory.
The theory puts emphasis on duality and conjugacy as well as on algorithms. This
results in a novel duality framework for nonlinear integer programming.
Two convexity concepts, called L-convexity and M-convexity, play primaryroles, where “L” stands for “Lattice” and “M” for “Matroid.” L-convex functions
and M-convex functions are convex functions with additional combinatorial properties distinguished by “L” and “M,” and they are conjugate to each other througha discrete version of the Legendre–Fenchel transformation. L-convex functions andM-convex functions generalize, respectively, the concepts of submodular set functions and base polyhedra of (poly)matroids.
L-convexity and M-convexity prevail in discrete systems.
• In network flow problems, flow and tension are dual objects. Roughly speaking, flow corresponds to M-convexity and tension to L-convexity.
• In matroids, the rank function corresponds to L-convexity and the base familyto M-convexity.
• M-matrices in matrix theory correspond to L-convexity, and their inverses
to M-convexity. Hence, in a discretization of the Poisson problem of partial
differential equations, for example, the differential operator corresponds toL-convexity and the Green function to M-convexity.
• Dirichlet forms in probability theory are essentially the same as quadratic
L-convex functions.
The present book is intended to be read profitably by graduate students inoperations research, mathematics, and computer science, and also by mathematicsxxi

“sidca2003/9
page xxxii

Prefaceoriented practitioners and application-oriented mathematicians. Self-contained presentation is envisaged. In particular, no familiarity with matroid theory nor withconvex analysis is assumed. On the contrary, the reader will hopefully acquire aunified view on matroids and convex functions through a variety of examples of
discrete systems and the axiomatic approach presented in this book.
I would like to express my appreciation for encouragement, support, help,and criticism that I have received during my research on the theory of “Discrete
Convex Analysis.” Joint works with Akiyoshi Shioura and Akihisa Tamura havebeen most substantial, and collaborations with Satoru Fujishige, Satoru Iwata,Gleb Koshevoy, and Satoko Moriguchi enjoyable. Moral support offered by BillCunningham, András Frank and Láci Lovász has been encouraging. I have benefited from discussions with and/or comments by Andreas Dress, Atsushi Kajii,Mamoru Kaneko, Takahiro Kawai, Takashi Kumagai, Tomomi Matsui, Makoto
Matsumoto, Shiro Matuura, Tom McCormick, Yoichi Miyaoka, Kiyohito Nagano,Maurice Queyranne, András Recski, András Sebő, Maiko Shigeno, Masaaki Sugihara, Zoltan Szigeti, Takashi Takabatake, Yoichiro Takahashi, Tamaki Tanaka,
Fabio Tardella, Levent Tunçel, Jens Vygen, Jun Wako, Walter Wenzel, Yoshitsugu
Yamamoto, and Zaifu Yang. In preparing this book I have been supported by several friends. Among others, Akiyoshi Shioura and Akihisa Tamura went throughthe text and provided comments, and Satoru Iwata agreed that his unpublished results be included in this book. Significant part of this book is based on my previous
book [147] in Japanese published from Kyoritsu Publishing Co. Finally, I express
my deep gratitude to Peter Hammer, the chief editor of this monograph series, for
his support in the realization of this book.
October 2002

Kazuo Murota