Chapter 1

Main Features of Discrete Convex Analysis(COSS 2018 Reading Material)

Kazuo Murota (June 21, 2018)

1.1 Aim of Discrete Convex Analysis
Convex functions appear in many mathematical models in engineering, operations
research, economics, game theory, and other sciences. The concept of convex functions is explained most easily by examples. The function in Fig. 1.1 (a) is convex
and that in Fig. 1.1 (b) is not.
f (x)(a) Convex functionf (x)(b) Nonconvex function

Fig. 1.1 Convex and nonconvex functions

A formal definition of convex functions is as follows. We denote the set of real
numbers by R and let R denote the set R ∪ {+∞}. A function f : Rn → R is said tobe convex if
λ f (x) + (1 − λ ) f (y) ≥ f (λ x + (1 − λ )y)(1.1)
holds for all x, y ∈ Rn and for all λ with 0 ≤ λ ≤ 1, where it is understood that
this inequality is satisfied if f (x) or f (y) is equal to +∞. Figure 1.2 illustrates thisinequality; the point correponds to the left-hand side of (1.1) and to the righthand side. Alternatively, we can say that a function f is convex if and only if, for3

4

1 Main Features of Discrete Convex Analysis(COSS 2018 Reading Material)

any x and y, the line segment connecting (x, f (x)) and (y, f (y)) lies above the graphof f .
f 6

λ f (x) + (1 − λ ) f (y)f (λ x + (1 − λ )y)x

λ x + (1 − λ )yy-Fig. 1.2 Definition of convex functions

Figure 1.3 illustrates the failure of inequality (1.1) for the function in Fig. 1.1 (b).
Again the point correponds to the left-hand side of (1.1) and to the right-hand
side.
f 6
f (λ x + (1 − λ )y)λ f (x) + (1 − λ ) f (y)xλ x + (1 − λ )yy-Fig. 1.3 Failure of the convexity condition

Convex functions are amenable to minimization. An obvious reason for this isthat a local minimizer of a convex function is guaranteed to be a global minimizer.
To put it more precisely, let x ∈ Rn be a point at which f is finite. If the inequality
f (x) ≤ f (y) holds for every y in some neighborhood of x, then the same inequality
holds for all y ∈ Rn . This property enables us to design descent-type algorithms forcomputing the minimum of a convex function. It should be clear that, for nonconvex
functions, local minimality does not imply global minimality. In Fig. 1.4 (b), forexample, there are two local minimizers ( , ) of which is a global minimizer andis not. On the other hand, the convex function in Fig. 1.4 (a) has only one local
minimizer, which is also a global minimizer.
Convex analysis lays the foundation for theoretical and algorithmic treatment of
convex functions. Besides the equivalence of local and global minimalities men-1.1 Aim of Discrete Convex Analysisf (x)(a) Convex function

5
f (x)

(b) Nonconvex function

Fig. 1.4 Local and global minimizers of convex and nonconvex functions

tioned above, there are much deeper reasons why convex functions are tractable inoptimization (minimization), namely, duality phenomena such as conjugacy, biconjugacy, min-max relations, and separation theorems. Indeed, duality is one of thecentral issues in convex analysis. Convex analysis is also indispensable in dealing
with nonconvex functions.
Discrete convex analysis is aimed at providing an analogous theoretical framework for discrete functions through a combination of convex analysis and the theoryof networks and matroids in discrete optimization. Primarily, it is a theory of functions f : Zn → R in discrete variables that enjoy certain nice properties comparable
to convexity. At the same time, it is a theory of convex functions f : Rn → R in
continuous variables that have additional combinatorial properties.
In defining convexity concepts for functions in discrete variables, it would benatural to expect the following properties:
1. Local minimality guarantees global minimality.
2. Duality theorems such as conjugacy, biconjugacy, min-max relations, and separation theorems hold.
In discrete convex analysis, two convexity concepts, called L-convexity and Mconvexity are defined, where “L” stands for “Lattice” and “M” for “Matroid.” Lconvex functions and M-convex functions are endowed with the above nice properties and they are conjugate to each other through the (continuous or discrete)
Legendre–Fenchel transformation.
The objective of this chapter is to present an overall picture on the most importantconcepts and properties of discrete convex functions. In Section 1.2 we identity
major issues to be addressed in discrete convex analysis by considering discrete
convex functions in one variable. Definitions and properties of multivariate discrete
convex functions are outlined in Sections 1.3 and 1.4.
Although discrete convex analysis is inspired by concepts and results in convex
analysis and combinatorial optimization, familiarity with these areas is not necessary in reading this book. Elementary facts in convex analysis used in this book arepresented in Chapter 2, while the interested reader is referred to [2,3,4,27,36,65] formore details of convex analysis. Concerning combinatorial optimization, the reader
is referred to [64, 72] for matroids, [5, 13, 35, 66] for combinatorial optimization,and [16, 71] for submodular function theory.

6

1 Main Features of Discrete Convex Analysis(COSS 2018 Reading Material)

1.2 Univariate Discrete Convex Functions
In this section we investigate discrete convexity for univariate functions (functions
in one variable). Univariate discrete convex functions are easy to analyze and usefulas a prototype of discrete convex functions. In so doing we intend to identify thegeneral issues to be addressed in discrete convex analysis for multivariate functions.

1.2.1 Definition
We denote the set of all real numbers by R and the set of all integers by Z. We also
use notations R = R ∪ {+∞}, R = R ∪ {−∞}, Z = Z ∪ {+∞}, and Z = Z ∪ {−∞}.
We consider functions f that are defined on integers Z and take values in R ∪{−∞, +∞}. The effective domain of f , to be denoted as dom f , is defined as the setof points at which the value of f is finite:1
dom f = domZ f = {x ∈ Z | −∞ < f (x) < +∞}.

(1.2)

A function f : Z → R is said to be a discrete convex function (or simply convex
function) if dom f ̸= 0/ and2
f (x − 1) + f (x + 1) ≥ 2 f (x)(∀x ∈ Z),

(1.3)

where it is understood that this inequality is satisfied trivially if f (x − 1) = +∞ orf (x + 1) = +∞. It follows from (1.3) that the effective domain dom f is a nonempty
integer interval (see Remark 1.1), since f (x − 1) < +∞ and f (x + 1) < +∞ imply
f (x) < +∞. The inequality (1.3) can be rewritten as
f (x) − f (x − 1) ≤ f (x + 1) − f (x)(∀x ∈ dom f ),(1.4)

showing the monotonicity (non-decreasingness) of the difference f (x + 1) − f (x) on
dom f . Thus, the discrete convexity of a function f is characterized by the monotonicity of the difference.
Naturally, we say that g : Z → R is a discrete concave function if −g : Z → R isa discrete convex function. That is, g : Z → R is a discrete concave function if andonly if dom g ̸= 0/ andg(x − 1) + g(x + 1) ≤ 2g(x)(∀x ∈ Z).

(1.5)

Remark 1.1. An integer interval means the set of integers in an interval. A finite
integer interval is a set of the form {x ∈ Z | a ≤ x ≤ b} for some a, b ∈ Z. An infinite

1 We sometimes use dom f for dom f to emphasize that it is a subset of Z.
Z
2 Symbol ∀ in (1.3) means “for all”, “for any,” or “for each.”1.2 Univariate Discrete Convex Functions

7

integer interval is a set of the form {x ∈ Z | a ≤ x < +∞}, {x ∈ Z | −∞ < x ≤ b}, or{x ∈ Z | −∞ < x < +∞} for some a, b ∈ Z.
In the following sections, we demonstrate that major nice features of convex
functions in continuous variables are shared by functions in discrete variables satisfying (1.3).

1.2.2 Convex extension
For any function f : Z → R in a single discrete variable, we can associate apiecewise-linear function f˜ : R → R in a continuous variable by connecting consecutive points (x, f (x)) and (x + 1, f (x + 1)) by line segments for all x ∈ Z as inFig. 1.5. This function f˜ is called the piecewise-linear extension of f . It is easy
to see that a function f is discrete convex (1.3) if and only if its piecewise-linear
extension f˜ is convex (1.1).
f 6

f 6

-

-

x

x

(a) Convex(b) Nonconvex

Fig. 1.5 Piecewise-linear extension and convex extensibility

A function f : Z → R is said to be convex-extensible if there exists a convex
function f : R → R in a continuous variable such thatf (x) = f (x)(∀x ∈ Z).

(1.6)

Such f is called a convex extension of f . A convex extension may not be unique.
Fig. 1.6 shows an example of two different convex extensions for the same function.
A convex-extensible function f is discrete convex, sincef (x − 1) + f (x + 1) = f (x − 1) + f (x + 1) ≥ 2 f (x) = 2 f (x)by (1.6) and the convexity of f . Conversely, a discrete convex function f is convexextensible, since its piecewise-linear extension f˜ serves as a convex extension f .
Thus discrete convexity (1.3) is equivalent to convex-extensibility (1.6), which fact
is stated as a theorem below. We emphasize that such a simple characterization of
convex-extensibility is valid only for functions in a single variable.

8

1 Main Features of Discrete Convex Analysis
f 6(COSS 2018 Reading Material)
f 6

x

x

Fig. 1.6 Two different convex extensions of the same function

Theorem 1.1. A univariate function f : Z → R is convex-extensible if and only if itsatisfies (1.3).

1.2.3 Minimization
Probably the most appealing property of a convex function is the equivalence of
local minimality and global minimality.
The following is a natural analogue of this equivalence for univariate discrete
convex functions, where x ∈ Z is said to be a (global) minimizer of f : Z → R if
f (x) ≤ f (y) for all y ∈ Z.
Theorem 1.2. For a univariate discrete convex function f : Z → R, an integer x ∈dom f is a global minimizer of f if and only if it is a local minimizer in the sensethatf (x) ≤ min{ f (x − 1), f (x + 1)}.
(1.7)
Proof. The “only-if” part is obvious. Although the “if” part is also easy to see, a formal proof is as follows. Since f (x+1)− f (x) ≥ 0 by (1.7), it follows from the monotonicity (1.4) of the difference that f (x + k + 1) − f (x + k) ≥ 0 for k = 0, 1, 2, . . ..
Hence, if y > x, we have f (y) ≥ f (y − 1) ≥ · · · ≥ f (x + 1) ≥ f (x). Similarly, if y < x,
we have f (y) ≥ f (y + 1) ≥ · · · ≥ f (x − 1) ≥ f (x), since f (x − k − 1) − f (x − k) ≥f (x − 1) − f (x) ≥ 0 for k = 0, 1, 2, . . . by (1.4) and (1.7). Therefore, f (y) ≥ f (x) for
all y ∈ Z. ⊓⊔The local characterization of global minimality naturally leads to descent-type
algorithms for minimization.
Remark 1.2. An alternative proof of Theorem 1.2 could be obtained by considering
the piecewise-linear extension f˜ of f , as in Fig. 1.5 (a), and applying to f˜ the local
characterization of global minimality for convex functions in continuous variables.
In this section, however, we intentionally avoid using convex extensions to prove
theorems for univariate discrete convex functions.

