Hausdorff Institute of Mathematics, Summer School (September 21–25, 2015)

Discrete Convex Analysis∗
Kazuo Murota

1

Introduction

Discrete convex analysis [18, 40, 43, 47] aims to establish a general theoretical framework for solvable discrete optimization problems by means of a combination of the ideas in continuous optimization and combinatorial optimization. The framework of convex analysis is adapted to discrete settings and the mathematical results in matroid/submodular function theory are generalized. Viewed
from the continuous side, it is 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 → R or
f : Zn → Z that enjoy certain nice properties comparable to convexity. Symbolically,
Discrete Convex Analysis = Convex Analysis + Matroid Theory.
The theory extends the direction set forth by J. Edmonds [11], A. Frank [16], S. Fujishige [17], and
L. Lovász [34]. The reader is referred to [59] for convex analysis, [8, 32, 60] for combinatorial
optimization, [57, 58, 71] for matroid theory, and [18, 70] for submodular function theory.
Two convexity concepts, called L-convexity and M-convexity, play primary roles. L-convex
functions and M-convex functions are conjugate to each other through the (continuous or discrete)
Legendre–Fenchel transformation. L-convex functions and M-convex functions generalize, respectively, the concepts of submodular set functions and base polyhedra. It is noted that “L” stands for“Lattice” and “M” for “Matroid.”
The set of all real numbers is denoted by R, and R = R ∪ {+∞} and R = R ∪ {−∞}. The set of all
integers is denoted by Z, and Z = Z ∪ {+∞} and Z = Z ∪ {−∞}. Let V = {1, 2, . . . , n} for a positive
integer n. The characteristic vector of X ⊆ V is denoted by χX ∈ {0, 1}n . For i ∈ V, we write χi forχ{i} , which is the ith unit vector, and χ0 = 0 (zero vector).

2

Concepts of Discrete Convex Functions

The concepts of L-convex and M-convex functions can be obtained through discretization of two
different characterizations of convex functions.

2.1 Ordinary Convex Functions
We start by recalling the definition of ordinary convex functions. A function f : Rn → R is said tobe convex if(1)
λ f (x) + (1 − λ) f (y) ≥ f (λx + (1 − λ)y)for all x, y ∈ Rn and for all λ with 0 ≤ λ ≤ 1, where it is understood that the inequality is satisfied if
f (x) or f (y) is equal to +∞. A function h : Rn → R is said to be concave if −h is convex.
A set S ⊆ Rn is called convex if, for any x, y ∈ S and 0 ≤ λ ≤ 1, we have λx + (1 − λ)y ∈ S . The
indicator function of a set S is a function δS : Rn → {0, +∞} defined by(0(x ∈ S ),δS (x) =(2)+∞ (x < S ).
∗ This is a reproduction of Sections 1 to 6, with minor revisions, of [K. Murota: Recent developments in discrete convex
analysis, Research Trends in Combinatorial Optimization, Bonn 2008 (W. Cook, L. Lovász and J. Vygen, eds.), SpringerVerlag, Berlin, 2009, Chapter 11, 219–260], prepared as a supplementary reading material for Summer School on Combinatorial Optimization (September 21–25, 2015) at Hausdorff Institute of Mathematics.

1

Then S is a convex set if and only if δS is a convex function.
For a function f : Rn → R ∪ {−∞, +∞} in general, the set
domR f = {x ∈ Rn | f (x) ∈ R}
is called the effective domain of f . A point x ∈ Rn is said to be a global minimum of f if theinequality f (x) ≤ f (y) holds for every y ∈ Rn . Point x is a local minimum if this inequality holds forevery y in some neighborhood of x. The set of global minima (minimizers) is denoted asargminR f = {x ∈ Rn | f (x) ≤ f (y) (∀y ∈ Rn )}.
Convex functions are tractable in optimization (or minimization) problems and this is mainly
because of the following properties.
1. Local optimality (or minimality) guarantees global optimality.
2. Duality theorems such as min-max relation and separation hold.
Duality is a central issue in convex analysis, and is discussed in Section 5.
A separable convex function is a function f : Rn → R that can be represented as
f (x) =nX

ϕi (xi ),

(3)

i=1

where x = (xi | i = 1, . . . , n) and ϕi : R → R (i = 1, . . . , n) are univariate convex functions.

2.2 Discrete Convex Functions
We now consider how convexity concept can (or should) be defined for functions in discrete variables. It would be natural to expect the following properties of any function f : Zn → R that isqualified as a “discrete convex function.”
1. Function f is extensible to a convex function on Rn .
2. Local optimality (or minimality) guarantees global optimality.
3. Duality theorems such as min-max relation and separation hold.
Recall that f : Zn → R is said to be convex-extensible if there exists a convex function f :Rn → R such that f (x) = f (x) for all x ∈ Zn . It is widely understood that convex extensibility
alone does not yield a fruitful theoretical framework, which fact motivates us to introduce L-convex
and M-convex functions. In this section we focus on convex extensibility and local optimality while
deferring duality issues to Section 5. The effective domain and the set of minimizers are denoted
respectively as
domZ fargminZ f
2.2.1

=
=

{x ∈ Zn | f (x) ∈ R},{x ∈ Zn | f (x) ≤ f (y) (∀y ∈ Zn )}.

Univariate and separable convex functions

The univariate case (n = 1) is simple and straightforward. We may regard a function f : Z → R asa discrete convex function iff (x − 1) + f (x + 1) ≥ 2 f (x)(∀x ∈ Z).

(4)This is justified by the following facts.
Theorem 1. A function f : Z → R is convex-extensible if and only if it satisfies (4).
Theorem 2. For a function f : Z → R satisfying (4), a point x ∈ domZ f is a global minimum if andonly if it is a local minimum in the sense thatf (x) ≤ min{ f (x − 1), f (x + 1)}.
Theorems 1 and 2 above can be extended in obvious ways to a separable (discrete) convex
function f : Zn → R, which is, by definition, representable in the form of (3) with univariate
functions ϕi : Z → R having property (4).
2

q q

q

p+q

p+q

2

p

p+q
2

p+q

2

p+q
2

2

p

p

p+q
2

図 1: 離散中点凸性
Figure 1: Discrete midpoint convexity

2.2.2

L-convex functions

We explain the concept of L-convex functions [40] by featuring an equivalent variant thereof, called
L\ -convex functions [19] (“L\ ” should be read “el natural”).
We first observe that a convex function g on Rn satisfies
 p + q
 p + qg(p) + g(q) ≥ g+g(p, q ∈ Rn ),(5)22which is a special case of (1) with λ = 1/2. This property, called midpoint convexity, is known to beequivalent to convexity if g is a continuous function.
For a function g : Zn → R in discrete variables the above inequality does not always make sense,
since the midpoint p+q
2 of two integer vectors p and q may not be integral. Instead we simulate (5)by p + q  p + q g(p) + g(q) ≥ g+g(p, q ∈ Zn ),(6)22
where, for z ∈ R in general, dze denotes the smallest integer not smaller than z (rounding-up to thenearest integer) and bzc the largest integer not larger than z (rounding-down to the nearest integer),and this operation is extended to a vector by componentwise applications, as illustrated in Fig. 1 in
the case of n = 2. We refer to (6) as discrete midpoint convexity [12].
We say that a function g : Zn → R is L\ -convex if it satisfies discrete midpoint convexity (6). In
the case of n = 1, L\ -convexity is equivalent to the condition (4). Examples of L\ -convex functions
are given in Section 4.1.
With this definition we can obtain the following desired statements in parallel with Theorems 1
and 2.
Theorem 3. An L\ -convex function g : Zn → R is convex-extensible.
Theorem 4. For an L\ -convex function g : Zn → R, a point p ∈ domZ g is a global minimum if andonly if it is a local minimum in the sense thatg(p) ≤ min{g(p − q), g(p + q)}(∀q ∈ {0, 1}n ).

(7)Although Theorem 4 affords a local criterion for global optimality of a point p, a straightforward
verification of (7) requires O(2n ) function evaluations. The verification can be done in polynomial
time as follows. We consider set functions ρ+p and ρ−p defined by ρ±p (Y) = g(p ± χY ) − g(p) forY ⊆ V, both of which are submodular. Since (7) is equivalent to saying that both ρ+p and ρ−p achieve
the minimum at Y = ∅, this condition can be verified in polynomial time by submodular function
minimization algorithms [24, 35].
L\ -convexity is closely related with submodularity. For two vectors p and q, the vectors ofcomponentwise maxima and minima are denoted respectively by p ∨ q and p ∧ q, that is,(p ∨ q)i = max(pi , qi ),(p ∧ q)i = min(pi , qi ).

A function g : Zn → R is called submodular ifg(p) + g(q) ≥ g(p ∨ q) + g(p ∧ q)

3

(p, q ∈ Zn ),

(8)

✻

y

⑦

y′
k

x − α(x − y)ky + α(x − y)

x′
⑥

x

✲

y

✲

✛

y′

x′

k

k

x

y + α(x − y) x − α(x − y)
図 1: 凸関数の性質（等近凸性）

Figure 2: Equidistance convexity

and translation submodular ifg(p) + g(q) ≥ g((p − α1) ∨ q) + g(p ∧ (q + α1)) (α ∈ Z+ , p, q ∈ Zn ),(9)where 1 = (1, 1, . . . , 1) and Z+ denotes the set of nonnegative integers. The latter property characterizes L\ -convexity, as follows.
Theorem 5. For a function g : Zn → R, translation submodularity (9) is equivalent to discrete
midpoint convexity (6).
An L-convex function is defined as an L\ -convex function g that satisfiesg(p + 1) = g(p) + r(10)for some r ∈ R (which is independent of p). It is known that g is L-convex if and only if it satisfies(8) and (10); in fact this is the original definition of L-convexity. L-convex functions and L\ -convex
functions are essentially the same, in that L\ -convex functions in n variables can be identified, up to
the constant r in (10), with L-convex functions in n + 1 variables.
2.2.3

M-convex functions

Just as L-convexity is defined through discretization of midpoint convexity, another kind of discrete
convexity, called M-convexity [39, 40], can be defined through discretization of another convexity
property. We feature an equivalent variant of M-convexity, called M\ -convexity [49] (“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))(11)for every α ∈ R with 0 ≤ α ≤ 1. This inequality follows from (1) for λ = α and λ = 1 − α, whereas it
implies (1) if f is a continuous function. The inequality (11) says that the sum of the function values
evaluated at two points, x and y, does not increase if the two points approach each other by the same
distance on the line segment connecting them (see Fig. 2). We refer to this property as equidistanceconvexity.
For a function f : Zn → R in discrete variables we simulate equidistance convexity (11) bymoving a pair of points (x, y) to another pair (x0 , y0 ) along the coordinate axes rather than on theconnecting line segment. To be more specific, we consider two kinds of possibilities(x0 , y0 ) = (x − χi , y + χi ) or

