Appendix

A.1 Convexity

This section contains a few basic facts on convex functions and on convex sets. For further facts we refer to [232], from where we also took some of the material in this section. In the sequel, E will denote a general real vector space.

Definition A.1. A subset C of E is called convex if λx + (1 − λ)y ∈ C whenever x, y ∈ C and 0 ≤ λ ≤ 1.

◊

A convex combination of x1, . . . , xn ∈ E is of the form

with real numbers λi ≥ 0 satisfying λ1 + · · · + λn = 1.

Proposition A.2. A subset C of E is convex if and only if it contains all convex combinations of its elements.

Proof. If C contains all convex combinations of its elements, then it is convex, as λx + (1 − λ)y ∈ C for 0 ≤ λ ≤ 1 is clearly a convex combination of x and y. Conversely, we use induction on n in (A.1). The case n = 2 follows again from Definition A.1. So suppose that C contains all convex combinations for some n ≥ 2, and consider x = λ1x1 + ·· · λn+1xn+1, where xi ∈ C, λi ≥ 0 and λ1 + ·· · + λn+1 = 1. If λn+1 = 0, we are done. Otherwise,

where n = λn+λn+1 > 0 and xn = αxn+(1−α)xn+1 for α := λn/n ∈ [0, 1). The convexity of C implies xn ∈ C. Since moreover λ1 + · · · + λn−1 + n = 1, the induction hypothesis now implies x ∈ C.

Definition A.3. Let A be a nonempty subset of E. The convex hull of A ⊂ E is a set denoted by conv A and defined as the following intersection,

Since E is a convex set containing A, it is clear that (A.2) is well-defined. It follows in particular that A ⊂ conv A.

Proposition A.4. The convex hull of a nonempty set A ⊂ E admits the following alternative characterizations.

(a) conv A is the smallest convex set containing A.

(b) conv A is equal to the set of all convex combinations of elements of A, i.e.,

Proof. (a) It is easy to see that the intersection of convex sets is again convex. Hence, conv A is indeed a convex set. It is moreover clear from the definition that there can be no smaller convex set C containing A.

(b) Let C0 denote the right-hand side of (A.3). It is easy to see that C0 is convex and contains A. Therefore, conv A ⊂ C0. Conversely, let C be any convex set containing A. by Proposition A.2, C must contain every convex combination of elements of A. Hence, C0 ⊂ C. This implies C0 ⊂ conv A and concludes the proof.

Now we consider specifically E = ℝn and denote by

the Euclidean inner product of x = (x1, . . . , xn) ∈ ℝn and y = (y1, . . . , yn) ∈ ℝn. By

we denote the Euclidean norm of x ∈ ℝn. The following proposition is a version of Minkowski’s separating hyperplane theorem.

Proposition A.5. Suppose thatC ⊂ ℝ n is a nonempty convex set with 0 /∈ C . Then there exists η ∈ ℝn with η · x ≥ 0 for all x ∈ C , and with η · x0 > 0 for at least one x0 ∈ C . If, moreover, infx∈C |x| > 0, then one can find η ∈ ℝn with infx∈C η · x > 0.

Proof. First we consider the case in which α := infx∈C |x| > 0. This infimum is attained by some nonzero y in the closure C of C . Indeed, x |x| is a continuous function and hence attains its minimum on the compact set that is obtained by intersecting C with the closed ball of radius α + 1 centered in 0. Since the set C is again convex, we have αx + (1 − α)y ∈ C for each x ∈ C and all α ∈ [0, 1]. Thus

Dividing by α and sending α to 0 yields y · x ≥ y · y > 0, and so we can take η := y.

The case in which infx∈C |x| = 0 is more subtle. For the first step, let {e1, . . . , e k} be a maximal collection of linearly independent vectors in C . Then each x ∈ C can be expressed as a linear combination of e1, . . . , e k. Let

We claim that βz does not belong C for each β > 0. To prove this claim, we assume by way of contradiction that βz ∈ for some β > 0. Then there are zn ∈ converging C C the convergence to βz. If we write then zn → βz is equivalent to for all i. It follows that for some n0 ∈ ℕ all coefficients are strictly negative. Let

Then αj > 0 for each j and α0 + · · · + αk = 1. Thus, the convexity of C implies that

which is a contradiction. Hence, βz cannot be contained in C .

In the second step, we can now prove the existence of a separating η in the case in which 0 is a boundary point of C , and thus infx∈C |x| = 0. Wemay assume without loss of generality that C is not contained in a proper linear subspace of ℝn; otherwise we replace ℝn with the Euclidean space spanned by the vectors e1, . . . , e k constructed in the preceding step. Take a sequence βm ↓ 0 and let Cm := C −βmz, where z was constructed in the preceding step. Then 0 /∈ C −βmz = C m and consequently infx∈Cm |x| > 0.Hence, the first part of the proof yields ηm ∈ ℝn such that infx∈Cm ηm ·x > 0. Wemay assume without loss of generality that |ηm| = 1 for all m. By compactness of the (n−1)-dimensional unit sphere, there exists a convergent subsequence with limit η. Thus,

for all x ∈ C . Since η is nonzero and C is not contained in a proper linear subspace of ℝn, the case η · x = 0 for all x ∈ C cannot occur, and so there must be some x0 ∈ C with η · x0 > 0.

Now we consider again the situation of a general real vector space E.

Definition A.6. Let C be a convex subset of E. A function f : C → [−∞, +∞] is called convex if its epigraph,

is a convex subset of E × ℝ. The effective domain of f is defined as

A convex function f is called proper if dom f ≠ ∅ and if f does not take the value −∞. A function u : C → [−∞, +∞] is called concave if f := −u is convex. A concave function is called proper, if f := −u is is a proper convex function.

