“sidca2003/9
page 110Chapter 1. Introduction to the Central Concepts

1.2

Useful Properties of Convex Functions

We have already mentioned that convex functions are tractable in optimization (orminimization) problems and this is mainly because of the following properties:
1. Local optimality (or minimality) guarantees global optimality;
2. Duality such as min-max relation and separation theorem holds good.
This section is to give more specific descriptions of these properties, and to discuss
their possible versions for discrete functions.
Let us first recall the definition of a convex function. A function f : Rn →R ∪ {+∞} is said to be convex ifλf (x) + (1 − λ)f (y) ≥ f (λx + (1 − λ)y)

(1.2)

for all x, y ∈ Rn and for all λ with 0 ≤ λ ≤ 1, where it is understood that theinequality is satisfied if f (x) or f (y) is equal to +∞. The inequality (1.2) implies
that the set
S = {x ∈ Rn | f (x) < +∞},
called the effective domain of f , is a convex set. Hence the present definition ofa convex function coincides with the one in (1.1) that makes an explicit reference
to the effective domain S. A special case of inequality (1.2) for λ = 1/2 yields themidpoint convexityµ¶f (x) + f (y)x+y≥f(x, y ∈ Rn ),(1.3)
22and, conversely, this implies convexity, provided f is continuous. We often assume(explicitly or implicitly) that f (x) < +∞ for some x ∈ Rn whenever we talk about
a convex function f . A function h : Rn → R ∪ {−∞} is said to be concave if −h isconvex.
A point (or vector) x is said to be a global optimum of f if the inequality
f (x) ≤ f (y)(1.4)

holds for every y, and x is a local optimum if this inequality holds for every y insome neighborhood of x. Obviously, global optimality implies local optimality. The
converse is not true in general, but it is true for convex functions.
Theorem 1.1. For a convex function, global optimality (or minimality) is guaranteed by local optimality.
Proof. Let x be a local optimum of a convex function f . Then we have f (z) ≥ f (x)for any z in some neighborhood U of x. For any y, z = λx + (1 − λ)y belongs to Ufor λ < 1 sufficiently close to 1, and it follows from (1.2) that
λf (x) + (1 − λ)f (y) ≥ f (λx + (1 − λ)y) = f (z) ≥ f (x).

“sidca2003/9
page 11.2. Useful Properties of Convex Functions

11This implies f (y) ≥ f (x).
The above theorem is significant and useful in that it reduces the global property to a local one. Still it refers to an infinite number of points or directions aroundx for the local optimality. In considering discrete structures on top of convexity we
may hope that a fixed and finite set of directions suffices to guarantee the local
optimality. For example, in the simplest case of a separable convex function
f (x) =nX

fi (x(i)),

(1.5)

i=1

which is the sum of univariate convex functions5) fi (x(i)) in each component of
x = (x(i) | i = 1, . . . , n), it suffices to check for local optimality in 2n directions,
positive and negative directions of the coordinate axes. Such phenomenon of “discreteness in direction”, so to speak, is a reflection of the combinatorial structureof separable convex functions. Although the combinatorial structure of separable
convex functions is too simple for further serious considerations, similar phenomenaof “discreteness in direction” occur in nontrivial ways for L-convex or M-convex
functions, as we see in §1.4.
We now go on to the second issue of duality and conjugacy. For a function f(not necessarily convex), the convex conjugate f • : Rn → R ∪ {+∞} is defined byf • (p) = sup{hp, xi − f (x) | x ∈ Rn }wherehp, xi =n
Xp(i)x(i)(p ∈ Rn ),(1.6)
(1.7)

i=1

for p = (p(i) | i = 1, . . . , n) and x = (x(i) | i = 1, . . . , n). The function f • isalso referred to as the (convex) Legendre–Fenchel transform of f , and the mapping
f 7→ f • as the (convex) Legendre–Fenchel transformation.
For example, for f (x) = exp(x), where n = 1, we see
 p log p − p (p > 0)0(p = 0)f • (p) =+∞(p < 0)by a simple calculation. See Fig. 1.3 for the geometric meaning in the case of n = 1.
The Legendre–Fenchel transformation gives a one-to-one correspondence inthe class of well-behaved convex functions, called “closed proper convex functions,”
where the precise meaning of this technical terminology (not important here) will
be explained later in §3.1. Notation f •• means (f • )• , the conjugate of the conjugate
function of f .
Theorem 1.2 (Conjugacy). The Legendre–Fenchel transformation f 7→ f • gives
a symmetric one-to-one correspondence in the class of all closed proper convex functions. That is, for a closed proper convex function f , f • is a closed proper convex
function and f •• = f .
5) A univariate function means a function in a single variable.