(x0 , y0 ) = (x − χi + χ j , y + χi − χ j )(12)with indices i and j such that xi > yi and x j < y j ; see Fig. 3. 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}.
4

y

✲
❄

y′

x′
✻
✛

j
✻

x

✲ i
♮

図 1:
M definition
凸関数の定義Figure 3: Nearer pairin theof M\ -convex functions

Then the expression (12) can be rewritten compactly as (x0 , y0 ) = (x − χi + χ j , y + χi − χ j ) withi ∈ supp+ (x − y) and j ∈ supp− (x − y) ∪ {0}, where χ0 is defined to be the zero vector.
As a discrete analogue of equidistance convexity (11) 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 − χi + χ j ) + f (y + χi − χ j ),(13)

which is referred to as the exchange property. A function f : Zn → R having this exchange property
is called M\ -convex. In the case of n = 1, M\ -convexity is equivalent to the condition (4). Examplesof M\ -convex functions are given in Section 4.2.
With this definition we can obtain the following desired statements comparable to Theorems 1
and 2.
Theorem 6. An M\ -convex function f : Zn → R is convex-extensible.
Theorem 7. For an M\ -convex function f : Zn → R, a point x ∈ domZ f is a global minimum if andonly if it is a local minimum in the sense thatf (x) ≤ f (x − χi + χ j )(∀i, j ∈ {0, 1, . . . , n}).

An M-convex function is defined as an M\ -convex function f that satisfies (13) with j ∈ supp− (x−y). This is equivalent to saying that f is an M-convex function if and only if it is M\ -convex andPdomZ f ⊆ {x ∈ Zn | ni=1 xi = r} for some r ∈ Z. M-convex functions and M\ -convex functions are
essentially the same, in that M\ -convex functions in n variables can be obtained as projections ofM-convex functions in n + 1 variables.
2.2.4

Classes of discrete convex functions

We have thus defined L\ -convex functions and M\ -convex functions by discretization of midpoint
convexity and equidistance convexity, respectively. The definitions are summarized in Fig. 4.
Figure 5 shows the classes of discrete convex functions we have introduced. L\ -convex functions contain L-convex functions as a special case. The same is true for M\ -convex and M-convex
functions. By Theorems 3 and 6 both L\ -convex functions and M\ -convex functions are containedin the class of convex-extensible functions. It is known that the classes of L-convex functions andM-convex functions are disjoint, whereas the intersection of the classes of L\ -convex functions andM\ -convex functions is exactly the class of separable convex functions.
2.2.5

Discrete convex sets

In the continuous case the convexity of a set S ⊆ Rn can be characterized by that of its indicatorfunction δS as
S is a convex set ⇐⇒ δS is a convex function.
We make use of this relation to define the concepts of discrete convex sets.

5

hContinuous Variablesi
f : Rn → R
midpoint convex
m(ordinary) convex
mequidistance convex

hDiscrete Variablesi
f : Zn → R
discrete midpoint convex (L\ -convex)−→[discretization][discretization]exchange property (M\ -convex)−→

discrete midpoint convex:
midpoint convex:(ordinary) convex:
equidistance convex:
exchange property:

l m
j k
f (x) + f (y) ≥ f x+y+ f x+y22
 
f (x) + f (y) ≥ 2 f x+y2
λ f (x) + (1 − λ) f (y) ≥ f (λx + (1 − λ)y)f (x) + f (y) ≥ f (x − α(x − y)) + f (y + α(x − y))f (x) + f (y) ≥ min[ f (x − χi ) + f (y + χi ),min { f (x − χi + χ j ) + f (y + χi − χ j )}]x j <y j

Figure 4: Definitions of L\ -convexity and M\ -convexity by discretization
1✬

f : Zn → R
convex-extensible✬M♮ -convex✬✬

L-convex

✫
✫
✫

✬

✩
M-convex✩
separable convex ✫✫✪♮L -convex✪

Figure 5: Classes of discrete convex functions(L\ -convex ∩ M\ -convex = separable convex)
Fig. 1. Classes of discrete convex functions(M♮ -convex ∩ L♮ -convex = separable convex)

6

✩

✩
✩
✪
✪

✪

For a set S ⊆ Zn the indicator function of S is a function δS : Zn → R given by (2). L\ -convex
sets and M\ -convex sets are defined as
S is an L\ -convex set
S is an M\ -convex set

δS is an L\ -convex function,
δS is an M\ -convex function.

⇐⇒⇐⇒

Similarly for the definitions of L-convex and M-convex sets. We have S = S ∩ Zn for an L\ -convex(M\ -convex, L-convex or M-convex) set S , where S denotes the convex hull of S .
For an L\ -convex function f , both domZ f and argminZ f are L\ -convex sets. This statement
remains true when L\ -convexity is replaced by M\ -convexity, L-convexity or M-convexity.

2.3 Discrete Convex Functions in Continuous Variables
So far we have been concerned with the translation from “continuous” to “discrete.” We have defined L-convex and M-convex functions by discretization of midpoint convexity and equidistanceconvexity, respectively. Although these two properities are both equivalent to (ordinary) convexity
for continuous functions in continuous variables, their discrete versions have given rise to different
concepts (cf. Fig. 4).
We are now interested in the reverse direction, from “discrete” to “continuous,” to define theconcepts of L-convex and M-convex functions in continuous variables [50, 51, 52]. In so doing
we intend to capture certain classes of convex functions with additional combinatorial structures.
We refer to such functions as discrete convex functions in continuous variables. This may soundsomewhat contradictory, but the adjective “discrete” indicates the discreteness in direction in thespace Rn of continuous variables.
2.3.1