1.2 Univariate Discrete Convex Functions

9

1.2.4 Conjugacy
For any function f : R → R in a continuous variable, whether convex or not, thefunction f • : R → R defined byf • (p) = sup{px − f (x) | x ∈ R}

(p ∈ R)(1.8)

is called the (convex) conjugate of f , where dom f ̸= 0/ is assumed. For a geometricinterpretation, consider the graph y = f (x) and the tangent line with slope p (seeFig. 1.7). Then − f • (p) is equal to the y-intercept of this tangent line.
y 6
f (x)

− f • (p)slope px

Fig. 1.7 Geometric meaning of the Legendre–Fenchel transformation

The function f • is also referred to as the (convex) Legendre–Fenchel transform(or simply Legendre transform) of f , and the mapping f 7→ f • as the (convex)
Legendre–Fenchel transformation (or simply Legendre transformation). The conjugate function of the conjugate of f , i.e., ( f • )• , is called the biconjugate of f anddenoted as f •• . See Section 2.4 for more about the Legendre–Fenchel transformation.
It is known in convex analysis3 that for any function f , the conjugate f • is aconvex function, and the biconjugate f •• is (essentially) the largest convex function that is dominated pointwise by f . In particular, for a convex function f , thebiconjugate f •• coincides with f itself (under some regularity assumption). Therefore, the Legendre–Fenchel transformation establishes a symmetric (or involutive)
one-to-one correspondence within the class of all (univariate) convex functions.
For a function f : Z → R in an integer variable, the discrete version of the
Legendre–Fenchel transformation can be defined asf • (p) = sup{px − f (x) | x ∈ Z}

(p ∈ R);(1.9)

recall that domZ f ̸= 0/ is assumed. The function f • : R → R is called the (convex)
conjugate of f . For any function f : Z → R, which may or may not satisfy (1.3),
the conjugate function f • : R → R is a convex function. We call (1.9) the (convex)
discrete Legendre–Fenchel transformation.
For an integer-valued function f on Z, the value of f • (p) for integral p is an
integer, since both px and f (x) are integers in (1.9). Hence (1.9) with p ∈ Z defines
3 See Theorem 2.2 in Section 2.4 for precise statements involving the condition of “closedness.”

10

1 Main Features of Discrete Convex Analysis(COSS 2018 Reading Material)a transformation of f : Z → Z to f • : Z → Z. For later reference, (1.9) with p ∈ Z is
explicitly written here:f • (p) = sup{px − f (x) | x ∈ Z}

(p ∈ Z).

(1.10)

This function f • is referred to as the integral conjugate of f , and the mapping f 7→
f • of (1.10) as the fully-discrete or fully-integral Legendre–Fenchel transformation.
We can apply (1.10) twice to obtain f •• = ( f • )• , which is referred to as the integral
biconjugate of f .
The conjugacy theorem for univariate discrete convex functions reads as follows.
Theorem 1.3. For an integer-valued univariate discrete convex function f : Z →Z, the integral conjugate f • in (1.10) is another integer-valued univariate discrete
convex function. Furthermore, the integral biconjugate f •• coincides with f itself,i.e., f •• = f .
Proof. The proof consists of three parts.
[Discrete convexity (1.3) of f • ]: The addition of the two expressionsf • (p − 1) = sup{(p − 1)x − f (x)},xf • (p + 1) = sup{(p + 1)x − f (x)}
x

(
) (
)
yields f • (p − 1) + f • (p + 1) ≥ supx { (p + 1)x − f (x) + (p − 1)x − f (x) } =2 supx {px − f (x)} = 2 f • (p).
[ f •• ≤ f ]: For any x, p ∈ Z we have f • (p) ≥ px − f (x) by (1.10), and hencepx − f • (p) ≤ f (x). Therefore, f •• (x) = sup p {px − f • (p)} ≤ f (x).
[ f •• ≥ f ]: First we assume x ∈ dom f . Take an integer p satisfying f (x) − f (x −1) ≤ p ≤ f (x + 1) − f (x), which is possible by (1.4) and the integrality of thefunction value. Consider the function h(y) = f (y) − py in y ∈ Z. Then we haveh(x) ≤ min{h(x − 1), h(x + 1)}. This implies, by Theorem 1.2, that h(x) ≤ h(y) for
all y ∈ Z, which is equivalent to px − f (x) ≥ py − f (y) (y ∈ Z). Hence we havepx − f (x) = supy {py − f (y)} = f • (p). Therefore, f •• (x) = supq {qx − f • (q)} ≥px − f • (p) = f (x).
Next we consider the case of x ̸∈ dom f . We assume that dom f is an integer interval [a, b]Z with b finite and x ≥ b + 1; the other case with a finite andx ≤ a − 1 can be treated similarly. For all sufficiently large p ∈ Z, say p ≥ p0 , wehave f • (p) = pb − f (b). Therefore, f •• (x) = sup p∈Z {px − f • (p)} ≥ sup p≥p0 {px −f • (p)} = sup p≥p0 {p(x − b) + f (b)} = +∞. ⊓⊔Theorem 1.3 above shows that the fully-integral Legendre–Fenchel transformation (1.10) establishes a symmetric (or involutive) one-to-one correspondence
within the class of all integer-valued univariate discrete convex functions.
Example 1.1. The Legendre–Fenchel transformation is illustrated for a quadratic
function f (x) = x2 in continuous and discrete variables. In the continuous case withx ∈ R, we havef • (p) = sup{px − x2 | x ∈ R} =

1 2
p
4

(p ∈ R)1.2 Univariate Discrete Convex Functions

11

by (1.8). In the discrete case with x ∈ Z, the discrete Legendre–Fenchel transformation (1.9) givesf • (p) = sup{px − x2 | x ∈ Z}
= max{px − x2 | x ∈ {⌊p/2⌋ , ⌈p/2⌉}}{⌊ p ⌋ (⌊ p⌋) ⌈ p⌉(⌈ p ⌉ )}
= max
p−
,
p−
2
2
2
2

(p ∈ R).

This is a piecewise-linear convex function whose graph consists of line segments
connecting (2k − 1, k2 − k) and (2k + 1, k2 + k) for k ∈ Z. In the fully discrete casewith x ∈ Z and p ∈ Z, we obtain the integral conjugate⌊ p⌋ ⌈ p⌉·(p ∈ Z),f • (p) =22⌊ p⌋ ⌈ p⌉+= p for an integer p. The integral biconjugacy f •• = f stated in
since
2
2
Theorem 1.3 is given as the identity{⌊ p⌋ ⌈ p⌉}
sup px −·| p ∈ Z = x2
(x ∈ Z),22
which can be verified easily.
For a general (not necessarily discrete convex) function f we have the following
statement about f • and f •• .
Proposition 1.1. For any integer-valued univariate function f : Z → Z, the integral
conjugate f • in (1.10) is an integer-valued discrete convex function, and the integral biconjugate f •• is the largest integer-valued discrete convex function such thatf •• (x) ≤ f (x) for all x ∈ Z.
Proof. In view of the proof of Theorem 1.3 it remains to prove that f •• is the largest
such function. Let g : Z → Z be any integer-valued univariate discrete convex function satisfying g(x) ≤ f (x) for all x ∈ Z. By (1.10) we have g• (p) ≥ f • (p) for allp ∈ Z. This implies, again by (1.10), that g•• (x) ≤ f •• (x) for all x ∈ Z. Here wehave g•• (x) = g(x) by Theorem 1.3. Therefore, g(x) ≤ f •• (x) for all x ∈ Z. ⊓⊔Example 1.2. Proposition 1.1 is illustrated for a simple nonconvex function. Let f
be defined by f (0) = 0, f (1) = f (2) = 3, and f (x) = +∞ for x ̸∈ {0, 1, 2}. A direct
calculation using the fully-integral Legendre–Fenchel transformation (1.10) showsf • (p) = max{px − f (x) | x ∈ {0, 1, 2}} = max{0, 2p − 3}(p ∈ Z),0 (x = 0),1(x = 1),f •• (x) = sup{px − max{0, 2p − 3} | p ∈ Z} =3(x = 2),+∞ (x ∈ Z \ {0, 1, 2}).

12

1 Main Features of Discrete Convex Analysis(COSS 2018 Reading Material)

This function f •• is indeed the largest integer-valued discrete convex function satisfying f •• (x) ≤ f (x) for all x ∈ Z. However, if no integrality is imposed on the function value, the largest discrete convex function g : Z → R satisfying g(x) ≤ f (x) for
all x ∈ Z is given by: g(0) = 0, g(1) = 3/2, g(2) = 3, and g(x) = +∞ for x ̸∈ {0, 1, 2}.

1.2.5 Discrete separation theorem
The separation theorem for functions in a continuous variable asserts the existenceof an affine function that lies between a convex function and a concave function(Fig. 1.8). While precise technical conditions are specified in Theorem 2.3 in Section 2.5, the separation theorem can be stated roughly as follows.
Theorem 1.4. Let f : R → R be a convex function and g : R → R be a concave
function (satisfying certain regularity conditions). If f (x) ≥ g(x) for all x ∈ R, there
exist α ∗ ∈ R and p∗ ∈ R such thatf (x) ≥ α ∗ + p∗ x ≥ g(x)(∀x ∈ R).

(1.11)f (x)α ∗ + p∗ xg(x)Fig. 1.8 Separation theorem for functions in a continuous variable

For discrete convex and concave functions we have the following discrete separation theorem, which is a discrete counterpart of Theorem 1.4. Discreteness isincorporated twofold in the theorem. The first statement of Theorem 1.5 is concerned with discreteness in the variable in that “x ∈ R” in Theorem 1.4 is changed
to “x ∈ Z.” The second statement is concerned with discreteness in function values
in that the separating affine function is described by integral α ∗ and p∗ for integervalued functions f and g. Figure 1.9 illustrates the integer-valued case.
Theorem 1.5. Let f : Z → R be a discrete convex function and g : Z → R be adiscrete concave function. If f (x) ≥ g(x) for all x ∈ Z, there exist α ∗ ∈ R and p∗ ∈ Rsuch that(∀x ∈ Z).
(1.12)
f (x) ≥ α ∗ + p∗ x ≥ g(x)