“sidca2003/
page 112Chapter 1. Introduction to the Central Concepts

Y6

Y = f (x)−f • (p)Y = hp, xi − f • (p)x
Figure 1.3. Conjugate function (Legendre–Fenchel transform)

Y = f (x)Y = α∗ + hp∗ , xi

Y 6
Y = h(x)x
Figure 1.4. Separation for convex and concave functions

Similarly, for a function h the concave conjugate h◦ : Rn → R ∪ {−∞} isdefined byh◦ (p) = inf{hp, xi − h(x) | x ∈ Rn }(p ∈ Rn ).

(1.8)

The duality principle in convex analysis can be expressed in a number of different forms. One of the most appealing statements is in the form of the separation
theorem, which asserts the existence of a separating affine function Y = α∗ + hp∗ , xi
for a pair of convex and concave functions (see Fig. 1.4).
Theorem 1.3 (Separation theorem).
Let f : Rn → R ∪ {+∞} and h :Rn → R ∪ {−∞} be convex and concave functions, respectively (satisfying certain

“sidca2003/9
page 11.2. Useful Properties of Convex Functions

13regularity conditions). If 6)
f (x) ≥ h(x)(∀x ∈ Rn ),there exist α∗ ∈ R and p∗ ∈ Rn such thatf (x) ≥ α∗ + hp∗ , xi ≥ h(x)(∀x ∈ Rn ).

It is admitted that the statement above is mathematically incomplete, referring to “certain regularity conditions,” which will be specified later in §3.1.
Another expression of the duality principle is in the form of the Fenchel duality.
This is a min-max relation between a pair of convex and concave functions and theirconjugate functions. The “certain regularity conditions” in the statement below willbe specified later.
Theorem 1.4 (Fenchel duality). Let f : Rn → R ∪ {+∞} and h : Rn →R∪{−∞} be convex and concave functions, respectively (satisfying certain regularityconditions). Thenmin{f (x) − h(x) | x ∈ Rn } = max{h◦ (p) − f • (p) | p ∈ Rn }.
Such a min-max theorem is computationally useful in that it affords a certificate of optimality. Suppose that we want to minimize f (x) − h(x) and havex = x̂ as a candidate for the minimizer. How can we verify or prove that x̂ isindeed an optimal solution? One possible way is to demonstrate a vector p̂ suchthat f (x̂) − h(x̂) = h◦ (p̂) − f • (p̂). This implies the optimality of x̂ by virtue ofthe min-max theorem. The vector p̂, often called a dual optimal solution, serves asa certificate for the optimality of x̂. It is emphasized that the min-max theorem
guarantees the existence of such a certificate p̂ for any optimal solution x̂. It is alsomentioned that the min-max theorem does not tell us how to find optimal solutionsx̂ and p̂.
It is one of the recurrent themes in discrete convexity how the conjugacy
and the duality above should be adapted in discrete settings. To be specific, let
us consider integer-valued functions on integer lattice points, and discuss possible
notions of conjugacy and duality for f : Zn → Z ∪ {+∞} and h : Zn → Z ∪{−∞}. Some ingredients of discreteness (integrality) are naturally expected in theformulation of conjugacy and duality. This amounts to discussing another kindof discreteness, “discreteness in value” so to speak, in contrast to “discreteness indirection” mentioned above.
Discrete versions of the Legendre–Fenchel transformations can be defined byf • (p) = sup{hp, xi − f (x) | x ∈ Zn }◦nh (p) = inf{hp, xi − h(x) | x ∈ Z }6) Notation ∀ means “for all”, “for any,” or “for each.”(p ∈ Zn ),n(p ∈ Z ).

(1.9)
(1.10)

“sidca2003/9
page 114

Chapter 1. Introduction to the Central Concepts

They are meaningful as transformations of discrete functions, in that the resulting
functions f • and h◦ are also integer-valued on integer points. We call (1.9) and(1.10), respectively, convex and concave discrete Legendre–Fenchel transformations.
With these definitions, a discrete version of the Fenchel duality would read asfollows.
[Discrete Fenchel-type duality theorem] Let f : Zn → Z ∪ {+∞} andh : Zn → Z ∪ {−∞} be “convex” and “concave” functions, respectively(in an appropriate sense). Thenmin{f (x) − h(x) | x ∈ Zn } = max{h◦ (p) − f • (p) | p ∈ Zn }.
Such a theorem, if any, claims a min-max duality relation for integer-valued nonlinear functions, which is not likely to be true for an arbitrary class of discrete
functions. It is emphasized that the definition of “convexity” itself is left open in
the above generic statement, although h should be called “concave” when −h is“convex.”
As for the separation theorem, a possible discrete version would read as follows,
imposing integrality (α∗ ∈ Z, p∗ ∈ Zn ) on the separating affine function. SeeFig. 1.5.
[Discrete separation theorem] Let f : Zn → Z ∪ {+∞} and h : Zn →Z ∪ {−∞} be “convex” and “concave” functions, respectively (in anappropriate sense). Iff (x) ≥ h(x)(∀x ∈ Zn ),there exist α∗ ∈ Z and p∗ ∈ Zn such thatf (x) ≥ α∗ + hp∗ , xi ≥ h(x)(∀x ∈ Zn ).