L-convex functions

L\ -convex functions in discrete variables have been introduced in terms of a discretization of midpoint convexity. By Theorem 5, however, we can alternatively say that L\ -convex functions are thosefunctions which satisfy translation submodularity (9).
This alternative definition enables us to introduce the concept of L\ -convex functions in continuous variables. That is, a convex function g : Rn → R is defined to be L\ -convex ifg(p) + g(q) ≥ g((p − α1) ∨ q) + g(p ∧ (q + α1)) (α ∈ R+ , p, q ∈ Rn ),(14)

where R+ denotes the set of nonnegative reals. Examples of L\ -convex functions are given in Section
4.1.
L\ -convex functions constitute a subclass of convex functions that are equipped with certain
combinatorial properties in addition to convexity. It is known, for example, that a smooth function
g is L\ -convex if and only if the Hessian matrix H = (hi j = ∂2 g/∂pi ∂p j ) is a diagonally dominantsymmetric M-matrix, i.e.,nXhi j ≤ 0 (i , j),
hi j ≥ 0 (i = 1, . . . , n)
(15)
j=1

at each point. This is a combinatorial property on top of positive semidefiniteness, which is familiarin operations research, mathematical economics, and numerical analysis. It may be said that L\ convexity extends this well-known property to nonsmooth functions.
An L-convex function in continuous variables is defined as an L\ -convex function g : Rn → R
that satisfies(16)g(p + α1) = g(p) + αr
(α ∈ R, p ∈ Rn )for some r ∈ R (which is independent of p and α). L-convex functions and L\ -convex functions are
essentially the same, in that L\ -convex functions in n variables can be identified, up to the constant r
in (16), with L-convex functions in n + 1 variables.
The inequality (14) is a continuous version of the translation submodularity (9), in which we had
α ∈ Z+ and p, q ∈ Zn instead of α ∈ R+ and p, q ∈ Rn . It may be said that (14) is obtained from (9)by prolongation, by which we mean a process converse to discretization. Figure 6 summarizes how
we have defined L\ -convex functions in discrete and continuous variables. Note that prolongation of
discrete midpoint convexity renders no novel concept, but reduces to midpoint convexity, which is(almost) equivalent to convexity.
7

hContinuous Variablesi
g : Rn → R(ordinary) convex
mmidpoint convex
translation submodular(L\ -convex)(ordinary) convex:
midpoint convex:
discrete midpoint convex:
translation submodular:

hDiscrete Variablesi
g : Zn → R[discretization]−→←−

discrete midpoint convex
mtranslation submodular(L\ -convex)[prolongation]
λg(p) + (1 − λ)g(q) ≥ g(λp + (1 − λ)q)g(p) + g(q) ≥ 2 g p+q
l 2 mj k
g(p) + g(q) ≥ g p+q+ g p+q22g(p) + g(q) ≥ g((p − α1) ∨ q) + g(p ∧ (q + α1))Figure 6: Definitions of L\ -convexity by discretization and prolongation

2.3.2

M-convex functions

M\ -convex functions in continuous variables can be defined by prolongation (i.e., a continuous version) of the exchange property (13). We say that a convex function f : Rn → R is M\ -convex if, forany x, y ∈ domR f and any i ∈ supp+ (x − y), there exist j ∈ supp− (x − y) ∪ {0} and a positive real
number α0 such thatf (x) + f (y) ≥ f (x − α(χi − χ j )) + f (y + α(χi − χ j ))(17)

for all α ∈ R with 0 ≤ α ≤ α0 .
M\ -convex functions in continuous variables constitute another subclass of convex functions,different from L\ -convex functions, that are equipped with another kind of combinatorial properties.
See examples in Section 4.2.
An M-convex function in continuous variables is defined as an M\ -convex function f : Rn → R
that satisfies (17) with j ∈ supp− (x − y). This is equivalent to saying that f is M-convex if andP
only if it is M\ -convex and domR f ⊆ {x ∈ Rn | ni=1 xi = r} for some r ∈ R. M-convex functions\
and M -convex functions are essentially the same, in that M\ -convex functions in n variables can beobtained as projections of M-convex functions in n + 1 variables.
2.3.3

Classes of discrete convex functions in continuous variables

Figure 7 shows the classes of discrete convex functions in continuous variables. L\ -convex functions contain L-convex functions as a special case. The same is true for M\ -convex and M-convex
functions. It is known that the classes of L-convex functions and M-convex functions are disjoint,whereas the intersection of the classes of L\ -convex functions and M\ -convex functions is exactly
the class of separable convex functions.
Comparison of Fig. 7 with Fig. 5 shows the parallelism between the continuous and discrete
cases.

3

Conjugacy

Conjugacy under the Legendre transformation is one of the most appealing facts in convex analysis.
In discrete convex analysis, the discrete Legendre transformation gives a one-to-one correspondence
between L-convex functions and M-convex functions.

3.1 Continuous Case
For a function f : Rn → R (not necessarily convex) with domR f , ∅, the convex conjugate f • :Rn → R is defined byf • (p) = sup{hp, xi − f (x) | x ∈ Rn }8(p ∈ Rn ),

(18)

✬

f : Rn → R
convex✬✬M♮ -convex✬✬

L-convex✫✫✫✩
M-convex✩
separable convex ✫✫✪♮L -convex

✪

✩

✩
✩
✪
✪

✪

Figure 7: Classes of convex functions(L\ -convex ∩ M\ -convex = separable convex)
Fig. 1. Classes of convex functions♮♮
Pn (M -convex ∩ L -convex = separable convex)
where hp, xi = i=1 pi xi is the inner product of p = (pi ) ∈ Rn and x = (xi ) ∈ Rn . The functionf • is also referred to as the (convex) Legendre(–Fenchel) transform of f , and the mapping f 7→ f •as the (convex) Legendre(–Fenchel) transformation. Similarly to (18), the concave conjugate ofh : Rn → R is defined to be the function h◦ : Rn → R given byh◦ (p) = inf{hp, xi − h(x) | x ∈ Rn }(p ∈ Rn ).

(19)

Note that h◦ (p) = −(−h)• (−p).
The conjugacy theorem in convex analysis states that the Legendre transformation gives a oneto-one correspondence in the class of closed proper convex functions, where a convex function f issaid to be proper if domR f is nonempty, and closed if the epigraph {(x, y) ∈ Rn+1 | y ≥ f (x)} is a
closed subset of Rn+1 . Notation f •• means ( f • )• .
Theorem 8. The Legendre transformation (18) gives a symmetric one-to-one correspondence inthe class of all closed proper convex functions. That is, for a closed proper convex function f , theconjugate function f • is a closed proper convex function and f •• = f .
Addition of combinatorial ingredients to the above theorem yields the conjugacy between Mconvex and L-convex functions.
Theorem 9 ([51]). The Legendre transformation (18) gives a one-to-one correspondence between
the classes of all closed proper M\ -convex functions and L\ -convex functions. Similarly for M-convex
and L-convex functions.
The first statement above means that, for a closed proper M\ -convex function f , f • is a closed
proper L\ -convex function and f •• = f , and that, for a closed proper L\ -convex function g, g• is a
closed proper M\ -convex function and g•• = g. To express this one-to-one correspondence we haveindicated M\ -convex functions and L\ -convex functions by congruent regions in Fig. 7. The second
statement means similarly that, for a closed proper M-convex function f , f • is a closed proper Lconvex function and f •• = f , and that, for a closed proper L-convex function g, g• is a closed proper
M-convex function and g•• = g. It is also noted that the conjugate of a separable convex function isanother separable convex function.
The L/M-conjugacy is also valid for polyhedral convex functions.
Theorem 10 ([50]). The Legendre transformation (18) gives a one-to-one correspondence between
the classes of all polyhedral M\ -convex functions and L\ -convex functions. Similarly for M-convex
and L-convex functions.