◊

Exercise A.1.1. Let C be a convex subset of E and f : C → ℝ a function. Show that the following conditions are equivalent.

(a) f is convex.

(b) For all x, y ∈ C and α ∈ [0, 1], we have

(c) For x1, . . . , xn ∈ E and λ1, . . . , λn ≥ 0 with λ1 + · · · + λn = 1,

◊

Often, the convexity of a function is defined by requiring the condition (A.4) instead of requiring the convexity of its epigraph. Note, however, that the right-hand side of (A.4) may not be well defined if f takes both −∞ and +∞ as values.

A proper convex function f : C → ℝ ∪ {+∞} can be extended to the entire space E by putting f (x) := +∞if x ∈ E C. It is easy to verify that this extension is again a proper convex function. It is therefore sufficient to study proper convex functions that are defined on the full space E.

Now we consider the special situation in which f is a proper convex function on E = ℝ. In this case, dom f is a real interval. The following proposition summarizes continuity and differentiability properties of a proper convex function on its effective domain.

Proposition A.7. Let f be a proper convex function on ℝ, and denote by D the interior of dom f .

(a) f is upper semicontinuous on dom f and locally Lipschitz continuous on D.

(b) f admits left- and right-hand derivatives

at each y ∈ D. Both and are increasing functions and satisfy

(c) The right-hand derivative is right-continuous, the left-hand derivative is left-continuous.

(d) f is differentiable a.e. in D, and for any x0 ∈ D

Proof. We first prove part (b). For x, y, z ∈ D with x < y < z, we take α ∈ (0, 1) such that y = αz + (1 − α)x. Using the convexity of f , one gets

Thus, the difference quotient

is an increasing function of x, which shows the existence of the left- and right-hand derivatives. Moreover, we get for y < z.

(a): Let z ∈ dom f , and take a sequence (xn) ⊂ dom f such that xn → z. Without loss of generality, we may assume that xn ↓ z or xn ↑ z. In either case, xn = δn x1 +(1− δn)z, where δn ↓ 0. Convexity of f yields

and so f is upper semicontinuous. To prove local Lipschitz continuity, take a ≤ x < y ≤ b such that [a, b] ⊂ D. We get from part (b) that

Hence, f is a Lipschitz continuous function on [a, b] with Lipschitz constant L :=

(c): Continuity of f shows that for x < z

Taking z ↓ x yields Since is increasing, we must in fact have as y ↓ x. In the same way, one shows left-continuity of

(d): Since the function f is Lipschitz continuous, it is absolutely continuous. By Lebesgue’s differentiation theorem, f is hence a.e. differentiable and equal to the integral of its derivative, which is equal to

Exercise A.1.2. Let f : (0,1) → ℝ be a function that is bounded from above and satisfies

Prove that f is continuous and conclude then that f is convex.

Note: See [148, p. 96] for the construction of a function f : ℝ → ℝ that satisfies f (x + y) = f (x) + f (y) for x, y ∈ ℝ, and hence (A.6), but that is neither convex nor continuous.

◊

Definition A.8. The Fenchel–Legendre transform of a function f : ℝ → ℝ ∪ {+∞} is defined as

◊

If f ≡ +∞, then f ∗ is a convex and lower semicontinuous as the supremum of the affine functions y y x − f (x). If f is a proper convex function, then f ∗ is also called the conjugate function of f .

Proposition A.9. Let f be a proper convex function on ℝ.

(a) For all x, y ∈ ℝ,

with equality if x belongs to the interior of dom f and if

(b) If f is lower semicontinuous, then f ∗∗ = f , i.e.,

Proof. (a): The inequality (A.7) is obvious. Now suppose that x0 belongs to the interior of dom f . Proposition A.7 yields for all x in the interior of dom f and, by upper semi-continuity, for all x ∈ ℝ. Hence, f (x) ≥ f (x0) + y0 (x − x0)

whenever This shows that x y0 − f (x) ≤ x0 y0 − f (x0) for all x ∈ ℝ, i.e.,

(b): We first show the following auxiliary claim: If β < f (x0), then there exists an affine function h such that h(x0) = β and h(x) < f (x) for all x. For the proof of this claim consider the epigraph,

It is a nonempty convex set since f is convex and proper, and it is closed due to the lower semicontinuity of f . The point (x0, β) does not belong to epif , and Proposition A.5, applied to C := epif − (x0, β), thus yields some η = (η1, η2) ∈ ℝ2 such that

It follows that

If f (x0) < ∞, we get η1x0 + η2f (x0) > η1x0 + η2β. Hence η2 > 0, and one checks that

is as desired. If f (x0) = ∞ and η2 > 0, then the same definition works. Now assume that f (x0) = ∞ and η2 = 0. Since f is proper, the first step of the proof of our claim, applied with some x0 ∈ dom f , allows us to construct an affine function g with g < f . If g(x0)≥ β, then h := g + β − g(x0) is as desired. Otherwise, we let h(x) := δ − η1x. Then h(x0) > 0 and h(x) ≤ 0 for x ∈ dom f . It follows that h(x) := g(x) + λh(x) for λ := (β−g(x0))/h(x0) > 0 is as desired. This concludes the proof of our auxiliary claim.

Now we can prove part (b) of the assertion. It is clear from the definition that f ≥ f ∗∗. Suppose there exists a point x0 such that f (x0) > f ∗∗(x0). Take β strictly between f ∗∗(x0) and f (x0). By the auxiliary claim, there exists an affine function h < f such that h(x0) = β. Let us write h(x) = y0x + α. Then it follows that f ∗(y0)≤ −α and hence

which is a contradiction.