1.2 Univariate Discrete Convex Functions

13

f (x)

α ∗ + p∗ x

g(x)
f (x)

α ∗ + p∗ xg(x)(a) dom f ∩ dom g ̸= 0/(b) dom f ∩ dom g = 0/

Fig. 1.9 Discrete separation theorem

Moreover, if f and g are integer-valued, there exist integral α ∗ ∈ Z and p∗ ∈ Z.
Proof. (The claim will be intuitively obvious from Fig. 1.9, but we give a formal
detailed proof for interested readers.) Assume that domZ f ∩ domZ g ̸= 0;/ the casewith domZ f ∩domZ g = 0/ is treated at the end of the proof. Define h(x) = f (x)−g(x)for x ∈ Z and ∆ = inf{h(x) | x ∈ Z}. Note that h is a discrete convex function and ∆is finite and nonnegative by the assumption.
First suppose that the infimum ∆ is attained and let z be a minimizer of h. Let
F + = f (z + 1) − f (z), F − = f (z) − f (z − 1), G+ = g(z + 1) − g(z), and G− = g(z) −g(z − 1). We have F + ≥ G+ and F − ≤ G− by h(z + 1) ≥ h(z) and h(z − 1) ≥ h(z),respectively, whereas F − ≤ F + and G− ≥ G+ by (1.4). Hence max(F − , G+ ) ≤min(F + , G− ), which implies that there exists p∗ ∈ R satisfying4
max(F − , G+ ) ≤ p∗ ≤ min(F + , G− ).

(1.13)Let α ∗ = f (z) − p∗ z. Then g(z) − p∗ z ≤ f (z) − p∗ z = α ∗ . Since F − ≤ p∗ ≤ F + , wehave f (y) − f (z) ≥ p∗ (y − z) for all y ∈ Z, i.e., f (y) − p∗ y ≥ f (z) − p∗ z = α ∗ forall y ∈ Z. Similarly, since G+ ≤ p∗ ≤ G− , we have g(y) − g(z) ≤ p∗ (y − z) for ally ∈ Z, i.e., g(y) − p∗ y ≤ g(z) − p∗ z ≤ f (z) − p∗ z = α ∗ for all y ∈ Z. Therefore, we
obtain f (y) − p∗ y ≥ α ∗ ≥ g(y) − p∗ y for all y ∈ Z, which is equivalent to (1.12).
Next suppose that the infimum ∆ is not attained.5 Then either limx→−∞ h(x) = ∆or limx→+∞ h(x) = ∆ . We consider the latter case only, as the former case can betreated similarly. Then we have limx→+∞ (h(x + 1) − h(x)) = 0. Since h(x + 1) −h(x) = ( f (x + 1) − f (x)) − (g(x + 1) − g(x)) with f (x + 1) − f (x) nondecreasing
and g(x + 1) − g(x) nonincreasing, we havelim ( f (x + 1) − f (x)) = lim (g(x + 1) − g(x)) = p∗

x→+∞

x→+∞

4 Using the notation of subgradients (Section 16.6), the condition (1.13) can be expressed as p∗ ∈∂ f (z) ∩ ∂ (−g)(z).
5 For example, such case occurs for f (x) = x +2+exp(−x) and g(x) = x −exp(−2x). The infimum∆ is equal to 2, but it is not attained. The proof yields p∗ = 1 and α ∗ = 2.

14

1 Main Features of Discrete Convex Analysis(COSS 2018 Reading Material)for some p∗ ∈ R. Let α ∗ = limy→+∞ ( f (y) − p∗ y). Since f (x) − p∗ x is nonincreasing
in x, we obtain f (x) − p∗ x ≥ α ∗ for all x ∈ Z. Similarly, since g(x) − p∗ x is nondecreasing in x, we obtain g(x) − p∗ x ≤ limy→+∞ (g(y) − p∗ y) ≤ limy→+∞ ( f (y) −p∗ y) = α ∗ for all x ∈ Z. Therefore, (1.12) holds.
For integer-valued f and g, the infimum of h = f − g is always attained and F − ,+F , G+ , and G− are integers. Hence we can choose an integral p∗ in (1.13), andthen α ∗ = f (z) − p∗ z is also integral.
It remains to treat the case of domZ f ∩ domZ g = 0.
/ We only consider the casewhere domZ f = [a, b]Z and domZ g = [c, d]Z with b + 1 ≤ c. The inequality (1.12)
holds if p∗ ≥ max{ f (b)− f (b−1), g(c+1)−g(c), (g(c)− f (b))/(c−b)} and α ∗ =f (b) − p∗ b. For integer-valued f and g, we can choose integral p∗ and α ∗ . ⊓⊔As we have seen above, the discrete separation theorem for univariate discrete
convex functions is a fairly simple statement that can be proved without much difficulty. For multivariate discrete convex functions, however, the discrete separation
theorem is highly nontrivial and often captures deep combinatorial properties inspite of its apparent similarity to the separation theorem in convex analysis.

1.2.6 Fenchel-type duality theorem
For integer-valued discrete convex and concave functions f : Z → Z and g : Z → Z,
we consider the problem of minimizing f (x) − g(x) over x ∈ Z. For this problem wehave the following Fenchel-type min-max duality theorem. We define the concave
version of the fully-integral Legendre–Fenchel transformation asg◦ (p) = inf{px − g(x) | x ∈ Z}

(p ∈ Z).

(1.14)We have g◦◦ = g (integral biconjugacy) by Theorem 1.3, where g◦◦ denotes (g◦ )◦ .
Theorem 1.6. Let f : Z → Z be an integer-valued discrete convex function and g :Z → Z be an integer-valued discrete concave function such that domZ f ∩ domZ g ̸=
0/ or domZ f • ∩ domZ g◦ ̸= 0.
/ Then we haveinf{ f (x) − g(x) | x ∈ Z} = sup{g◦ (p) − f • (p) | p ∈ Z}.

(1.15)

If this common value is finite, the infimum and the supremum are attained.
Proof. Suppose that domZ f ∩ domZ g ̸= 0.
/ For any x, p ∈ Z we have f • (p) ≥ px −◦f (x) by (1.10) and g (p) ≤ px − g(x) by (1.14), and therefore, g◦ (p) − f • (p) ≤f (x) − g(x). This shows inf( f − g) ≥ sup(g◦ − f • ) (weak duality).
Let ∆ = inf{ f (x) − g(x) | x ∈ Z}, which is an integer or −∞. If ∆ = −∞,the weak duality implies sup(g◦ − f • ) = −∞ and hence (1.15). Suppose that ∆is finite. Then the infimum is attained since the functions are integer-valued. By
the discrete separation theorem (Theorem 1.5) for ( f − ∆ , g), there exist α ∗ ∈ Z
and p∗ ∈ Z such that f (x) − ∆ ≥ α ∗ + p∗ x ≥ g(x) for all x ∈ Z. This implies1.2 Univariate Discrete Convex Functions

15g◦ (p∗ ) − f • (p∗ ) ≥ (−α ∗ ) − (−α ∗ − ∆ ) = ∆ . Combined with the weak duality, thisshows (1.15) together with the attainment of the supremum by p∗ .
The other case with domZ f • ∩ domZ g◦ ̸= 0/ can be treated similarly by virtueof the integral biconjugacy f •• = f and g◦◦ = g. Indeed, by applying the above
argument to f • (p) and g◦ (p) we obtain inf{ f • (p) − g◦ (p) | p ∈ Z} = sup{g◦◦ (x) −f •• (x) | x ∈ Z}, which is equivalent to (1.15). ⊓⊔As the proof indicates, we can regard the Fenchel-type duality theorem as a corollary of the discrete separation theorem. The converse is also true and it may safely
be said that these two theorems are essentially equivalent to each other and capture
the same duality principle for univariate discrete convex functions.

1.2.7 Toward multivariate functions
In this section we have clarified the issues of our interest by considering univariate“discrete convex” functions. Fortunately, the natural definition of discrete convexity
by the inequality f (x − 1) + f (x + 1) ≥ 2 f (x) (∀x ∈ Z) in (1.3) entails the following
nice properties.
1. Convex-extensibility (Theorem 1.1),
2. Local characterization of global minimality (Theorem 1.2),
3. Conjugacy and biconjugacy under the fully-integral Legendre–Fenchel transformation (Theorem 1.3),
4. Discrete separation theorem (Theorem 1.5),
5. Fenchel-type min-max duality (Theorem 1.6).
Also for multivariate functions it would be natural to expect these five propertiesof “discrete convex” functions and, accordingly, the key question here is what shouldbe the definition of discrete convexity for multivariate functions in integer variables
that leads us to the desired properties. Discrete convex analysis answers this question by introducing two classes of discrete convex functions, called L-convex functions and M-convex functions, as well as their variants called L♮ -convex functions
and M♮ -convex functions.6 These classes of discrete convex functions are describedbriefly in Section 1.3 as a preview.

6 “L♮ ” and “M♮ ” should be read “ell natural” and “em natural,” respectively.

16

1 Main Features of Discrete Convex Analysis(COSS 2018 Reading Material)

1.3 Classes of Discrete Convex Functions
In this section we briefly introduce the major classes of multivariate discrete convex
functions defined on the integer lattice Zn , with particular reference to the following
five properties possessed by univariate discrete convex functions:
1. Convex-extensibility,
2. Local characterization of global minimality,
3. Conjugacy and biconjugacy for integer-valued functions under the fully-integral
Legendre–Fenchel transformation,
4. Discrete separation theorem,
5. Fenchel-type min-max duality for integer-valued functions.
In the following we briefly describe the definitions and properties of separable
convex, integrally convex, L-convex, L♮ -convex, M-convex, and M♮ -convex functions. A full-length description of these and other classes of discrete convex functions are given in Chapter 11.

1.3.1 General issues
For f : Zn → R ∪ {−∞, +∞}, the effective domain of f is defined as
dom f = domZ f = {x ∈ Zn | −∞ < f (x) < +∞}.

(1.16)We always assume that dom f is nonempty. The set of minimizers of f is denoted asargmin f = argminZ f = {x ∈ Zn | f (x) ≤ f (y) (∀y ∈ Zn )}.

(1.17)

Note that argmin f can possibly be an empty set.
Some definitions and remarks are in order concerning the above five properties. A
function f : Zn → R is said to be convex-extensible if there exists a convex function
f : Rn → R in continuous variables such thatf (x) = f (x)(∀x ∈ Zn ).