93.2 Discrete Case
We turn to functions defined on integer points. For functions f : Zn → R and h : Zn → R with
domZ f , ∅ and domZ h , ∅, discrete versions of the Legendre transformations are defined byf • (p)h◦ (p)= sup{hp, xi − f (x) | x ∈ Zn }= inf{hp, xi − h(x) | x ∈ Zn }(p ∈ Rn ),(p ∈ Rn ).

(20)
(21)

We call (20) and (21), respectively, convex and concave discrete Legendre(–Fenchel) transformations. The functions f • : Rn → R and h◦ : Rn → R are called the convex conjugate of f and theconcave conjugate of h, respectively.
Theorem 11. For an M\ -convex function f : Zn → R, the conjugate function f • : Rn → R isa (locally polyhedral) L\ -convex function. For an L\ -convex function g : Zn → R, the conjugate
function g• : Rn → R is a (locally polyhedral) M\ -convex function. Similarly for M-convex andL-convex functions.
For an integer-valued function f , f • (p) is integer for an integer vector p. Hence (20) with p ∈ Zn
defines a transformation of f : Zn → Z to f • : Zn → Z; we refer to (20) with p ∈ Zn as (20)Z .
The conjugacy theorem for discrete M-convex and L-convex functions reads as follows.
Theorem 12 ([40]). The discrete Legendre transformation (20)Z gives a one-to-one correspondence
between the classes of all integer-valued M\ -convex functions and L\ -convex functions in discretevariables. Similarly for M-convex and L-convex functions.
It should be clear that the first statement above means that, for an integer-valued M\ -convex
function f : Zn → Z, the function f • in (20)Z is an integer-valued L\ -convex function and f •• = f ,where f •• is a short-hand notation for ( f • )• using the discrete Legendre transformation (20)Z , andsimilarly when f is L\ -convex.

4

Examples4.1

L-convex Functions

Some examples of L\ - and L-convex functions are given in this section. The following basic facts
are noted.
1. The effective domain of an L\ -convex function is an L\ -convex set.
2. An L\ -convex function remains to be L\ -convex when its effective domain is restricted to any
L\ -convex set.
3. A sum of L\ -convex functions is L\ -convex.
Similar statements are true when “L\ -convex” is replaced by “L-convex” in the above.
We first consider functions in discrete variable p = (p1 , . . . , pn ) ∈ Zn .
Linear function: A linear (or affine) functiong(p) = α + hp, xi(22)

with x ∈ Rn and α ∈ R is L-convex (and hence L\ -convex).
Quadratic function: A quadratic functiong(p) =n X
nX

ai j pi p j(23)

i=1 j=1

with ai j = a ji ∈ R (i, j = 1, . . . , n) is L\ -convex if and only if
ai j ≤ 0 (i , j),

n
X
j=1

10

ai j ≥ 0 (i = 1, . . . , n).

(24)

It is L-convex if and only if
ai j ≤ 0 (i , j),nXai j = 0 (i = 1, . . . , n).

(25)

j=1

Separable convex function: For univariate convex functions ψi (i = 1, . . . , n) and ψi j (i, j =1, . . . , n; i , j),nXXg(p) =
ψi (pi ) +ψi j (pi − p j )
(26)
i, j

i=1

is an L\ -convex function. This is L-convex if ψi = 0 for i = 1, . . . , n.
Maximum-component function: For any τ0 , τ1 , . . . , τn ∈ R,
g(p) = max{τ0 , p1 + τ1 , p2 + τ2 , . . . , pn + τn }(27)

is an L\ -convex function. This is L-convex if τ0 does not exist (i.e., τ0 = −∞). Henceg(p) = max{p1 , p2 , . . . , pn } − min{p1 , p2 , . . . , pn }(28)

is an L-convex function. Furthermore, if ψ is a nondecreasing univariate convex function,g(p) = ψ(max {pi + τi })
1≤i≤n

(29)

is an L\ -convex function. It is also mentioned that, if g0 (p, t) is L\ -convex in (p, t) ∈ Zn × Z and
nondecreasing in t, then the max-aggregation g : Zn × Zm → R defined byg(p, q) = g0 (p, max(q1 , . . . , qm ))(p ∈ Zn , q ∈ Zm )(30)

is L\ -convex in (p, q), whereas g is L-convex if g0 is L-convex.
Submodular set function: A submodular set function ρ : 2V → R can be identified with an\
L -convex function g under the correspondence g(χX ) = ρ(X) for X ⊆ V, where domZ g ⊆ {0, 1}n .
Multimodular function: A function h : Zn → R is multimodular if and only if it can be
represented ash(p) = g(p1 , p1 + p2 , . . . , p1 + · · · + pn )for some L\ -convex function g; see [1, 2, 22, 45].
The constructions above work for functions in continuous variable p ∈ Rn . That is, the functions
g : Rn → R defined by the expressions (22) to (30) are L\ - or L-convex functions, if all the variables
are understood as real numbers or vectors. It is noteworthy that quadratic L\ -convex functions areexactly the same as the (finite dimensional case of) Dirichlet forms used in probability theory [21].
The energy consumed in a nonlinear electrical network, when expressed as a function in terminal
voltages, is an L\ -convex function [43, Section 2.2].

4.2 M-convex Functions
Some examples of M\ - and M-convex functions are given in this section. The following basic facts
are noted.
1. The effective domain of an M\ -convex function is an M\ -convex set.
2. An M\ -convex function does not necessarily remain M\ -convex when its effective domain isrestricted to an M\ -convex set.
3. A sum of M\ -convex functions is not necessarily M\ -convex.
4. The infimal convolution of M\ -convex functions f1 and f2 , defined as( f1  f2 )(x) = inf{ f1 (x1 ) + f2 (x2 ) | x = x1 + x2 },(31)

is M\ -convex if f1  f2 does not take −∞, where x1 , x2 ∈ Zn in the discrete case and x1 , x2 ∈ Rn
in the continuous case.
11

Similar statements are true when “M\ -convex” is replaced by “M-convex” in the above.
We first consider functions in discrete variable x = (x1 , . . . , xn ) ∈ Zn .
Linear function: A linear (or affine) function
f (x) = α + hp, xi(32)

with p ∈ Rn and α ∈ R is M\ -convex. It is M-convex if domZ f is an M-convex set.
Quadratic function: A quadratic function
f (x) =n X
nX

ai j xi x j(33)

i=1 j=1

with ai j = a ji ∈ R (i, j = 1, . . . , n) is M\ -convex if and only if ai j ≥ 0 for all (i, j) andai j ≥ min(aik , a jk ) if {i, j} ∩ {k} = ∅,where domZ f = Zn . A function f of (33), with domZ f = {x ∈ Zn |M-convex if and only if

(34)
Pn

i=1 xi = r} for some r ∈ Z, isai j + akl ≥ min(aik + a jl , ail + a jk ) if {i, j} ∩ {k, l} = ∅.

(35)

Laminar convex function: By a laminar family we mean a nonempty family T of subsets of V
such that X ∩ Y = ∅ or X ⊆ Y or X ⊇ Y for any X, Y ∈ T . A function f is called laminar convex if it
can be represented asXf (x) =fX (x(X))(36)
X∈T

for a laminar family T and a family of univariate convex functions fX indexed by X ∈ T , whereP
x(X) = i∈X xi . A laminar convex function is M\ -convex. A separable convex function (3) is laminarconvex and hence M\ -convex. It is known [23] that every quadratic M\ -convex function (in discretevariables) is laminar convex.
Minimum-value function: Given ai for i ∈ V we define a set function µ : 2V → R as µ(X) =min{ai | i ∈ X} for nonempty X ⊆ V. By convention we put µ(∅) = a∗ by choosing a∗ ∈ R suchthat a∗ ≥ max{ai | i ∈ V}. Then µ is M\ -convex when identified with a function f : Zn → R with
domZ f ⊆ {0, 1}n by f (χX ) = µ(X) for X ⊆ V.
Bipartite matching: Let G = (V, W; E) be a bipartite graph with vertex set V ∪ W and edge set
E, and suppose that each edge e ∈ E is associated with weight γ(e) ∈ R. For X ⊆ V denote by Γ(X)the minimum weight of a matching that matches with X, i.e.,XΓ(X) = min{ γ(e) | M is a matching, V ∩ ∂M = X},e∈M

