The concept of M-convex functions has recently been generalized for functions defined on constant-parity jump systems. The b-matching problem and its generalization provide canonical examples of M-convex functions on jump systems. In this paper, we propose a steepest descent algorithm for minimizing an M-convex function on a constant-parity jump system.

L-convex functions are nonlinear discrete functions on integer points that are computationally tractable in optimization. In this paper, a discrete Hessian matrix and a local quadratic expansion are defined for L-convex functions. We characterize L-convex functions in terms of the discrete Hessian matrix and the local quadratic expansion.

The concepts of M-convexity and L-convexity, introduced by Murota (1996, 1998) for functions on the integer lattice, extract combinatorial structures in well-solved nonlinear combinatorial optimization problems. These concepts are extended to polyhedral convex functions and quadratic functions on the real space by Murota-Shioura (2000, 2001). In this paper, we consider a further extension to general convex functions. The main aim of this paper is to provide rigorous proofs for fundamental properties of general M-convex and L-convex functions.

M-convex functions have various desirable properties as convexity in discrete optimization. We can find a global minimum of an M-convex function by a greedy algorithm, i.e., so-called descent algorithms work for the minimization. In this paper, we apply a scaling technique to a greedy algorithm and propose an efficient algorithm for the minimization of an M-convex function. Computational results are also reported.

This note investigates the characterizing properties of the level sets of an M-convex function introduced by Murota.

This is a survey of algorithmic results in the theory of "discrete convex analysis" for integer-valued functions defined on integer lattice points. The theory parallels the ordinary convex analysis, covering discrete analogues of the fundamental concepts such as conjugacy, the Fenchel min-max duality, and separation theorems. The technical development is based on matroid-theoretic concepts, in particular, submodular functions and exchange axioms.