Again the precise definition of “convexity” remains unspecified here.
To motivate our framework to be introduced in the subsequent sections, let
us try with a naive and natural candidate for the “convexity” concept, which turns
out to be insufficient.
Let us (temporarily) define f : Zn → Z ∪ {+∞} to be “convex” if it canbe extended to a convex function on Rn , i.e., if there exists a convex function
f : Rn → R ∪ {+∞} such thatf (x) = f (x)(x ∈ Zn ).

(1.11)

This is illustrated in Fig. 1.6.
In the one-dimensional case (with n = 1) this is equivalent to defining f : Z →Z ∪ {+∞} to be “convex” iff (x − 1) + f (x + 1) ≥ 2f (x)(∀x ∈ Z).

(1.12)

As is easily verified, the discrete separation theorem as well as the discrete Fenchel
duality holds with this definition in the case of n = 1.

“sidca2003/9
page 11.2. Useful Properties of Convex Functions

15Y = f (x)Y = α∗ + hp∗ , xi

Y = h(x)Figure 1.5. Discrete separation

66ffxxFigure 1.6. “Convex” and non-“convex” discrete functions

When it comes to higher dimensions, the situation is not that simple. The
following examples demonstrate that the discrete separation fails with this naivedefinition of “convexity.”
Example 1.5. [failure of discrete separation] Consider two discrete functions
defined byf (x) = max(0, x(1) + x(2)),h(x) = min(x(1), x(2)),

where x = (x(1), x(2)) ∈ Z2 . They are integer-valued on the integer lattice Z2
with f (0) = h(0) = 0, and can be extended, respectively, to a convex function
f : R2 → R and a concave function h : R2 → R given by
f (x) = max(0, x(1) + x(2)),h(x) = min(x(1), x(2)),

where x = (x(1), x(2)) ∈ R2 . Since f (x) ≥ h(x) (∀x ∈ R2 ), the separation theorem
in convex analysis (Theorem 1.3) applies to the pair (f , h), to yield a (unique)separating affine function hp∗ , xi with p∗ = (1/2, 1/2). We have f (x) ≥ hp∗ , xi ≥h(x) for all x ∈ R2 , and a fortiori, f (x) ≥ hp∗ , xi ≥ h(x) for all x ∈ Z2 . However,“sidca2003/9
page 116

Chapter 1. Introduction to the Central Concepts

there exists no integral vector p∗ ∈ Z2 such that f (x) ≥ hp∗ , xi ≥ h(x) for allx ∈ Z2 . This demonstrates the failure of the desired discreteness in the separating
affine function.
Example 1.6. [failure of real-valued separation] This example shows that even theexistence of a separating affine function can be denied. For the discrete functions
f (x) = |x(1) + x(2) − 1|,h(x) = 1 − |x(1) − x(2)|,where x = (x(1), x(2)) ∈ Z2 , we have f (x) ≥ h(x) (∀x ∈ Z2 ). There exists,
however, no pair of real number α∗ ∈ R and a real vector p∗ ∈ R2 for whichf (x) ≥ α∗ + hp∗ , xi ≥ h(x) for all x ∈ Z2 . Note that the separation theorem inconvex analysis (Theorem 1.3) does not apply to the pair of their convex/concave
extensions (f , h), which are given by
f (x) = |x(1) + x(2) − 1|,h(x) = 1 − |x(1) − x(2)|for x = (x(1), x(2)) ∈ R2 , since f (1/2, 1/2) < h(1/2, 1/2). This example shows alsothat f ≥ h on Rn does not follow from f ≥ h on Zn .
Similarly, the discrete Fenchel duality fails under the naive definition of “convexity.” The above two examples serve to demonstrate this.
Thus the naive approach to discrete convexity does not work, and some deep
combinatorial or discrete-mathematical considerations are needed. We are now
motivated to look at some results in the area of matroids and submodular functions,which hopefully provide a clue for fruitful definitions of discrete convexity.