where Γ(X) = +∞ if such M does not exist. Then Γ is M\ -convex when identified with a function
f : Zn → R with domZ f ⊆ {0, 1}n by f (χX ) = Γ(X) for X ⊆ V. This construction can be extended tothe minimum convex-cost flow problem.
Stable marriage problem: The payoff function of the stable marriage problem is M\ -concave[20, 68].
Matroid: Let (V, B, I, ρ) be a matroid on V with base family B, independent-set family I andrank function ρ. The characteristic vectors of bases {χB | B ∈ B} form an M-convex set and thoseof independent sets {χI | I ∈ I} form an M\ -convex set. The rank function ρ : 2V → Z is M\ concave when identified with a function f : Zn → R with domZ f = {0, 1}n by f (χX ) = ρ(X) for
X ⊆ V; see Section 6.1. More generally, the vector rank function of an integral submodular system
is M\ -concave [18, p. 51].
Valuated matroid: A valuated matroid ω : 2V → R of [9, 10] (see also [42, Chapter 5]) can be
identified with an M\ -concave function f under the correspondence f (χX ) = ω(X) for X ⊆ V, where
domZ f ⊆ {0, 1}n . The tropical geometry [67] is closely related with valuated matroids. For example,
the tropical linear space [66] is essentially the same as the circuit valuation of matroids [54].

12

Next we turn to functions f : Rn → R in continuous variable x ∈ Rn . The infimal convolution(31) preserves M\ -convexity when the infimum is taken over x1 , x2 ∈ Rn . Laminar convex functions(36) as well as linear functions (32) remain to be M\ -convex when x is understood as a real vector.
The energy consumed in a nonlinear electrical network, when expressed as a function in terminal
currents, is an M\ -convex function [43, Section 2.2].
A subtlety arises for quadratic functions. Condition (34), together with ai j ≥ 0 for all (i, j), issufficient but not necessary for f : Rn → R of the form of (33) to be M\ -convex. A necessary andsufficient condition in terms of the matrix A = (ai j ) is that, for any β > 0, A + βI is nonsingular and(A + βI)−1 satisfies (24). It is also mentioned that not every quadratic M\ -convex function in realvariables is laminar convex. As for M-convexity, condition (35) is sufficient but not necessary for f
to be M-convex.
Thus the relation between discrete and continuous cases are not so simple in M-convexity as inL-convexity.

5

Separation and Fenchel Duality

5.1 Separation Theorem
The duality principle in convex analysis can be expressed in a number of different forms. One of themost appealing statements is in the form of the separation theorem, which asserts the existence of aseparating affine function y = α∗ + hp∗ , xi for a pair of convex and concave functions.
In the continuous case we have the following.
Theorem 13. Let f : Rn → R and h : Rn → R be convex and concave functions, respectively(satisfying certain regularity conditions). If(∀x ∈ Rn ),f (x) ≥ h(x)there exist α∗ ∈ R and p∗ ∈ Rn such thatf (x) ≥ α∗ + hp∗ , xi ≥ h(x)(∀x ∈ Rn ).

A discrete separation theorem means a statement like:
For any f : Zn → R and h : Zn → R belonging to certain classes of functions, if
f (x) ≥ h(x) for all x ∈ Zn , then there exist α∗ ∈ R and p∗ ∈ Rn such thatf (x) ≥ α∗ + hp∗ , xi ≥ h(x)(∀x ∈ Zn ).

Moreover, if f and h are integer-valued, there exist integer-valued α∗ ∈ Z and p∗ ∈ Zn .
Discrete separation theorems often capture deep combinatorial properties in spite of the apparent
similarity to the separation theorem in convex analysis. In this connection we note the following
facts (see [43, Examples 1.5 and 1.6] for concrete examples), where f denotes the convex closure off , h the concave closure of h, and =⇒/ stands for “does not imply.”
1. f (x) ≥ h(x) (∀x ∈ Zn ) =⇒/ f (x) ≥ h(x) (∀x ∈ Rn ).
2. f (x) ≥ h(x) (∀x ∈ Zn ) =⇒/ existence of α∗ ∈ R and p∗ ∈ Rn .
3. existence of α∗ ∈ R and p∗ ∈ Rn =⇒/ existence of α∗ ∈ Z and p∗ ∈ Zn .
The separation theorems for M-convex/M-concave functions and for L-convex/L-concave functions read as follows. It should be clear that f • and h◦ are the convex and concave conjugate functionsof f and h defined by (20) and (21), respectively.
Theorem 14 (M-separation theorem). Let f : Zn → R be an M\ -convex function and h : Zn → R
be an M\ -concave function such that domZ f ∩ domZ h , ∅ or domR f • ∩ domR h◦ , ∅. If f (x) ≥ h(x)(∀x ∈ Zn ), there exist α∗ ∈ R and p∗ ∈ Rn such thatf (x) ≥ α∗ + hp∗ , xi ≥ h(x)(∀x ∈ Zn ).

Moreover, if f and h are integer-valued, there exist integer-valued α∗ ∈ Z and p∗ ∈ Zn .
13

Theorem 15 (L-separation theorem). Let g : Zn → R be an L\ -convex function and k : Zn → R bean L\ -concave function such that domZ g ∩ domZ k , ∅ or domR g• ∩ domR k◦ , ∅. If g(p) ≥ k(p)(∀p ∈ Zn ), there exist β∗ ∈ R and x∗ ∈ Rn such thatg(p) ≥ β∗ + hp, x∗ i ≥ k(p)(∀p ∈ Zn ).

Moreover, if g and k are integer-valued, there exist integer-valued β∗ ∈ Z and x∗ ∈ Zn .
As an immediate corollary of the M-separation theorem we can obtain an optimality criterion
for the problem of minimizing the sum of two M-convex functions, which we call the M-convex
intersection problem. Note that the sum of M-convex functions is no longer M-convex and Theorem
7 does not apply.
Theorem 16 (M-convex intersection theorem). For M\ -convex functions f1 , f2 : Zn → R and a pointx∗ ∈ domZ f1 ∩ domZ f2 we havef1 (x∗ ) + f2 (x∗ ) ≤ f1 (x) + f2 (x)(∀x ∈ Zn )if and only if there exists p∗ ∈ Rn such that( f1 − p∗ )(x∗ ) ≤ ( f1 − p∗ )(x)( f2 + p∗ )(x∗ ) ≤ ( f2 + p∗ )(x)(∀x ∈ Zn ),(∀x ∈ Zn ).

These conditions are equivalent, respectively, to( f1 − p∗ )(x∗ ) ≤ ( f1 − p∗ )(x∗ + χi − χ j )( f2 + p∗ )(x∗ ) ≤ ( f2 + p∗ )(x∗ + χi − χ j )(∀ i, j ∈ {0, 1, . . . , n}),(∀ i, j ∈ {0, 1, . . . , n}),and for such p∗ we haveargminZ ( f1 + f2 ) = argminZ ( f1 − p∗ ) ∩ argminZ ( f2 + p∗ ).
Moreover, if f1 and f2 are integer-valued, we can choose integer-valued p∗ ∈ Zn .
Frank’s discrete separation theorem [16] for submodular/supermodular set functions is a special
case of the L-separation theorem. Frank’s weight splitting theorem [15] for the weighted matroidintersection problem is a special case of the M-convex intersection problem. The submodular flow
problem can be generalized to the M-convex submodular flow problem [41]; see also [25, 26].

5.2 Fenchel Duality
Another expression of the duality principle is in the form of the Fenchel duality. This is a minmax relation between a pair of convex and concave functions and their conjugate functions. Such a
min-max theorem is computationally useful in that it affords a certificate of optimality.
The Fenchel duality theorem in the continuous case reads as follows. Recall the notations f • and◦h in (18) and (19).
Theorem 17. Let f : Rn → R and h : Rn → R be convex and concave functions, respectively(satisfying certain regularity conditions). Theninf{ f (x) − h(x) | x ∈ Rn } = sup{h◦ (p) − f • (p) | p ∈ Rn }.
We now turn to the discrete case. For any functions f : Zn → Z and h : Zn → Z we have a chainof inequalities:inf{ f (x) − h(x) | x ∈ Zn }sup{h◦ (p) − f • (p) | p ∈ Zn }≥≥inf{ f (x) − h(x) | x ∈ Rn } ≥