(1.18)Such f is called a convex extension of f .
To formulate a local characterization of global minimality, we need to specify
an appropriate neighborhood of a point (vector) in accordance with the class offunctions in question. Then we say that a vector x is a local minimizer if it is aminimizer within that neighborhood of x.
Conjugacy and biconjugacy are defined with respect to the Legendre–Fencheltransformation. For a function f : Zn → R we define f • : Rn → R byf • (p) = sup{⟨p, x⟩ − f (x) | x ∈ Zn }(p ∈ Rn ),(1.19)

1.3 Classes of Discrete Convex Functions

17

where ⟨p, x⟩ denotes the inner product of p and x, i.e., ⟨p, x⟩ = ∑ni=1 pi xi for
p = (p1 , p2 , . . . , pn ) and x = (x1 , x2 , . . . , xn ). This function f • is referred to as the
conjugate of f , and the mapping f 7→ f • of (1.19) as the discrete Legendre–Fencheltransformation.
For an integer-valued function f : Zn → Z we can define f • : Zn → Z byf • (p) = sup{⟨p, x⟩ − f (x) | x ∈ Zn }(p ∈ Zn ).

(1.20)

This function f • is referred to as the integral conjugate of f , and the mapping f 7→
f • of (1.20) as the fully-discrete or fully-integral Legendre–Fenchel transformation.
We can apply (1.20) twice to obtain f •• = ( f • )• , which is referred to as the integral
biconjugate of f .
We are concerned with the following questions related to conjugacy and biconjugacy for any integer-valued function f in a given class of discrete convex functions.
• Does the integral conjugate f • in (1.20) belong to the same class? If not, how is
it characterized?
• Do we have integral biconjugacy f •• = f under the transformation (1.20)?
The discrete separation theorem may be stated in a generic form as follows,
where a precise meaning of f being “discrete convex” should be specified and g
being “discrete concave” means −g being “discrete convex” in the same specificsense.
Theorem 1.7 (Generic form of discrete separation theorem). Let f : Zn → R bea “discrete convex” function and g : Zn → R be a “discrete concave” function suchthat domZ f ∩ domZ g ̸= 0.
/ If f (x) ≥ g(x) for all x ∈ Zn , there exist α ∗ ∈ R and∗np ∈ R such thatf (x) ≥ α ∗ + ⟨p∗ , x⟩ ≥ g(x)(∀x ∈ Zn ).

(1.21)

Moreover, if f and g are integer-valued, there exist integral α ∗ ∈ Z and p∗ ∈ Zn .
The generic form of a Fenchel-type duality theorem reads as follows. For f :Zn → Z and g : Zn → Z, their integral conjugates f • : Zn → Z and g◦ : Zn → Z aredefined, respectively, by the fully-integral Legendre–Fenchel transformation (1.20)
and its concave versiong◦ (p) = inf{⟨p, x⟩ − g(x) | x ∈ Zn }(p ∈ Zn ).

(1.22)

Theorem 1.8 (Generic form of Fenchel-type duality theorem). Let f : Zn → Z be
an integer-valued “discrete convex” function and g : Zn → Z be an integer-valued“discrete concave” function such that domZ f ∩ domZ g ̸= 0/ or domZ f • ∩ domZ g◦ ̸=
0.
/ Then we haveinf{ f (x) − g(x) | x ∈ Zn } = sup{g◦ (p) − f • (p) | p ∈ Zn }.
If this common value is finite, the infimum and the supremum are attained.

(1.23)

18

1 Main Features of Discrete Convex Analysis(COSS 2018 Reading Material)

Let N = {1, 2, . . . , n}. For i ∈ N, the ith unit vector is denoted as 1 i ; in addition
we define 1 i with i = 0 to be the zero vector and 1 to be the all one vector:i∨

1 i = (0, . . . , 0, 1, 0, . . . , 0) (i ∈ N),

1 0 = (0, 0, . . . , 0),

1 = (1, 1, . . . , 1).

The characteristic vector of a subset A ⊆ N is denoted by 1 A , whose ith component
1 Ai is given by{
1 (i ∈ A),(1.24)
1 Ai =
0 (i ∈ N \ A).

1.3.2 Separable convex functions
A function f : Zn → R is called a separable convex function if it can be represented
asn

f (x) = ∑ φi (xi )(1.25)

i=1

with univariate discrete convex functions φi : Z → R (i = 1, 2, . . . , n), which, bydefinition (1.3), satisfy

φi (t − 1) + φi (t + 1) ≥ 2φi (t)(∀t ∈ Z).

(1.26)It should be clear that xi denotes the ith component of vector x = (x1 , x2 , . . . , xn ).
The following properties of separable convex functions can be shown easily fromthe corresponding statements for univariate discrete convex functions in Section 1.2.
1. A separable convex function is convex-extensible.
2. For a separable convex function f , a point x ∈ domZ f is a global minimizer of f
if and only if it is a local minimizer in the sense thatf (x) ≤ min{ f (x − 1 i ), f (x + 1 i )}(∀i ∈ {1, 2, . . . , n}).

(1.27)

3. The integral conjugate f • in (1.20) of an integer-valued separable convex function f is another integer-valued separable convex function. Furthermore, we haveintegral biconjugacy f •• = f using the fully-integral Legendre–Fenchel transformation (1.20).
4. A discrete separation theorem of the form of Theorem 1.7 holds for separable
convex functions.
5. A Fenchel-type min-max duality of the form of Theorem 1.8 holds for integervalued separable convex functions.

1.3 Classes of Discrete Convex Functions

19

1.3.3 Integrally convex functions
The concept of integrally convex functions arise from convex-extensibility respecting the integer lattice Zn .
A function f : Zn → R is called integrally convex if its local convex extension
˜f : Rn → R is (globally) convex in the ordinary sense, where f˜ is defined as thecollection of piecewise-linear convex extensions of f in each unit hypercube {x ∈Rn | ai ≤ xi ≤ ai + 1 (i = 1, 2, . . . , n)} with a ∈ Zn ; see Section 11.3 for details. In
the case of n = 1, integral convexity is equivalent to the condition (1.3).
Among the major properties we are interested in, convex-extensibility, local characterization of global minimality, and integral biconjugacy hold for integrally convex functions, whereas the separation and Fenchel-type min-max theorems fail.
1. An integrally convex function is convex-extensible, by definition.
2. For an integrally convex function f , a point x ∈ domZ f is a global minimizer off if and only if it is a local minimizer in the sense thatf (x) ≤ f (x + d)(∀d ∈ {−1, 0, 1}n ).

(1.28)

3. The integral conjugate f • in (1.20) of an integer-valued integrally convex function f is not necessarily an integrally convex function. Nevertheless, we haveintegral biconjugacy f •• = f under the fully-integral Legendre–Fenchel transformation (1.20).
4. No discrete separation theorem of the form of Theorem 1.7 holds for integrally
convex functions.
5. No Fenchel-type min-max duality of the form of Theorem 1.8 holds for integervalued integrally convex functions.
It is noteworthy that the local characterization of global minimality above is formulated in terms of a neighborhood that does not depend on individual functions.
Convex-extensibility alone would not lead to such a statement that refers to vectorsin (x + S) ∩ Zn with some S ⊆ Rn independent of individual functions f .
However, the failure of duality theorems for integrally convex functions indicates the need of some additional conditions for functions that can be qualified as“discrete convex” functions in the true sense of the word.

1.3.4 L-convex functions
We introduce the concept of L-convex functions by featuring an equivalent variant
thereof, called L♮ -convex functions (“L” stands for “Lattice” and “L♮ ” should beread “ell natural”).
We first observe that a convex function f on Rn satisfies

20

1 Main Features of Discrete Convex Analysis(
f (x) + f (y) ≥ f(COSS 2018 Reading Material)

)
(
)
x+y
x+y
+f
2
2

(x, y ∈ Rn ),(1.29)

which is a special case of (1.1) with λ = 1/2. This property, called midpoint convexity, is known to be equivalent to convexity if f is a continuous function.

f 6(x + y)/2x-yFig. 1.10 Midpoint convexity⌈x+y ⌉yy2

x⌊x+y ⌋⌊x+y ⌋

22⌈x+y ⌉⌈x+y ⌉

22y⌊x+y ⌋xx

2Fig. 1.11 Discrete midpoint convexity

For a function f : Zn → R in discrete variables the above inequality does notalways make sense, since the midpoint (x + y)/2 of two integer vectors x and y may
not be integral. Instead we simulate (1.29) by
(⌈
⌉)
(⌊
⌋)
x+y
x+y
f (x) + f (y) ≥ f+f(x, y ∈ Zn ),(1.30)
22
where, for z ∈ R in general, ⌈z⌉ denotes the smallest integer not smaller than z(rounding-up to the nearest integer) and ⌊z⌋ the largest integer not larger than z(rounding-down to the nearest integer), and this operation is extended to a vector bycomponentwise applications. This is illustrated in Fig. 1.11 in the case of n = 2. Werefer to (1.30) as discrete midpoint convexity.

1.3 Classes of Discrete Convex Functions

21

We say that a function f : Zn → R is L♮ -convex if it satisfies discrete midpoint
convexity (1.30). In the case of n = 1, L♮ -convexity is equivalent to the condition(1.3).

f(x)

x2

x1

Fig. 1.12 An L♮ -convex function (n = 2)L♮ -convexity is closely related to submodularity. For two vectors x and y, thevectors of componentwise maximum and minimum are denoted respectively by x∨yand x ∧ y, that is,(x ∨ y)i = max(xi , yi ),(x ∧ y)i = min(xi , yi ).

(1.31)

A function f : Zn → R is called submodular if
f (x) + f (y) ≥ f (x ∨ y) + f (x ∧ y)(x, y ∈ Zn ),(1.32)and translation submodular if
f (x) + f (y) ≥ f ((x − α 1) ∨ y) + f (x ∧ (y + α 1)) (α ∈ Z+ , x, y ∈ Zn ),(1.33)

where 1 = (1, 1, . . . , 1) and Z+ denotes the set of nonnegative integers. Note that
submodularity (1.32) is a special case of translation submodularity (1.33) for α = 0.
Translation submodularity characterizes L♮ -convexity. That is, a function f :n
Z → R is discrete midpoint convex (1.30) if and only if it is translation submodular(1.33). Note that in case of n = 1, every function satisfies (1.32), which shows that
submodularity alone does not imply discrete convexity. It is known that submodular
integrally convex functions are precisely L♮ -convex functions.
For L♮ -convex functions the five key properties take the following forms. It isnoteworthy that the conjugacy statement involves another kind of discrete convexity
called M♮ -convexity, to be introduced in Section 1.3.5.
1. An L♮ -convex function is convex-extensible.

22

1 Main Features of Discrete Convex Analysis(COSS 2018 Reading Material)

2. For an L♮ -convex function f , a point x ∈ domZ f is a global minimizer of f if andonly if it is a local minimizer in the sense thatf (x) ≤ min{ f (x − d), f (x + d)}(∀d ∈ {0, 1}n ).

(1.34)

3. The integral conjugate f • in (1.20) of an integer-valued L♮ -convex function f is
an integer-valued M♮ -convex function. Furthermore, we have integral biconjugacy f •• = f under the fully-integral Legendre–Fenchel transformation.
4. A discrete separation theorem of the form of Theorem 1.7 holds for L♮ -convex
functions.
5. A Fenchel-type min-max duality of the form of Theorem 1.8 holds for integervalued L♮ -convex functions.
A function f : Zn → R is said to be an L-convex function if it is an L♮ -convex
function with the additional property that f is linear in the direction of 1, i.e.,f (x + 1) = f (x) + r(x ∈ Zn )(1.35)

for some r ∈ R (r being independent of x). It is known that f is L-convex if andonly if it satisfies (1.32) and (1.35). L-convex functions and L♮ -convex functions
are essentially equivalent in the sense that L♮ -convex functions in n variables can be
identified, up to the constant r in (1.35), with L-convex functions in n + 1 variables.
L-convex functions also enjoy the five key properties in slightly modified forms.
For an L-convex function f with r = 0, the local minimality condition (1.34) ischanged tof (x) ≤ f (x + d)(∀d ∈ {0, 1}n ),(1.36)and the conjugate of an L-convex function is an M-convex function, to be introducedin Section 1.3.5.

1.3.5 M-convex functions
Just as L-convexity is defined through discretization of midpoint convexity, anotherkind of discrete convexity, called M-convexity, can be defined through discretizationof another property of convex functions in continuous variables. We feature a variantof M-convexity, called M♮ -convexity (“M” stands for “Matroid” and “M♮ ” should
be read “em natural”).
We first observe that a convex function f on Rn satisfies the inequality
f (x) + f (y) ≥ f (x − α (x − y)) + f (y + α (x − y))(1.37)

for every α ∈ R with 0 ≤ α ≤ 1. This inequality follows from (1.1) by adding theinequality for λ = α and that for λ = 1 − α . The inequality (1.37) says that the sumof the function values evaluated at two points, x and y, does not increase if the two1.3 Classes of Discrete Convex Functions

23

points approach each other by the same distance on the line segment connecting
them (see Fig. 1.13). We refer to this property as equidistance convexity.

f 6

y

~

x − α (x − y)

y′

∥

x′

∥

y + α (x − y)

}

