This first monograph on discrete convex analysis has the main goal to establish a novel theoretical framework for solvable discrete optimization problems by means of a combination of the ideas in continuous and combinatorial optimization. More precisely, tools from convex analysis and matroid theory are combined. The major convexity concepts in this book are L-convexity (where “L” stands for lattice) and M-convexity (where “M” stands for matroid). The definition of L-convex functions is obtained from a generalization of the Lovász extension of submodular set functions. Beside a submodularity condition, L-convex functions have to be linear with respect to translation in the direction of \(1\). M-convex functions are motivated by a generalization of the simultaneaous exchange property of base polyhedra. Moreover, L-convex and M-convex functions enjoy a conjugacy relationship with respect to the discrete Legendre-Fenchel transformation.
The book is divided into 12 chapters. In the first chapter central concepts like convex functions, submodular functions and base polyhedra are introduced. Moreover, definitions and properties of L-convex and M-convex functions are given. This part is a kind of preview of what will be explained in more detail in later chapters. Chapter \(2\) is devoted to convex functions with combinatorial structures. Here, quadratic functions, nonlinear networks, substitutes and complements in network flows and matroids are discussed. The next chapters deals with convex analysis, linear programming and integrality. A detailed introduction to M-convex sets and the relation to submodular set functions is the main topic of Chapter \(4\). In Chapter \(5\) L-convex sets are introduced and their relationship to distance functions is discussed. Chapter \(6\) and Chapter \(7\) are devoted to the properties of M-convex and L-convex functions. Conjugacy and duality for the introduced convexity concepts are treated in Chapter \(8\). In Chapter \(9\) the application of discrete convex analysis to network flows is discussed. Chapter \(10\) is devoted to algorithms for dealing with discrete convex functions and Chapter \(11\) presents an application to mathematical economics. The last chapter deals with an application to system analysis by mixed matrices.
Each chapter has at the end some very useful bibliographical notes. The book contains more than 400 pages and lists 222 references. It is very well written and clearly structured. However, it has a quite theoretical focus and does nearly give no examples to illustrate the results.