◦

•

(37)

sup{h (p) − f (p) | p ∈ Rn }from the definitions (20) and (21) of conjugate functions f • and h◦ , where f and h are convex andconcave closures of f and h, respectively. It should be observed that14

1. The second inequality in the middle of (37) is in fact an equality by the Fenchel duality theorem (Theorem 17) in convex analysis;
2. The first (left) inequality in (37) can be strict even when f is convex-extensible and h isconcave-extensible, and similarly for the third (right) inequality. See Examples 1 and 2 below.
Example 1. For f, h : Z2 → Z defined asf (x1 , x2 ) = |x1 + x2 − 1|,h(x1 , x2 ) = 1 − |x1 − x2 |we have inf{ f − h} = 0, inf{ f − h} = −1. The discrete Legendre transforms are given by((
p1((p1 , p2 ) ∈ S )−1 ((p1 , p2 ) ∈ T )•◦f (p1 , p2 ) =h (p1 , p2 ) =+∞ (otherwise),−∞ (otherwise)with S = {(−1, −1), (0, 0), (1, 1)} and T = {(−1, 1), (0, 0), (1, −1)}. Hence sup{h◦ − f • } = h◦ (0, 0) −f • (0, 0) = −1 − 0 = −1. Then (37) reads asinf{ f − h}(0)◦

> inf{ f − h} =(−1)•

sup{h − f }(−1)= sup{h◦ − f • }.
(−1)

Example 2. For f, h : Z2 → Z defined asf (x1 , x2 ) = max(0, x1 + x2 ),h(x1 , x2 ) = min(x1 , x2 )we have inf{ f − h} = inf{ f − h} = 0. The discrete Legendre transforms are given as f • = δS andh◦ = −δT in terms of the indicator functions of S = {(0, 0), (1, 1)} and T = {(1, 0), (0, 1)}. Since◦••◦
S ∩ T = ∅, h◦ − f • is identically equal to −∞, whereas sup{h − f } = 0 since f = δS , h = −δT
and S ∩ T = {(1/2, 1/2)}. Then (37) reads asinf{ f − h}(0)

= inf{ f − h} =
(0)

◦

•

sup{h − f }(0)> sup{h◦ − f • }.
(−∞)

From the observations above, we see that the essence of the following theorem is the assertion
that the first and third inequalities in (37) are in fact equalities for M\ -convex/M\ -concave functionsand L\ -convex/L\ -concave functions.
Theorem 18 (Fenchel-type duality theorem).
(1) Let f : Zn → Z be an integer-valued M\ -convex function and h : Zn → Z be an integer-valued
M\ -concave function such that domZ f ∩ domZ h , ∅ or domZ f • ∩ domZ h◦ , ∅. Then we haveinf{ f (x) − h(x) | x ∈ Zn } = sup{h◦ (p) − f • (p) | p ∈ Zn }.

(38)

If this common value is finite, the infimum and the supremum are attained.
(2) Let g : Zn → Z be an integer-valued L\ -convex function and k : Zn → Z be an integer-valued
L\ -concave function such that domZ g ∩ domZ k , ∅ or domZ g• ∩ domZ k◦ , ∅. Then we haveinf{g(p) − k(p) | p ∈ Zn } = sup{k◦ (x) − g• (x) | x ∈ Zn }.

(39)

If this common value is finite, the infimum and the supremum are attained.
Edmonds’ intersection theorem [11] in the integral case is a special case of Theorem 18 (1)above, and Fujishige’s Fenchel-type duality theorem [17] (see also [18, Section 6.1]) for submodular
set functions is a special case of Theorem 18 (2) above.
Whereas L-separation and M-separation theorems are parallel or conjugate in their statements,
the Fenchel-type duality theorem is self-conjugate, in that the substitution of f = g• and h = k◦ into(38) results in (39) by virtue of g = g•• and k = k◦◦ . With the knowledge of M-/L-conjugacy, thesethree duality theorems are almost equivalent to one another; once one of them is established, theother two theorems can be derived by relatively easy formal calculations.
15

6

Submodular Function Maximization

Maximization of a submodular set function is a difficult task in general. Many NP-hard problems canbe reduced to this problem. Also known is that no polynomial algorithm exists in the ordinary oracle
model (and this statement is independent of the P,NP conjecture) [27, 33, 34]. For approximate
maximization under matroid constraints the performance bounds of greedy or ascent type algorithms
were analyzed in [7, 14, 56]. See, e.g., [4, 5, 6, 13] for recent development.
M\ -concave functions on {0, 1}-vectors form a subclass of submodular set functions that arealgorithmically tractable for maximization [48]. This is compatible with our general understandingthat concave functions are easy to maximize, and explains why certain submodular functions treatedin the literature are easier to maximize. To be specific, we have the following.
1. The greedy algorithm can be generalized for maximization of a single M\ -concave function.
2. The matroid intersection algorithm can be generalized for maximization of a sum of two M\ concave functions.
Note that a sum of M\ -concave functions is not necessarily M\ -concave, though it is submodular.
It is also mentioned that maximization of a sum of three M\ -concave functions is NP-hard, since it
includes the three-matroid intersection problem as a special case.

6.1 M\ -concave set functions
Let us say that a set function ρ : 2V → R is M\ -concave if the function h : Zn → R defined ash(χX ) = ρ(X) for X ⊆ V and h(x) = −∞ for x < {0, 1}n is M\ -concave. In other words, ρ is M\ concave if and only if, for any X, Y ⊆ V and i ∈ X \ Y, we have ρ(X) + ρ(Y) ≤ ρ(X \ {i}) + ρ(Y ∪ {i})or ρ(X) + ρ(Y) ≤ ρ((X \ {i}) ∪ { j}) + ρ((Y ∪ {i}) \ { j}) for some j ∈ Y \ X. An M\ -concave set function
is submodular [43, Theorem 6.19].
Not every submodular set function is M\ -concave. An example of a submodular function that is
not M\ -concave is given by ρ on V = {1, 2, 3} defined as ρ(∅) = 0, ρ({2, 3}) = 2, ρ({1}) = ρ({2}) =ρ({3}) = ρ({1, 2}) = ρ({1, 3}) = ρ({1, 2, 3}) = 1. The condition above fails for X = {2, 3}, Y = {1} andi = 2.
A simple example of an M\ -concave set function is given by ρ(X) = ϕ(|X|), where ϕ is a univariate concave function. This is a classical example [34] of a submodular function that connects
submodularity and concavity.
For a family of univariate concave functions {ϕA | A ∈ T } indexed by a family T of subsets ofV, the functionXρ(X) =
ϕA (|A ∩ X|)(X ⊆ V)A∈T\

is submodular. This function is M -concave if, in addition, T is a laminar family (i.e., A, B ∈ T ⇒A ∩ B = ∅ or A ⊆ B or A ⊇ B).
Given a set of real numbers ai indexed by i ∈ V, the maximum-value function
ρ(X) = max aii∈X(X ⊆ V)is an M\ -concave function, where ρ(∅) is defined to be sufficiently small.
A matroid rank function is M\ -concave. Given a matroid on V in terms of the family I of
independent sets, the rank function ρ is defined by
ρ(X) = max{|I| | I ∈ I, I ⊆ X}

(X ⊆ V),

which denotes the maximum size of an independent set contained in X. An interesting identity
exists that indicates a kind of self-conjugacy of a matroid rank function. Let g : Zn → Z be suchthat g(χX ) = ρ(X) for X ⊆ V and domZ g = {0, 1}n , and denote by ρ• the discrete Legendre transformg• of g defined by (20)Z (i.e., (20) with p ∈ Zn ). Then we have
ρ(X) = |X| − ρ• (χX )16(X ⊆ V).

(40)

This can be shown as follows: ρ• (χX ) = maxY {|X ∩ Y| − ρ(Y) | Y ⊆ V} = maxY {|X ∩ Y| − ρ(Y) |X ⊆ Y ⊆ V} = maxY {|X| − ρ(Y) | X ⊆ Y ⊆ V} = |X| − ρ(X); see also [18, Lemma 6.2]. Since ρ issubmodular, g is L\ -convex, and hence g• (= ρ• ) is M\ -convex by conjugacy (Theorem 12). Thenthe expression (40) shows that ρ is M\ -concave.
A weighted matroid rank function, represented asX
ρ(X) = max{ wi | I ∈ I, I ⊆ X}
(X ⊆ V)(41)i∈Iwith a nonnegative vector w ∈ Rn , is also M\ -concave [62, 63]. It is noted that a polymatroid rankfunction is not necessarily M\ -concave.

6.2

Greedy algorithm

M\ -concave set functions admit the following local characterization of global maximum, an immediate corollary of Theorem 7.
Theorem 19. For an M\ -concave set function ρ : 2V → R and a subset X ⊆ V, we have ρ(X) ≥ ρ(Y)(∀ Y ⊆ V) if and only if
ρ(X) ≥ max {ρ((X \ {i}) ∪ { j}), ρ(X \ {i}), ρ(X ∪ { j})}.
i∈X, j∈V\X

A natural greedy algorithm works for maximization of an M\ -concave set function ρ:
S0: Put X := ∅.
S1: Find j ∈ V \ X that maximizes ρ(X ∪ { j}).
S2: If ρ(X) ≥ ρ(X ∪ { j}), then stop (X is a maximizer of ρ).
S3: Set X := X ∪ { j} and go to S1.
This algorithm may be regarded as a variant of the algorithm of Dress–Wenzel [9] for valuatedmatroids, and the validity can be shown similarly.

6.3 Intersection algorithm
Edmonds’s matroid intersection/union algorithms show that we can efficiently maximize ρ1 (X) +ρ2 (V \ X) and ρ1 (X) + ρ2 (X) − |X| for two matroid rank functions ρ1 and ρ2 . It should be clearthat maxX {ρ1 (X) + ρ2 (V \ X)} is equal to the rank of the union of two matroids (V, ρ1 ) and (V, ρ2 ),and that maxX {ρ1 (X) + ρ2 (X) − |X|} is equal to the maximum size of a common independent set
for matroid (V, ρ1 ) and the dual of matroid (V, ρ2 ). We note here that both ρ1 (X) + ρ2 (V \ X) andρ1 (X) + (ρ2 (X) − |X|) are submodular functions that are represented as a sum of two M\ -concave
functions.
Edmonds’s intersection algorithm can be generalized for M\ -concave functions. A sum of two\
M -concave set functions can be maximized in polynomial time by means of a variant of the valuated matroid intersection algorithm [37, 38]; see also [41, 42, 43]. It follows from the M-convex
intersection theorem (Theorem 16) that, for two M\ -concave set functions ρ1 and ρ2 , X maximizes
ρ1 (X) + ρ2 (X) if and only if there exists p∗ ∈ Rn such that X maximizes both ρ1 (X) + p∗ (X) andPρ1 (X) − p∗ (X) at the same time, where p∗ (X) = i∈X p∗i .

Conclusion
Efficient algorithms are available for minimization of L-convex and M-convex functions [43, Chapter
10]. The complexity analysis for the L-convex function minimization algorithm of [44] is improvedin [31, 53]. We also refer to [61, 69] for M-convex function minimization, and [25] for the submodular flow problem, or equivalently for the Fenchel duality. Most of the efficient algorithms employ
scaling techniques based on proximity theorems; see [26, 36, 55] for proximity theorems.
Discrete convex functions appear naturally in operations research. Multimodular functions,which are L\ -convex functions in disguise, are used in queueing theory [1, 2, 22, 45] and inventory theory [65, 72].
17

A jump system [3] is a generalization of a matroid, a delta-matroid and a base polyhedron of an
integral polymatroid (or a submodular system). The concept of M-convex functions can be extended
to functions on constant-parity jump systems [46]. For x, y ∈ Zn we call s ∈ Zn an (x, y)-increment
if s = χi for some i ∈ supp+ (y − x) or s = −χi for some i ∈ supp− (y − x). We call f : Zn → R an
M-convex function (on a constant-parity jump system) if it satisfies the following exchange property:
For any x, y ∈ domZ f and any (x, y)-increment s, there exists an (x + s, y)-increment t such thatf (x) + f (y) ≥ f (x + s + t) + f (y − s − t).
It then follows that domZ f is a constant-parity jump system. Theorem 7 can be extended and operations such as infimal convolution can be generalized. See [28, 29, 30, 64].

References[1] E. Altman, B. Gaujal, and A. Hordijk: Multimodularity, convexity, and optimization properties,
Mathematics of Operations Research, 25 (2000), 324–347.
[2] E. Altman, B. Gaujal, and A. Hordijk: Discrete-Event Control of Stochastic Networks: Multimodularity and Regularity, Lecture Notes in Mathematics, 1829, Springer-Verlag, Heidelberg,
2003.
[3] A. Bouchet and W. H. Cunningham: Delta-matroids, jump systems, and bisubmodular polyhedra, SIAM Journal on Discrete Mathematics, 8 (1995), 17–32.
[4] N. Buchbinder, M. Feldman, J. Naor, R. Schwartz: A tight linear time (1/2)-approximation for
unconstrained submodular maximization. Proceedings of the 53th Annual IEEE Symposium on
Foundation of Computer Science, pp. 649–658, New Brunswick, New Jersey, October 2012.
[5] N. Buchbinder, M. Feldman, J. Naor, R. Schwartz: Submodular maximization with cardinality constraints. Proceedings of the 25th ACM-SIAM Symposium on Discrete Algorithms
pp. 1433-1452, ACM, New York, 2014.
[6] G. Calinescu, C. Chekuri, M. Pál, and J. Vondrák: Maximizing a submodular set function
subject to a matroid constraint, SIAM Journal on Computing, 40 (2011), 1740–1766.
[7] M. Conforti and G. Cornuéjols: Submodular set functions, matroids and the greedy algorithm:
tight worst-case bounds and some generalizations of the Rado–Edmonds theorem, Discrete
Applied Mathematics, 7 (1984), 251–274.
[8] W. J. Cook, W. H. Cunningham, W. R. Pulleyblank, and A. Schrijver: Combinatorial Optimization, John Wiley and Sons, New York, 1998.
[9] A. W. M. Dress and W. Wenzel: Valuated matroid: A new look at the greedy algorithm, Applied
Mathematics Letters, 3 (1990), 33–35.
[10] A. W. M. Dress and W. Wenzel: Valuated matroids, Advances in Mathematics, 93 (1992),
214–250.
[11] J. Edmonds: Submodular functions, matroids and certain polyhedra, in: R. Guy, H. Hanani, N.
Sauer, and J. Schönheim, eds., Combinatorial Structures and Their Applications, Gordon andBreach, New York, 1970, 69–87. Also in: M. Jünger, G. Reinelt, G. Rinaldi, eds., Combinatorial Optimization—Eureka, You Shrink!, Lecture Notes in Computer Science, 2570, SpringerVerlag, Berlin, 2003, 11–26.
[12] P. Favati and F. Tardella: Convexity in nonlinear integer programming, Ricerca Operativa, 53(1990), 3–44.
[13] U. Feige, V. Mirrokni, and J. Vondrak: Maximizing non-monotone submodular functions,
SIAM Journal on Computing, 40 (2011), 1133–1153.
[14] M. L. Fisher, G. L. Nemhauser, and L.A. Wolsey: An analysis of approximations for maximizing submodular set functions II, Mathematical Programming Study, 8 (1978), 73–87.
18

[15] A. Frank: A weighted matroid intersection algorithm, Journal of Algorithms, 2 (1981), 328–
336.
[16] A. Frank: An algorithm for submodular functions on graphs, Annals of Discrete Mathematics,
16 (1982), 97–120.
[17] S. Fujishige: Theory of submodular programs: A Fenchel-type min-max theorem and subgradients of submodular functions, Mathematical Programming, 29 (1984), 142–155.
[18] S. Fujishige: Submodular Functions and Optimization, 2nd ed., Annals of Discrete Mathematics, 58, Elsevier, 2005.
[19] S. Fujishige and K. Murota: Notes on L-/M-convex functions and the separation theorems,
Mathematical Programming, 88 (2000), 129–146.
[20] S. Fujishige and A. Tamura: A two-sided discrete-concave market with possibly bounded side
payments: An approach by discrete convex analysis, Mathematics of Operations Research, 32(2007), 136–155.
[21] M. Fukushima, Y. Oshima, and M. Takeda: Dirichlet Forms and Symmetric Markov Processes,
Walter de Gruyter, Berlin, 1994.
[22] B. Hajek: Extremal splittings of point processes, Mathematics of Operations Research, 10(1985), 543–556.
[23] H. Hirai and K. Murota: M-convex functions and tree metrics, Japan Journal of Industrial andApplied Mathematics, 21 (2004), 391–403.
[24] S. Iwata: Submodular function minimization, Mathematical Programming, Series B, 112(2007), 45–64.
[25] S. Iwata, S. Moriguchi, and K. Murota: A capacity scaling algorithm for M-convex submodular
flow, Mathematical Programming, 103 (2005), 181–202.
[26] S. Iwata and M. Shigeno: Conjugate scaling algorithm for Fenchel-type duality in discrete
convex optimization, SIAM Journal on Optimization, 13 (2003), 204–211.
[27] P. M. Jensen and B. Korte: Complexity of matroid property algorithms, SIAM Journal on
Computing, 11 (1982), 184–190.
[28] Y. Kobayashi and K. Murota: Induction of M-convex functions by linking systems, Discrete
Applied Mathematics, 155 (2007), 1471–1480.
[29] Y. Kobayashi, K. Murota, and K. Tanaka: Operations on M-convex functions on jump systems,
SIAM Journal on Discrete Mathematics, 21 (2007), 107–129.
[30] Y. Kobayashi and K. Takazawa: Even factors, jump systems, and discrete convexity, Journalof Combinatorial Theory, Series B, 99 (2009), 139–161.
[31] V. Kolmogorov and A. Shioura: New algorithms for convex cost tension problem with application to computer vision, Discrete Optimization, 6 (2009), 378–393.
[32] B. Korte and J. Vygen: Combinatorial Optimization: Theory and Algorithms, 3rd ed.,Springer-Verlag, Berlin, 2006.
[33] L. Lovász: Matroid matching and some applications, Journal of Combinatorial Theory (B), 28(1980), 208–236.
[34] L. Lovász: Submodular functions and convexity, in: A. Bachem, M. Grötschel and B. Korte,eds., Mathematical Programming—The State of the Art, Springer-Verlag, Berlin, 1983, 235–
257.
[35] S. T. McCormick: Submodular function minimization. in: K. Aardal, G. Nemhauser, and R.
Weismantel, eds., Handbook on Discrete Optimization, Elsevier Science Publishers, Berlin,
2006, Chapter 7, 321–391.
19

[36] S. Moriguchi, K. Murota, and A. Shioura: Scaling algorithms for M-convex function minimization, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E85-A (2002), 922–929.
[37] K. Murota: Valuated matroid intersection, I: optimality criteria, SIAM Journal on Discrete
Mathematics, 9 (1996), 545–561.
[38] K. Murota: Valuated matroid intersection, II: algorithms, SIAM Journal on Discrete Mathematics, 9 (1996), 562–576.
[39] K. Murota: Convexity and Steinitz’s exchange property, Advances in Mathematics, 124 (1996),
272–311.
[40] K. Murota: Discrete convex analysis, Mathematical Programming, 83 (1998), 313–371.
[41] K. Murota: Submodular flow problem with a nonseparable cost function, Combinatorica, 19(1999), 87–109.
[42] K. Murota: Matrices and Matroids for Systems Analysis, Springer-Verlag, Berlin, 2000.
[43] K. Murota: Discrete Convex Analysis, SIAM Monographs on Discrete Mathematics and Applications, Vol. 10, Society for Industrial and Applied Mathematics, Philadelphia, 2003.
[44] K. Murota: On steepest descent algorithms for discrete convex functions, SIAM Journal on
Optimization, 14 (2003), 699–707.
[45] K. Murota: Note on multimodularity and L-convexity, Mathematics of Operations Research,
30 (2005), 658–661.
[46] K. Murota: M-convex functions on jump systems: A general framework for minsquare graphfactor problem, SIAM Journal on Discrete Mathematics, 20 (2006), 213–226.
[47] K. Murota: Recent developments in discrete convex analysis, in: W. Cook, L. Lovász, and J.
Vygen, eds., Research Trends in Combinatorial Optimization, Springer-Verlag, Berlin, 2009,
219–260.
[48] K. Murota: Submodular function minimization and maximization in discrete convex analysis,
RIMS Kokyuroku Bessatsu, B23 (2010), 193-211.
[49] K. Murota and A. Shioura: M-convex function on generalized polymatroid, Mathematics ofOperations Research, 24 (1999), 95–105.
[50] K. Murota and A. Shioura: Extension of M-convexity and L-convexity to polyhedral convex
functions, Advances in Applied Mathematics, 25 (2000), 352–427.
[51] K. Murota and A. Shioura: Conjugacy relationship between M-convex and L-convex functions
in continuous variables, Mathematical Programming, 101 (2004), 415–433.
[52] K. Murota and A. Shioura: Fundamental properties of M-convex and L-convex functions incontinuous variables, IEICE Transactions on Fundamentals of Electronics, Communications
and Computer Sciences, E87-A (2004), 1042–1052.
[53] K. Murota and A. Shioura: Exact bounds for steepest descent algorithms of L-convex function
minimization, Operations Research Letters, 42 (2014), 361–366.
[54] K. Murota and A. Tamura: On circuit valuation of matroids, Advances in Applied Mathematics,
26 (2001), 192–225.
[55] K. Murota and A. Tamura: Proximity theorems of discrete convex functions, Mathematical
Programming, 99 (2004), 539–562.
[56] G. L. Nemhauser, L.A. Wolsey, and M. L. Fisher: An analysis of approximations for maximizing submodular set functions I, Mathematical Programming, 14 (1978), 265–294.

20

[57] J. G. Oxley: Matroid Theory, Oxford University Press, Oxford, 1992.
[58] A. Recski: Matroid Theory and Its Applications in Electric Network Theory and in Statics,
Springer-Verlag, Berlin, 1989.
[59] R. T. Rockafellar: Convex Analysis, Princeton University Press, Princeton, 1970.
[60] A. Schrijver: Combinatorial Optimization—Polyhedra and Efficiency, Springer-Verlag, Heidelberg, 2003.
[61] A. Shioura: Fast scaling algorithms for M-convex function minimization with application to
the resource allocation problem, Discrete Applied Mathematics, 134 (2003), 303–316.
[62] A. Shioura: On the pipage rounding algorithm for submodular function maximization: a view
from discrete convex analysis, Discrete Mathematics, Algorithms and Applications, 1 (2009),
1–23.
[63] A. Shioura: Matroid rank functions and discrete concavity, Japan Journal of Industrial andApplied Mathematics, 29 (2012), 535–546.
[64] A. Shioura and K. Tanaka: Polynomial-time algorithms for linear and convex optimization on
jump systems, SIAM Journal on Discrete Mathematics, 21 (2007), 504–522.
[65] D. Simchi-Levi, X. Chen, J. Bramel: The Logic of Logistics: Theory, Algorithms, and Applications for Logistics Management, 3rd ed. Springer-Verlag, New York, 2014.
[66] D. Speyer: Tropical linear spaces, arXiv:math.CO/0410455, 2004.
[67] D. Speyer and B. Sturmfels: The tropical Grassmannian, Advances in Geometry, 4 (2004),
389–411.
[68] A. Tamura: Applications of discrete convex analysis to mathematical economics, Publicationsof Research Institute for Mathematical Sciences, 40 (2004), 1015–1037.
[69] A. Tamura: Coordinatewise domain scaling algorithm for M-convex function minimization,
Mathematical Programming, 102 (2005), 339–354.
[70] D. M. Topkis: Supermodularity and Complementarity, Princeton University Press, Princeton,
NJ, 1998.
[71] N. White, ed.: Theory of Matroids, Cambridge University Press, London, 1986.
[72] P. Zipkin: On the structure of lost-sales inventory models, Operations Research, 56 (2008),
937–944.

21