x

-

y′

y

∥

y + α (x − y)



x′

x

∥

x − α (x − y)Fig. 1.13 Equidistance convexity

For a function f : Zn → R in discrete variables we simulate equidistance convexity (1.37) by moving a pair of points (x, y) to another pair (x′ , y′ ) along the coordinate
axes rather than on the connecting line segment. To be more specific, we consider
two kinds of possibilities(x′ , y′ ) = (x − 1 i , y + 1 i ) or

(x′ , y′ ) = (x − 1 i + 1 j , y + 1 i − 1 j )(1.38)

with indices i and j such that xi > yi and x j < y j ; see Fig. 11.2. For a vector z ∈ Rn
in general, define the positive and negative supports of z as
supp+ (z) = {i | zi > 0},

supp− (z) = { j | z j < 0}.

(1.39)

Then (1.38) can be rewritten compactly as (x′ , y′ ) = (x − 1 i + 1 j , y + 1 i − 1 j ) withi ∈ supp+ (x − y) and j ∈ supp− (x − y) ∪ {0}, where 1 0 = 0.

y

-

y′

y

y′

j

6
-i

x′ 

x

?

j

6
-i

Fig. 1.14 Nearer pairs (x′ , y′ ) in the definition of M♮ -convex functions

x′

6


x

24

1 Main Features of Discrete Convex Analysis(COSS 2018 Reading Material)

As a discrete analogue of equidistance convexity (1.37) we consider the following condition: For any x, y ∈ domZ f and any i ∈ supp+ (x − y), there exists
j ∈ supp− (x − y) ∪ {0} such thatf (x) + f (y) ≥ f (x − 1 i + 1 j ) + f (y + 1 i − 1 j ),(1.40)

which is referred to as the exchange property. A function f : Zn → R having thisexchange property is called M♮ -convex. In the case of n = 1, M♮ -convexity is equivalent to the condition (1.3).
f(x)

x2

x1

Fig. 1.15 An M♮ -convex function (n = 2)

With this definition we can obtain the five desired properties as follows. Note thatthe conjugacy statement refers to L♮ -convexity introduced in Section 1.3.4.
1. An M♮ -convex function is convex-extensible.
2. For an M♮ -convex function f , a point x ∈ domZ f is a global minimizer of f if
and only if it is a local minimizer in the sense thatf (x) ≤ f (x − 1 i + 1 j )(∀i, j ∈ {0, 1, . . . , n}).

(1.41)

3. The integral conjugate f • in (1.20) of an integer-valued M♮ -convex function f is
an integer-valued L♮ -convex function. Furthermore, we have integral biconjugacy
f •• = f under the fully-integral Legendre–Fenchel transformation (1.20).
4. A discrete separation theorem of the form of Theorem 1.7 holds for M♮ -convex
functions.
5. A Fenchel-type min-max duality of the form of Theorem 1.8 holds for integervalued M♮ -convex functions.

1.3 Classes of Discrete Convex Functions

25

A function f : Zn → R is called M-convex if we can always choose j ∈ supp− (x −y) (i.e., j ̸= 0) in the exchange property (1.40). In other words, f is an M-convex
function if and only if it is M♮ -convex and domZ f ⊆ {x ∈ Zn | ∑ni=1 xi = r} for somer ∈ Z. M-convex functions and M♮ -convex functions are essentially equivalent in
the sense that M♮ -convex functions in n variables can be obtained as projections ofM-convex functions in n + 1 variables.
M-convex functions also enjoy the five key properties in slightly modified forms.
The local minimality condition (1.41) should be changed tof (x) ≤ f (x − 1 i + 1 j )(∀i, j ∈ {1, 2, . . . , n})(1.42)and the conjugate of an M-convex function is an L-convex function.

1.3.6 Discrete convex sets
The concepts of discrete convex sets are naturally induced from those of discrete
convex functions as follows.
In the continuous case, the convexity of a set S ⊆ Rn can be characterized using
its indicator function δS : Rn → {0, +∞}, which is defined as{
0 (x ∈ S),
δS (x) =(1.43)+∞ (x ̸∈ S).
That is, a set S is convex if and only if its indicator function δS is convex.
For a set S ⊆ Zn we may regard its indicator function as a function δS : Zn →{0, +∞} on Zn . Then the concepts of L♮ -convex sets and M♮ -convex sets can be
defined as
S is an L♮ -convex set ⇐⇒ δS is an L♮ -convex function,
S is an M♮ -convex set⇐⇒ δS

is an M♮ -convex function.

(1.44)(1.45)

Similarly we can define the concepts of L-convex sets, M-convex sets, and integrally
convex sets. An L♮ -convex (M♮ -convex, L-convex, M-convex, or integrally convex)
set S has the property(1.46)
S = S ∩ Zn ,where S denotes the convex hull of S. This is sometimes referred to as the hole-freeproperty.
For an L♮ -convex function f , the effective domain domZ f and the set of minimizers argminZ f are L♮ -convex sets. This statement remains true when L♮ -convexity isreplaced by M♮ -convexity, L-convexity, M-convexity, or integral convexity.
Discrete convex sets are discussed fully in Chapter 10, and the discrete convexityof domZ f and argminZ f are treated in Chapters 11 and 13, respectively.

26

1 Main Features of Discrete Convex Analysis(COSS 2018 Reading Material)

1.4 Comparison of Discrete Convex Functions
1.4.1 Inclusion relation among function classes
We have defined L♮ -convex functions and M♮ -convex functions by discretization of
midpoint convexity (1.29) and equidistance convexity (1.37), respectively, to discrete midpoint convexity (1.30) and exchange property (1.40). This scheme is summarized in Fig. 1.16.
⟨Continuous Variables⟩f : Rn → R
midpoint convex (1.29)⇕⟨Discrete Variables⟩f : Zn → R−→ discrete midpoint convex (1.30)(L♮ -convex)(ordinary) convex (1.1)⇕(M♮ -convex)

equidistance convex (1.37) −→ exchange property (1.40)
Fig. 1.16 Definitions of L♮ -convexity and M♮ -convexity by discretization

Figure 1.17 shows the inclusion relations among classes of discrete convex functions we have introduced. Integrally convex functions contain both L♮ -convex functions and M♮ -convex functions. L♮ -convex functions contain L-convex functions asa special case. The same is true for M♮ -convex and M-convex functions. The classesof L-convex functions and M-convex functions are disjoint, whereas the intersectionof the classes of L♮ -convex functions and M♮ -convex functions is exactly the classof separable convex functions.
A function f : 2N → R that assigns a real number (or +∞) to each subset of
N = {1, 2, . . . , n} is called a set function, where notation 2N means the set of all
subsets of N, and hence X ∈ 2N is equivalent to saying that X is a subset of N. A set
function f is said to be submodular if
f (X) + f (Y ) ≥ f (X ∪Y ) + f (X ∩Y )(∀X,Y ⊆ N),(1.47)

where it is understood that the inequality is satisfied if f (X) or f (Y ) is equal to +∞.
A set function f : 2N → R can be identified with a function g : Zn → R withdom g ⊆ {0, 1}n through the correspondence f (X) = g(11X ) for X ⊆ N. With thiscorrespondence in mind we can say that submodular set functions are exactly L♮ convex functions on {0, 1}n , and valuated matroids (see Section 4.1 for definition)
are exactly M-concave functions on {0, 1}n . Part II, consisting of Chapters 3 to 9, isdevoted to the study of such set functions with discrete convexity/concavity.

1.4 Comparison of Discrete Convex Functions

27

f : Zn → R
Convex-extensible
Integrally convex
L♮ -convex

L-convexM♮ -convex
Separable-convex

M-convex

Fig. 1.17 Classes of discrete convex functions (L♮ -convex ∩ M♮ -convex = separable convex)

Other kinds of discrete convex functions are also treated in this book, including
multimodular functions (Section 11.6), globally and locally discrete midpoint convex functions (Section 11.7), M-convex functions on jump systems (Section 31.3),
and L-convex functions on trees and graphs (Section 32.1). Multimodularity can be
regarded as a variant of L♮ -convexity, since a function f : Zn → R is multimodular if and only if it can be represented as f (x) = g(x1 , x1 + x2 , . . . , x1 + · · · + xn )for some L♮ -convex function g. Globally (resp., locally) discrete midpoint convex
functions are defined by weakening the condition for L♮ -convexity, that is, by imposing the discrete midpoint convex inequality (1.30) only when ∥x−y∥∞ ≥ 2 (resp.,∥x − y∥∞ = 2). We often use “DMC” to mean “discrete midpoint convex(ity).”
Table 1.1 Various kinds of discrete convex functions
Convexity
Domain Defining condition (roughly)
submodular set fn
2N
f (X) + f (Y ) ≥ f (X ∪Y ) + f (X ∩Y )valuated matroid
2N
f (X) + f (Y ) ≤ max{ f (X − i + j) + f (Y + i − j)}separable convex
Znf (x) = φ1 (x1 ) + φ2 (x2 ) + · · · + φn (xn ) (φi : convex)
integrally convex
Zn
Local convex extensionis (globally)
convex(⌈⌉)(⌊⌋)
L♮ -convex
Znf (x) + f (y) ≥ f x+y+ f x+y2
2
L-convexZnL♮ -convex & linear in direction 1♮nM -convex
Zf (x) + f (y) ≥ min{ f (x − 1i + 1 j ) + f (y + 1i − 1 j )}M-convexZnM♮ -convex & constant component-sum on dom f
multimodularZnf (x) = g(x1 , x1 + (⌈x2 , . . . ⌉), x1 + · (⌊· · + xn⌋)), g: L♮ -convex
x+y+f
globally DMC
Zn
f (x) + f (y) ≥ f (⌈ x+y
2 ⌉)2 ⌋) (∥x − y∥∞ ≥ 2)(⌊ x+ylocally DMC+f(∥x − y∥∞ = 2)
Znf (x) + f (y) ≥ f x+y
2
2
i
j
i
j
M-convex (jump)Znf (x) + f (y) ≥ min{
f
(x
±
1
±
1
)
+
f
(y
(⌈
⌉)
(⌊ x+y ⌋) ∓ 1 ∓ 1 )}L-convex
tree/graph f (x) + f (y) ≥ f x+y+
f22∗ Valuated matroid is discrete concave

28

1 Main Features of Discrete Convex Analysis(COSS 2018 Reading Material)

The discrete convex functions considered in this book are listed in Table 1.1 witha brief description of definitions. In addition to Fig. 1.17 we have the following
inclusion relations among the function classes:{separable convex} ⫋ {multimodular} ⫋ {integrally convex},{L♮ -convex} ⫋ {globally DMC} ⫋ {locally DMC} ⫋ {integrally convex},{M♮ -convex} ⫋ {M-convex (jump)} ̸⊆ {convex-extensible}.
The inclusion relations, including those in Fig. 1.17, will be proved in Chapter 11.

1.4.2 Comparion with respect to the key properties
We compare discrete convex functions with respect to the five crucial properties
highlighted in this chapter. In Table 1.2 below, “Y” means “Yes, this function class
has this property” and “N” means “No, this function class does not have this property.” In the columns of “Biconjugacy” and “Fenchel duality,” functions are assumed
to be integer-valued and the fully-integral Legendre–Fenchel transformation (1.20)
with p ∈ Zn is used.7
Table 1.2 Five key properties of discrete convex functions
DiscreteConvex- Local/global Integral Separation Fenchel
convexity
extension minimality biconjugacy theorem duality
separable convex
Y
Y
Y
Y
Y
Y
Y
Y
N
N
integrally convex
L♮ -convex
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
L-convexM♮ -convex
Y
Y
Y
Y
Y
M-convex
YYYYY
multimodular
Y
Y
Y
Y
Y
Y
Y
Y
N
N
globally DMC
locally DMC
Y
Y
Y
N
N
M-convex (jump)
N
Y
N
N
N

7 We also discuss conjugacy and Fenchel-type duality for real-valued functions in Chapters 16 and18.

1.4 Comparison of Discrete Convex Functions29

1.4.3 Operations on discrete convex functions
We compare the discrete convex functions with respect to admissible operations
such as an origin shift of variables, a sign inversion of variables, scaling of variables
and function values, addition and convolution of functions. While these operations
are discussed in detail in Chapters 14 and 22, Tables 1.3 and 1.4 show a quickcomparison. In these tables, “Y” means “Yes, this function class is closed under
this operation” and “N” means “No, this function class is not closed under thisoperation.”
Table 1.3 covers the following operations.
• An origin shift means f (x + b) with an integer vector b.
• Two types of sign inversion of variables are distinguished. A simultaneous sign
inversion means f (−x1 , −x2 , . . . , −xn ), and an independent sign inversion meansf (±x1 , ±x2 , . . . , ±xn ) with an arbitrary choice of “+” and “−” for each variable.
• Permutation of variables means f (xσ (1) , xσ (2) , . . . , xσ (n) ) with a permutation σ of(1, 2, . . . , n).
• Scaling of variables means f (sx1 , sx2 , . . . , sxn ) with a positive integer s. Note thatthe same scaling factor s is used for all coordinates.

Table 1.3 Operations on discrete convex functions via coordinate changes
Discreteconvexity

Origin Sign inversion Permu- Scaling
shift simult. indep. tationf (x + b) f (−x) f (±xi ) f (xσ (i) ) f (sx)separable convex
Y
Y
Y
Y
Y
integrally convex
Y
Y
Y
Y
N
L♮ -convex
Y
Y
Y
N
Y
L-convex
YYNYY
M♮ -convex
Y
Y
N
Y
N
M-convex
Y
YNY
N
multimodular
Y
Y
N
N
Y
Y
globally DMC
YYNY
locally DMC
Y
Y
N
Y
Y
Y
Y
Y
Y
N
M-convex (jump)

Table 1.4 covers the following operations.
• Value scaling means a f (x) with a nonnegative factor a ≥ 0.
• Restriction and projection are defined with reference to a partition of the components of x into two parts8 as x = (y, z). We call f (y, 0) the restriction (or section)of f , and infz f (y, z) the projection (or partial minimization) of f .
i = yi for i ∈ Y and xi = zi
for i ∈ Z for some partition of {1, 2, . . . , n} into two disjoint nonempty subsets Y and Z. For x =(x1 , x2 , x3 , x4 ), for example, we can take y = (x2 , x3 ) and z = (x1 , x4 ).

8 More precisely, “x = (y, z)” is a short-hand notation to mean that x

30

1 Main Features of Discrete Convex Analysis(COSS 2018 Reading Material)• Addtion of two functions is defined, in an obvious way, by the addition of function values for each x. Two types of additions are distinguished: one is the addition of f with a separable convex function φ , denoted f + φ , and the other is thesum f1 + f2 of two functions f1 and f2 in the same class. Since a linear function
is separable convex, f (x) + ⟨p, x⟩ is a special case of f + φ .
• Convolution of two functions f and g is defined as ( f 2 g)(x) = inf{ f (y) + g(z) |x = y + z, y, z ∈ Zn }. Two types of convolutions are distinguished: one is the
convolution of f with a separable convex function φ , denoted f 2 φ , and theother is the convolution f1 2 f2 of two functions f1 and f2 in the same class.

Table 1.4 Operations on discrete convex functions related to function values
Discreteconvexity

Value Restric- ProjecAddition
Convolution
scaling tion
separable general separable
tion
generala f (x) f (y, 0) minz f (y, z) f + φ f1 + f2
f 2φ
f1 2 f2
separable convex
Y
Y
Y
Y
Y
Y
Y
Y
Y
integrally convex Y
YNYNL♮ -convex
Y
Y
Y
Y
Y
Y
N
Y
N
Y
Y
Y
Y
N
L-convexM♮ -convex
Y
Y
N
Y
Y
Y
Y
M-convex
Y
N
Y
Y
N
Y
Y
Y
Y
N
Y
Y
N
N
multimodular
YYY
globally DMC
YYNN
locally DMC
Y
Y
Y
Y
Y
N
N
Y
Y
Y
N
Y
Y
M-convex (jump) Y(φ : separable convex on a specified domain)1.5 History of Discrete Convex Analysis

31

1.5 History of Discrete Convex Analysis
In this section we briefly describe the history of discrete convex functions closely related to L-convex and M-convex functions. There are, however, many other studies
of discrete convex functions that have been done independently of L- and M-convex
functions, such as Girlich–Kowaljow [19], Hemmecke–Köppe–Lee–Weismantel[22], Hochbaum [28], Hochbaum–Shanthikumar [29], Ibaraki–Katoh [30], Lee–
Leyffer [38], Miller [40], Onn [63].
The origin of L-convex and M-convex functions can be traced back to 1935, when
the concept of matroids was introduced by Whitney [73] and Nakasawa [62]. The
equivalence between submodularity of rank functions and exchange property of independent sets is the germ of the conjugacy between L-convex and M-convex functions in discrete convex analysis. The subsequent history is outlined in Table 1.5.
Table 1.5 Development of discrete convex functions
1935 matroid
Whitney [73], Nakasawa [62]1965 submodular set function
Edmonds [8]1969 convex-cost network flow
Iri [31]1982 gross substitutes condition
Kelso–Crawford [33]1983 Submodularity and Convexity
discrete separation theorem
Frank [12]Fenchel-type duality
Fujishige [14]convex extension
Lovász [39]Hajek [21]1985 multimodular function
1990 valuated matroid
Dress–Wenzel [6, 7]
1990 integrally convex function
Favati–Tardella [10]1996 M-convex function
Murota [43]1998 Discrete Convex Analysis
Murota [45]1998 L-convex function
Murota [45]1999 M♮ -convex function
Murota–Shioura [56]2000 L♮ -convex function
Fujishige–Murota [17]2000 polyhedral L-/M-convex function
Murota–Shioura [57]2003 quasi L-/M-convex function
Murota–Shioura [58]Murota–Shioura [60, 61]
2004 L-/M-convex function on Rn
2006 M-convex function on jump systems Murota [52]2011 submodular function on trees
Kolmogorov [34]2015 L-convex function on graphs
Hirai [23, 24, 25, 26]

In the late 1960s, J. Edmonds found a duality theorem on the intersection problem
for a pair of (poly)matroids. This theorem, Edmonds’ intersection theorem, shows a
min-max relation between the maximum of a common independent set and the minimum of a submodular set function derived from the rank functions. The famous
article of Edmonds [8] convinced us of the fundamental role of submodularity indiscrete optimization. Analogies of submodular functions to convex functions andto concave functions were discussed at the same time. The min-max relation sup-32

1 Main Features of Discrete Convex Analysis(COSS 2018 Reading Material)

ported the analogy to convex functions, whereas some other facts pointed to concave
functions. No unanimous conclusion was reached for a long time.
The relationship between submodular functions and convex functions was madeclear in the early 1980s. The fundamental relationship between submodular set functions and convex functions, due to Lovász [39], says that a set function is submodular if and only if the Lovász extension (a specific piecewise-linear extension) ofthat function is convex. Reformulations of Edmonds’ intersection theorem into aseparation theorem for a pair of submodular/supermodular functions by Frank [12]and a Fenchel-type min-max duality theorem by Fujishige [14] indicate similarity
to convex functions. The discrete mathematical content of these theorems, whichcannot be captured by the relationship of submodularity to convexity, lies in the
integrality assertion for integer-valued submodular/supermodular functions. Further
analogy to convex analysis such as subgradients was conceived by Fujishige [15].
These developments in the 1980s led us to the understanding that (i) submodularity should be compared to convexity, and (ii) the essence of the duality for a pair ofsubmodular/supermodular functions lies in the discreteness (integrality) assertion in
addition to the duality for convex/concave functions.
The Lovász extension of a submodular set function is a convex function, which isnecessarily a positively homogeneous function satisfying f (λ x) = λ f (x) for λ ≥ 0.
This means that the convexity arguments about submodularity in the 1980s focus ona restricted class of convex functions. The relationship of submodular set functions
to convex functions is generalized to the full extent by the concept of L-convex
functions in discrete convex analysis.
Addressing the issue of local vs global minimality for functions defined on integer lattice points, Favati and Tardella [10] came up with the concept of integrally
convex functions in 1990. This concept successfully captures a fairly general classof functions on integer lattice points, for which a local minimality implies the global
minimality. Moreover, the class of submodular integrally convex functions (i.e.,
integrally convex functions that are submodular on integer lattice points) was investigated as a well-behaved subclass of integrally convex functions. It turned out
later [17] that this concept is equivalent to L♮ -convex functions in discrete convex
analysis.
We have so far seen major milestones towards L-convex functions, and are now
turning to M-convex functions.
A weighted version of the matroid intersection problem was introduced by Edmonds [8]. The problem is to find a maximum weight common independent set (ora common base) with respect to a given weight vector. Efficient algorithms for thisproblem were developed in the 1970s by Edmonds [9], Lawler [37], Tomizawa–
Iri [70], and Iri–Tomizawa [32] on the basis of a nice optimality criterion in termsof dual variables. The optimality criterion of Frank [11] in terms of weight splitting can be thought of as a version of such optimality criterion using dual variables.
The weighted matroid intersection problem was generalized to the polymatroid intersection problem as well as to the submodular flow problem. It should be noted,
however, that in all of these generalizations the weighting remained linear or separable convex.

1.5 History of Discrete Convex Analysis

33

The concept of valuated matroids, introduced by Dress and Wenzel [6,7] in 1990,
provides a nice framework of nonlinear optimization on matroids. A valuation of amatroid is a nonlinear and nonseparable function on bases satisfying a certain exchange axiom. It was shown by Dress and Wenzel that a version of greedy algorithm
works for maximizing a matroid valuation, and this property in turn characterizes
matroid valuations.
Not only the greedy algorithm but the intersection problem extends to valuatedmatroids. The valuated matroid intersection problem, introduced by Murota [41],is to maximize the sum of two valuations. This generalizes the weighted matroidintersection problem since linear weighting is a special case of matroid valuation.
Optimality criteria such as weight splitting as well as algorithms for the weighted
matroid intersection are generalized to the valuated matroid intersection (Murota[42]). Analogy of matroid valuations to concave functions resulted in a Fenchel-type
min-max duality theorem for matroid valuations (Murota [44]). This Fenchel-type
duality is not a generalization nor a special case of Fujishige’s Fenchel-type duality
for submodular functions, but these two are generalized and unified into a single
min-max equation, which is the Fenchel-type duality theorem in discrete convex
analysis.
The analogy of valuated matroids to concave functions led to the concept of Mconvex/concave functions in Murota [43], 1996. M-convexity is a concept of “convexity” for functions defined on integer lattice points in terms of an exchange axiom,
and affords a common generalization of valuated matroids and (integral) polymatroids. A valuated matroid can be identified with an M-concave function defined on{0, 1}-vectors, and the base polyhedron of an integral polymatroid is a synonym fora {0, +∞}-valued M-convex function. The valuated matroid intersection problem
and the polymatroid intersection problem are unified into the M-convex intersection
problem. The Fenchel-type duality theorem for matroid valuations is generalized
for M-convex functions, and the submodular flow problem to the M-convex submodular flow problem (Murota [47]), which involves an M-convex function as anonlinear cost. The nice optimality criterion using dual variables survives in thisgeneralization. Thus, M-convex functions yield fruitful generalizations of many important optimization problems on matroids.
The two independent lines of developments, namely, the convexity argument for
submodular functions in the early 1980s and that for valuated matroids and Mconvex functions in the early nineties, were merged into a unified framework of“Discrete Convex Analysis,” advocated by Murota [45] in 1998. The concept of Lconvex functions was introduced as a generalization of submodular set functions.
L-convex functions form a conjugate class of M-convex functions with respect to
the Legendre–Fenchel transformation. This completes the picture of conjugacy advanced by Whitney [73] as the equivalence between submodularity of the rank function of a matroid and exchange property of independent sets of a matroid. The duality theorems generalize to L-convex and M-convex functions. In particular, theseparation theorem for L-convex functions is a generalization of Frank’s separation
theorem for submodular set functions.

34

1 Main Features of Discrete Convex Analysis(COSS 2018 Reading Material)

Ramifications of the concepts of L- and M-convexity followed. M♮ -convex functions, introduced by Murota–Shioura [56], are essentially equivalent to M-convex
functions but are often more convenient in applications. L♮ -convex functions, due toFujishige–Murota [17], are an equivalent variant of L-convex functions. It turnedout [17] that L♮ -convex functions are exactly the same as submodular integrally
convex functions that had been introduced by Favati–Tardella [10] in 1990. Quasi
L-convex and M-convex functions are introduced in Murota–Shioura [58], and Mconvex functions on jump systems in Murota [52].
While the functions described above are defined for discrete variables belonging
to Zn or {0, 1}n , it is also possible to define L- and M-convexity for functions inreal or continuous variables belonging to Rn . This amounts to investigating convex
functions with some additional combinatorial structures. L- and M-convexity are defined for polyhedral functions (Murota–Shioura [57]), quadratic functions (Murota–
Shioura [59]), and closed convex functions (Murota–Shioura [60, 61]). They form
subclasses of ordinary convex functions, and the conjugacy under the Legendre–
Fenchel transformation holds between L-convex and M-convex functions.
Since 2010, discrete convex functions on graph structures have been investigated.
The concept of submodular function on trees is formulated by Kolmogorov [34] asa framework unifying L♮ -convex functions and bisubmodular functions. A theory of
L-convex functions on graphs has been developed by Hirai [23,24,25,26], motivatedby combinatorial dualities in multi-commodity flow problems and complexity classification of facility location problems on graphs. This theory exhibits substantial
progress of discrete convex analysis, which may be called “discrete convex analysis
beyond Zn .”We have outlined the development of the framework of discrete convex functions starting from matroids and submodular set functions. These studies are mostly
driven by mathematical interest or aesthetics. However, substantial results on discrete convex functions have also been obtained in the literature of more practicaldisciplines.
In the late 1960s, Iri [31] made a comprehensive study of nonlinear electric networks, where the role and significance of convexity are considered in combination
with discrete structures stemming from the underlying graphs. This study, with adual view of mathematics and physics, offers a major guiding principle to discrete
convex analysis.
Discrete convex functions appear naturally in operations research. In queueing
theory, Hajek [21] introduced the concept of multimodular functions in 1985. Multimodular functions are further investigated in the literature of discrete event systems(Altman–Gaujal–Hordijk [1], Glasserman–Yao [20]). It turned out later [51] that
this concept is equivalent to L♮ -convexity through a simple transformation of variables. L♮ -convex functions are used and studied also in inventory theory (SimchiLevi–Chen–Bramel [68]).
In economics and game theory, Kelso and Crawford [33] introduced gross substitutes condition in 1982. Subsequent studies in the literature of mathematical economics revealed that this condition is crucial for the existence of economic or gametheoretic equilibria. In 2003, Fujishige and Yang [18] pointed out that this condition

1.5 History of Discrete Convex Analysis

35

is equivalent to M♮ -concavity, which triggered active interaction between mathematical economics and discrete convex analysis (Murota [55], Shioura–Tamura [67],Tamura [69]).
It is emphasized that the theory of discrete convex analysis have benefited a lot
from interactions with application fields outside optimization. Some concepts, theorems and algorithms were discovered in the process of solving concrete problems
what had denied solution by the then existing tools. In particular, the valuated matroid intersection problem [41,42] was formulated and solved in an effort of solving
a certain problem in matrix theory.9
Finally, we mention that the earlier development of discrete convex analysis ispresented in monographs [49] and [50] published in 2001 and 2003, and in [16,Chapter VII] published in 2005. More recent surveys are given in [54, 55].

9 More specifically, the problem is to design an efficient algorithm to compute the degree of de-terminants of a mixed polynomial matrix [46], which is described also in [48, Chapter 6] and [50,
Chapter 12].

36

1 Main Features of Discrete Convex Analysis(COSS 2018 Reading Material)

References
1. Altman, E., Gaujal, B., Hordijk, A.: Discrete-Event Control of Stochastic Networks: Multimodularity and Regularity. Lecture Notes in Mathematics 1829, Springer, Heidelberg (2003)
2. Barvinok, A.: A Course in Convexity. American Mathematical Society, Providence, R.I.
(2002)
3. Borwein, J.M., Lewis, A.S.: Convex Analysis and Nonlinear Optimization: Theory and Examples. Springer, Berlin (2000)
4. Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge(2004)
5. Cook, W.J., Cunningham, W.H., Pulleyblank, W.R., Schrijver, A.: Combinatorial Optimization. Wiley, New York (1998)
6. Dress, A.W.M., Wenzel, W.: Valuated matroid: A new look at the greedy algorithm. Applied
Mathematics Letters 3, 33–35 (1990)
7. Dress, A.W.M., Wenzel, W.: Valuated matroids. Advances in Mathematics 93, 214–250 (1992)
8. Edmonds, J.: Submodular functions, matroids and certain polyhedra. In: Guy, R., Hanani,
H., Sauer, N., Schönheim, J. (eds.) Combinatorial Structures and Their Applications, pp. 69–
87. Gordon and Breach, New York (1970); Also in: Jünger, M., Reinelt, G., Rinaldi, G.
(eds.) Combinatorial Optimization—Eureka, You Shrink! Lecture Notes in Computer Science,
vol. 2570, pp. 11–26. Springer, Berlin (2003)
9. Edmonds, J.: Matroid intersection. Annals of Discrete Mathematics 14, 39–49 (1979)
10. Favati, P., Tardella, F.: Convexity in nonlinear integer programming. Ricerca Operativa 53,
3–44 (1990)
11. Frank, A.: A weighted matroid intersection algorithm. Journal of Algorithms 2, 328–336(1981)
12. Frank, A.: An algorithm for submodular functions on graphs. Annals of Discrete Mathematics
16, 97–120 (1982)
13. Frank, A.: Connections in Combinatorial Optimization. Oxford University Press, Oxford(2011)
14. Fujishige, S.: Theory of submodular programs: A Fenchel-type min-max theorem and subgradients of submodular functions. Mathematical Programming 29, 142–155 (1984)
15. Fujishige, S.: On the subdifferential of a submodular function. Mathematical Programming
29, 348–360 (1984)
16. Fujishige, S.: Submodular Functions and Optimization. 2nd ed., Annals of Discrete Mathematics 58, Elsevier, Amsterdam (2005)
17. Fujishige, S., Murota, K.: Notes on L-/M-convex functions and the separation theorems. Mathematical Programming 88, 129–146 (2000)
18. Fujishige, S., Yang, Z.: A note on Kelso and Crawford’s gross substitutes condition. Mathematics of Operations Research 28, 463–469 (2003)
19. Girlich, E., Kowaljow, M.M.: Nichtlineare diskrete Optimierung. Akademie-Verlag, Berlin(1981)
20. Glasserman, P., Yao, D.D.: Monotone Structure in Discrete-Event Systems. Wiley, New York(1994)
21. Hajek, B.: Extremal splittings of point processes. Mathematics of Operations Research 10,
543–556 (1985)
22. Hemmecke, R., Köppe, M., Lee, J., Weismantel, R.: Nonlinear integer programming. In:
Jünger, M., et al. (eds.) 50 Years of Integer Programming 1958–2008: From The Early Yearsand State-of-the-Art, Chapter 15, pp. 561–618, Springer-Verlag, Berlin (2010)23. Hirai, H.: L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem. Discrete Optimization 18, 1–37 (2015)24. Hirai, H.: Discrete convexity and polynomial solvability in minimum 0-extension problems.
Mathematical Programming, Series A 155, 1–55 (2016)25. Hirai, H.: Discrete convex functions on graphs and their algorithmic applications. In: Fukunaga, T., Kawarabayashi, K. (eds.) Combinatorial Optimization and Graph Algorithms, Communications of NII Shonan Meetings, pp. 67–101. Springer Nature, Singapore (2017)

References37

26. Hirai, H.: L-convexity on graph structures. Jounal of the Operations Research Society of Japan
61, 71–109 (2018)27. Hiriart-Urruty, J.-B., Lemaréchal, C.: Fundamentals of Convex Analysis. Springer, Berlin(2001)
28. Hochbaum, D.S.: Complexity and algorithms for nonlinear optimization problems. Annals of
Operations Research 153, 257–296 (2007)
29. Hochbaum, D.S., Shanthikumar, J.G.: Convex separable optimization is not much harder thanlinear optimization. Journal of the Association for Computing Machinery 37, 843–862 (1990)
30. Ibaraki, T., Katoh, N.: Resource Allocation Problems: Algorithmic Approaches. MIT Press,
Boston (1988)
31. Iri, M.: Network Flow, Transportation and Scheduling—Theory and Algorithms. Academic
Press, New York (1969)
32. Iri, M., Tomizawa, N.: An algorithm for finding an optimal ‘independent assignment’. Journalof the Operations Research Society of Japan 19, 32–57 (1976)
33. Kelso, A.S., Jr., Crawford, V.P.: Job matching, coalition formation, and gross substitutes.
Econometrica 50, 1483–1504 (1982)
34. Kolmogorov, V.: Submodularity on a tree: Unifying L♮ -convex and bisubmodular functions.
In: Murlak, F., Sankowski, P. (eds.) Mathematical Foundations of Computer Science 2011,
Lecture Notes in Computer Science, vol. 6907, pp. 400–411. Springer, Heidelberg (2011)
35. Korte, B., Vygen, J.: Combinatorial Optimization: Theory and Algorithms. 5th ed., Springer,
Heidelberg (2012)
36. Krantz, S.G.: Convex Analysis. CRC Press, Boca Raton (2015)
37. Lawler, E.L.: Matroid intersection algorithms. Mathematical Programming 9, 31–56 (1975)
38. Lee, J., Leyffer, S. (eds): Mixed Integer Nonlinear Programming, The IMA Volumes in Mathematics and its Applications 154, Springer-Verlag, Berlin (2012)
39. Lovász, L.: Submodular functions and convexity. In: Bachem, A., Grötschel, M., Korte,
B. (eds.) Mathematical Programming—The State of the Art, pp. 235–257. Springer, Berlin(1983)
40. Miller, B.L.: On minimizing nonseparable functions defined on the integers with an inventory
application. SIAM Journal on Applied Mathematics 21, 166–185 (1971)
41. Murota, K.: Valuated matroid intersection, I: optimality criteria. SIAM Journal on Discrete
Mathematics 9, 545–561 (1996)
42. Murota, K.: Valuated matroid intersection, II: algorithms. SIAM Journal on Discrete Mathematics 9, 562–576 (1996)
43. Murota, K.: Convexity and Steinitz’s exchange property. Advances in Mathematics 124, 272–
311 (1996)
44. Murota, K.: Fenchel-type duality for matroid valuations. Mathematical Programming 82, 357–
375 (1998)
45. Murota, K.: Discrete convex analysis. Mathematical Programming 83, 313–371 (1998)
46. Murota, K.: On the degree of mixed polynomial matrices. SIAM Journal on Matrix Analysis
and Applications 20, 196–227 (1998)
47. Murota, K.: Submodular flow problem with a nonseparable cost function. Combinatorica 19,
87–109 (1999)
48. Murota, K.: Matrices and Matroids for Systems Analysis. Springer, Berlin (2000)
49. Murota, K.: Discrete Convex Analysis—An Introduction (in Japanese). Kyoritsu PublishingCo., Tokyo (2001)
50. Murota, K.: Discrete Convex Analysis. SIAM Monographs on Discrete Mathematics and Applications, Vol. 10, Society for Industrial and Applied Mathematics, Philadelphia (2003)
51. Murota, K.: Note on multimodularity and L-convexity. Mathematics of Operations Research30, 658–661 (2005)
52. Murota, K.: M-convex functions on jump systems: A general framework for minsquare graphfactor problem. SIAM Journal on Discrete Mathematics 20, 213–226 (2006)
53. Murota, K.: Primer of Discrete Convex Analysis—Discrete versus Continuous Optimization(in Japanese). Kyoritsu Publishing Co., Tokyo (2007)

38

1 Main Features of Discrete Convex Analysis(COSS 2018 Reading Material)

54. Murota, K.: Recent developments in discrete convex analysis. In: Cook, W., Lovász, L.,
Vygen, J. (eds.) Research Trends in Combinatorial Optimization, Chapter 11, pp. 219–260.
Springer, Berlin (2009)
55. Murota, K.: Discrete convex analysis: A tool for economics and game theory. Journal of Mechanism and Institution Design 1, 151–273 (2016)56. Murota, K., Shioura, A.: M-convex function on generalized polymatroid. Mathematics of Operations Research 24, 95–105 (1999)
57. Murota, K., Shioura, A.: Extension of M-convexity and L-convexity to polyhedral convex
functions. Advances in Applied Mathematics 25, 352–427 (2000)
58. Murota, K., Shioura, A.: Quasi M-convex and L-convex functions: quasi-convexity in discrete
optimization. Discrete Applied Mathematics 131 467–494 (2003)
59. Murota, K., Shioura, A.: Quadratic M-convex and L-convex functions. Advances in Applied
Mathematics 33, 318–341 (2004)
60. Murota, K., Shioura, A.: Fundamental properties of M-convex and L-convex functions in continuous variables. IEICE Transactions on Fundamentals of Electronics, Communications andComputer Sciences E87-A, 1042–1052 (2004)
61. Murota, K., Shioura, A.: Conjugacy relationship between M-convex and L-convex functions
in continuous variables. Mathematical Programming 101, 415–433 (2004)
62. Nakasawa, T.: Zur Axiomatik der linearen Abhängigkeit, I, II, III. Science Reports of theTokyo Bunrika Daigaku, Section A 2, 235–255 (1935); 3, 45–69 (1936); 3, 123–136 (1936)
63. Onn, S.: Nonlinear Discrete Optimization: An Algorithmic Theory. European MathematicalSociety, Zurich (2010)
64. Oxley, J.G.: Matroid Theory. 2nd ed., Oxford University Press, Oxford (2011)
65. Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970)
66. Schrijver, A.: Combinatorial Optimization—Polyhedra and Efficiency. Springer, Heidelberg(2003)
67. Shioura, A., Tamura, A.: Gross substitutes condition and discrete concavity for multi-unit
valuations: a survey. Journal of the Operations Research Society of Japan 58, 61–103 (2015)68. Simchi-Levi, D., Chen, X., Bramel, J.: The Logic of Logistics: Theory, Algorithms, and Applications for Logistics Management, 3rd ed. Springer, New York (2014)
69. Tamura, A.: Discrete Convex Analysis and Game Theory (in Japanese). Asakura PublishingCo., Tokyo (2009)
70. Tomizawa, N., Iri, M.: An algorithm for solving the “independent assignment” problem withapplication to the problem of determining the order of complexity of a network (in Japanese).
Transactions of the Institute of Electronics and Communication Engineers of Japan 57A, 627–
629 (1974)
71. Topkis, D.M.: Supermodularity and Complementarity. Princeton University Press, Princeton,
NJ (1998)
72. White, N.(ed.): Theory of Matroids. Cambridge University Press, London (1986)
73. Whitney, H.: On the abstract properties of linear dependence. American Journal of Mathematics 57, 509–533 (1935)