18.10 Convex Functions

The chapter so far has studied convex sets. Convex functions have been in the book for longer, as the first subsection recalls, and every finite support function of §04 is one too. This section defines the notion, ties it to convex sets through the epigraph, and proves its basic theorems: Jensen’s inequality, the convexity of a supremum of affine functions, which pays a promise of Chapter 17 §06, a second-derivative test, and continuity. §11 then spends them on three classical inequalities.

Throughout, the field is $\mathbb{R}$ . $V$ is a real vector space, and a set $C \subseteq V$ called convex is convex in the sense of Definition 18.1.1. From the second-derivative test onward we work in $\mathbb{R}^n$ , with the standard inner product and its norm $\left\| \cdot \right\| = \left\| \cdot \right\|_2$ . A function $g$ on an interval of $\mathbb{R}$ is increasing when $s \le t$ implies $g(s) \le g(t)$ , as in Chapter 17 §11, and strictly increasing when $s < t$ implies $g(s) < g(t)$ .

18.10.1. Convex functions and their epigraphs

Look again at three inequalities the book has already proved. For a norm, (N2) and (N3) of Definition 16.1.1 give $\left\| t\mathbf{x} + (1-t)\mathbf{y} \right\| \le t\left\| \mathbf{x} \right\| + (1-t)\left\| \mathbf{y} \right\|$ for $0 \le t \le 1$ . For the top partial sum $s_k(\mathbf{A}) = \sum_{i \le k}\lambda_i(\mathbf{A})$ of a Hermitian matrix, Chapter 17 §06 derived $s_k(t\mathbf{A} + (1-t)\mathbf{B}) \le ts_k(\mathbf{A}) + (1-t)s_k(\mathbf{B})$ from Corollary 17.6.5. And the case $n = 1$ of operator convexity in Definition 17.11.1 (b) reads $f(t a + (1-t)b) \le tf(a) + (1-t)f(b)$ for numbers $a, b$ . It is the same inequality three times, and it deserves a name.

A function is convex when, on every segment of its domain, its graph lies on or below the chord.

Definition 18.10.1 (Convex Function)

Let $C$ be a non-empty convex subset of a real vector space $V$ , and let $f \colon C \to \mathbb{R}$ . Then $f$ is convex if $f\bigl(t\mathbf{x} + (1-t)\mathbf{y}\bigr) \ \le\ tf(\mathbf{x}) + (1-t)f(\mathbf{y})$ for all $\mathbf{x}, \mathbf{y} \in C$ and all real $t$ with $0 \le t \le 1$ . It is strictly convex if the inequality is strict whenever $\mathbf{x} \ne \mathbf{y}$ and $0 < t < 1$ . It is concave, or strictly concave, if $-f$ is convex, or strictly convex.

The epigraph of $f$ is the subset of the real vector space $V \times \mathbb{R}$ , with componentwise operations, $\operatorname{epi} f = \{ (\mathbf{x}, s) \in V \times \mathbb{R} : \mathbf{x} \in C,\ s \ge f(\mathbf{x}) \} .$

In words: take any two points $\mathbf{x}$ and $\mathbf{y}$ of the domain and any point $t\mathbf{x} + (1-t)\mathbf{y}$ between them. The left side is the value of $f$ there. The right side is the value, at the same place, of the straight line through $(\mathbf{x}, f(\mathbf{x}))$ and $(\mathbf{y}, f(\mathbf{y}))$ . So the condition says the chord is never below the graph. Strict convexity forbids the graph to touch the chord anywhere strictly between two distinct points. The epigraph is everything on or above the graph.

The domain must be convex, and this is the only thing to check. The point $t\mathbf{x} + (1-t)\mathbf{y}$ must lie in $C$ , or $f$ is not defined there. That is exactly what Definition 18.1.1 guarantees.

Diagram. Labels: (x, f(x)), (y, f(y)), operatorname epi f

The picture shows $f(x) = 0.35x^2$ on $\mathbb{R}$ : the dashed chord lies above the graph between its endpoints, and the shaded region is the epigraph.

Example (First convex functions)

Check each against Definition 18.10.1.

(a) An affine function $a(\mathbf{x}) = \varphi(\mathbf{x}) + c$ , with $\varphi$ a linear functional on $V$ (Definition 5.1.1) and $c \in \mathbb{R}$ .
(b) A norm $\left\| \cdot \right\|$ on $\mathbb{R}^n$ .
(c) $f(x) = x^2$ on $\mathbb{R}$ , and more generally $q(\mathbf{x}) = \mathbf{x}^{\top}\mathbf{A}\mathbf{x}$ on $\mathbb{R}^n$ for a symmetric $\mathbf{A} \succeq 0$ .

Solution.

(a) Since $\varphi$ is linear and $c = tc + (1-t)c$ , $a\bigl(t\mathbf{x} + (1-t)\mathbf{y}\bigr) = t\varphi(\mathbf{x}) + (1-t)\varphi(\mathbf{y}) + tc + (1-t)c = ta(\mathbf{x}) + (1-t)a(\mathbf{y}) .$ Equality holds, so $a$ is convex, and so is $-a$ : an affine function is both convex and concave, and neither strictly. The constant functions are the degenerate case $\varphi = 0$ . They matter because they show that convexity by itself forces no growth at all.
(b) By (N3) and then (N2) of Definition 16.1.1, with $\lvert t \rvert = t$ and $\lvert 1 - t\rvert = 1 - t$ for $0 \le t \le 1$ , $\left\| t\mathbf{x} + (1-t)\mathbf{y} \right\| \le \left\| t\mathbf{x} \right\| + \left\| (1-t)\mathbf{y} \right\| = t\left\| \mathbf{x} \right\| + (1-t)\left\| \mathbf{y} \right\| .$ A norm is not strictly convex: on the ray through a non-zero $\mathbf{x}$ , $\left\| s\mathbf{x} \right\| = s\left\| \mathbf{x} \right\|$ is linear in $s \ge 0$ , so the chord between $\mathbf{x}$ and $2\mathbf{x}$ lies on the graph.
(c) Expanding and collecting terms, $tx^2 + (1-t)y^2 - \bigl(tx + (1-t)y\bigr)^2 = t(1-t)(x - y)^2 \ \ge\ 0 ,$ and the right side is strictly positive when $x \ne y$ and $0 < t < 1$ . So $x^2$ is strictly convex. The same expansion with $\mathbf{A}$ symmetric gives $tq(\mathbf{x}) + (1-t)q(\mathbf{y}) - q\bigl(t\mathbf{x} + (1-t)\mathbf{y}\bigr) = t(1-t)\,q(\mathbf{x} - \mathbf{y}) ,$ and $q(\mathbf{x} - \mathbf{y}) = \langle \mathbf{A}(\mathbf{x} - \mathbf{y}), \mathbf{x} - \mathbf{y} \rangle \ge 0$ by (P2) of Definition 13.1.1. So $q$ is convex. The case $n = 1$ , $\mathbf{A} = (1)$ , is $x^2$ .

A non-example by minimal change. Replace $x^2$ by $x^3$ on $\mathbb{R}$ . With $x = -2$ , $y = 0$ and $t = \tfrac12$ , the left side is $(-1)^3 = -1$ and the right side is $\tfrac12(-8) + \tfrac12 \cdot 0 = -4$ , and $-1 \le -4$ is false. What fails is the inequality for this pair, on the negative half-line, where the graph bends downward. On the convex domain $(0, \infty)$ the same function is convex, as the one-variable test below shows. So convexity depends on the domain.

Why this definition. The inequality is non-strict so that affine functions and norms, the most important examples, qualify. Requiring it for every $t \in [0, 1]$ , not just $t = \tfrac12$ , is what makes Jensen’s inequality below immediate. The name comes from the epigraph: a function is convex exactly when the set above its graph is convex.

Proposition 18.10.1 (Convex Function, Convex Epigraph)

Let $C \subseteq V$ be non-empty and convex, and let $f \colon C \to \mathbb{R}$ . Then $f$ is convex if and only if $\operatorname{epi} f$ is a convex subset of $V \times \mathbb{R}$ .

Idea. A point $(\mathbf{x}, s)$ lies in the epigraph exactly when $s \ge f(\mathbf{x})$ . So the chord inequality for $f$ and the statement that segments between points of the epigraph stay in it are one inequality, read in two directions.

Proof. $(\Rightarrow)$ Let $(\mathbf{x}, s), (\mathbf{y}, u) \in \operatorname{epi} f$ and $0 \le t \le 1$ . The point $t\mathbf{x} + (1-t)\mathbf{y}$ lies in $C$ , since $C$ is convex, and $f\bigl(t\mathbf{x} + (1-t)\mathbf{y}\bigr) \le tf(\mathbf{x}) + (1-t)f(\mathbf{y}) \le ts + (1-t)u ,$ the second step because $f(\mathbf{x}) \le s$ , $f(\mathbf{y}) \le u$ and $t, 1-t \ge 0$ . So $t(\mathbf{x}, s) + (1-t)(\mathbf{y}, u) \in \operatorname{epi} f$ .

$(\Leftarrow)$ Let $\mathbf{x}, \mathbf{y} \in C$ and $0 \le t \le 1$ . The points $(\mathbf{x}, f(\mathbf{x}))$ and $(\mathbf{y}, f(\mathbf{y}))$ lie in $\operatorname{epi} f$ , so by convexity so does $\bigl(t\mathbf{x} + (1-t)\mathbf{y},\ tf(\mathbf{x}) + (1-t)f(\mathbf{y})\bigr)$ . By the definition of the epigraph this says $f(t\mathbf{x} + (1-t)\mathbf{y}) \le tf(\mathbf{x}) + (1-t)f(\mathbf{y})$ . This proves the proposition.

The same one-line argument shows that every sublevel set $\{\mathbf{x} \in C : f(\mathbf{x}) \le c\}$ of a convex $f$ is convex: if $f(\mathbf{x}) \le c$ and $f(\mathbf{y}) \le c$ , then $f(t\mathbf{x} + (1-t)\mathbf{y}) \le tc + (1-t)c = c$ .

Quick check. Every sublevel set of a convex function is convex. Is the converse true? Is a function $f \colon \mathbb{R} \to \mathbb{R}$ whose sublevel sets are all convex necessarily convex?

Solution. No. Take $f(x) = x^3$ . It is increasing: if $a < b$ then $b^3 - a^3 = (b - a)(a^2 + ab + b^2) > 0$ , since $a^2 + ab + b^2 = (a + \tfrac{b}{2})^2 + \tfrac34b^2$ vanishes only at $a = b = 0$ . So if $x \le z \le y$ and $x^3, y^3 \le c$ , then $z^3 \le y^3 \le c$ . Each sublevel set is therefore an interval, which is convex. But $x^3$ is not convex on $\mathbb{R}$ , by the non-example above.

Warning. A convex function need not be differentiable. The function $\lvert x \rvert$ is a norm on $\mathbb{R}$ , hence convex, and it has a corner at $0$ : its difference quotients $\lvert h\rvert/h$ are $1$ for $h > 0$ and $-1$ for $h < 0$ , so they have no limit. The same corner appears in linear algebra. The map $\mathbf{A} \mapsto \lambda_1(\mathbf{A})$ on Hermitian matrices is convex, as the next two subsections prove, and on the diagonal matrices $\operatorname{diag}(t, -t)$ it equals $\lvert t \rvert$ . The corner sits at $t = 0$ , where the top eigenvalue is repeated.

18.10.2. Jensen’s inequality

The definition speaks of two points. Induction extends it to any finite convex combination (Definition 18.1.3), and that extension is the form in which convexity is most often used.

Theorem 18.10.2 (Jensen’s Inequality)

Let $C \subseteq V$ be non-empty and convex, and let $f \colon C \to \mathbb{R}$ be convex. Let $\mathbf{x}_1, \dots, \mathbf{x}_m \in C$ , and let $w_1, \dots, w_m \ge 0$ with $w_1 + \dots + w_m = 1$ . Then $\sum_i w_i\mathbf{x}_i \in C$ and $f\Bigl(\sum_{i=1}^{m} w_i\mathbf{x}_i\Bigr) \ \le\ \sum_{i=1}^{m} w_if(\mathbf{x}_i) .$ If $f$ is strictly convex and every $w_i > 0$ , equality holds only when $\mathbf{x}_1 = \mathbf{x}_2 = \dots = \mathbf{x}_m$ .

Idea. Split off the last point. The remaining weights add up to $s = 1 - w_m$ , and after dividing by $s$ they are the weights of a convex combination $\mathbf{y}$ of $m - 1$ points, to which induction applies. The whole combination is then $s\mathbf{y} + w_m\mathbf{x}_m$ , a combination of two points, which is where the definition applies.

Proof. We prove both statements by induction on $m \ge 1$ . For $m = 1$ the weight is $w_1 = 1$ , both sides equal $f(\mathbf{x}_1)$ , and the equality clause is empty.

Let $m \ge 2$ and assume both statements for $m - 1$ points. If $w_m = 1$ , every other weight is $0$ , both sides equal $f(\mathbf{x}_m)$ , and the equality clause does not apply since $w_1 = 0$ . Otherwise $s = 1 - w_m = w_1 + \dots + w_{m-1} > 0$ . The numbers $w_i/s$ for $i < m$ are non-negative with sum $1$ , so by the inductive hypothesis $\mathbf{y} = \sum_{i<m}(w_i/s)\mathbf{x}_i$ lies in $C$ and $f(\mathbf{y}) \le \sum_{i<m}\frac{w_i}{s}f(\mathbf{x}_i) . \tag{1}$ Now $\sum_{i=1}^m w_i\mathbf{x}_i = s\mathbf{y} + w_m\mathbf{x}_m$ with $s + w_m = 1$ , so this point lies in $C$ because $C$ is convex, and Definition 18.10.1 gives $\begin{aligned} f(s\mathbf{y} + w_m\mathbf{x}_m) &\le sf(\mathbf{y}) + w_mf(\mathbf{x}_m) \\ &\le \sum_{i<m}w_if(\mathbf{x}_i) + w_mf(\mathbf{x}_m) , \end{aligned} \tag{2}$ where the second step multiplies (1) by $s > 0$ . This proves the inequality.

For the equality clause, let $f$ be strictly convex and every $w_i > 0$ , so that $0 < w_m < 1$ and $0 < s < 1$ . If equality holds in the theorem, both inequalities in (2) are equalities. The second is $s$ times (1), so (1) is an equality, and the inductive hypothesis gives $\mathbf{x}_1 = \dots = \mathbf{x}_{m-1}$ ; then $\mathbf{y}$ equals this common point. The first is the two-point inequality with weights strictly between $0$ and $1$ , so strict convexity forces $\mathbf{y} = \mathbf{x}_m$ . Hence all $m$ points are equal, as claimed.

In the language of §01, the points $(\mathbf{x}_i, f(\mathbf{x}_i))$ lie in the convex set $\operatorname{epi} f$ , and Jensen’s inequality says that their convex combinations stay there. That is Theorem 18.1.3 read inside the epigraph.

18.10.3. Suprema of affine functions

Chapter 17 §06 showed that $s_k(\mathbf{A}) = \sum_{i\le k}\lambda_i(\mathbf{A})$ is the largest of the linear functions $\mathbf{A} \mapsto \operatorname{tr}(\mathbf{Q}^{*}\mathbf{A}\mathbf{Q})$ , deduced its convexity, and ended with a promise: “Chapter 18 studies convex functions in general, and the observation that a pointwise supremum of linear functions is convex is one of its basic facts.” Here is that fact, stated for affine functions, which include the linear ones.

Proposition 18.10.3 (A Supremum of Affine Functions Is Convex)

Let $C \subseteq V$ be non-empty and convex, and let $(a_i)_{i \in I}$ be a non-empty family of affine functions on $V$ . Suppose that for every $\mathbf{x} \in C$ the set $\{a_i(\mathbf{x}) : i \in I\}$ is bounded above, and put $g(\mathbf{x}) = \sup_{i \in I} a_i(\mathbf{x}) \qquad (\mathbf{x} \in C) .$ Then $g \colon C \to \mathbb{R}$ is convex.

Idea. Each $a_i$ meets its own chord inequality with equality, and each lies below $g$ . So at a point between $\mathbf{x}$ and $\mathbf{y}$ , every $a_i$ is at most the chord of $g$ , and therefore so is their supremum.

Proof. The supremum exists for each $\mathbf{x} \in C$ by completeness, fact (A1) of Chapter 16’s introduction. Let $\mathbf{x}, \mathbf{y} \in C$ and $0 \le t \le 1$ . For each $i \in I$ , by Example (First convex functions) (a) and then $a_i \le g$ at $\mathbf{x}$ and at $\mathbf{y}$ , $a_i\bigl(t\mathbf{x} + (1-t)\mathbf{y}\bigr) = ta_i(\mathbf{x}) + (1-t)a_i(\mathbf{y}) \le tg(\mathbf{x}) + (1-t)g(\mathbf{y}) ,$ where the inequality uses $t \ge 0$ and $1 - t \ge 0$ . So the right side is an upper bound for the set $\{a_i(t\mathbf{x} + (1-t)\mathbf{y}) : i \in I\}$ , and it is therefore at least that set’s least upper bound, $g(t\mathbf{x} + (1-t)\mathbf{y})$ . This proves the proposition.

The proof never used that the $a_i$ are affine beyond the fact that each is convex. So the same argument shows that a pointwise supremum of convex functions is convex, whenever it is finite. In particular the maximum of two convex functions is convex. The minimum need not be: $\min(x, -x) = -\lvert x\rvert$ is concave and not convex.

Instances. Many convex functions of this chapter are suprema of linear functions, and this proposition proves their convexity at a stroke.

$\lvert x\rvert = \max(x, -x)$ ; $\left\| \mathbf{x} \right\|_\infty = \max_i\max(x_i, -x_i)$ ; and $\left\| \mathbf{x} \right\|_1 = \max\{\langle \boldsymbol{\upepsilon}, \mathbf{x} \rangle : \boldsymbol{\upepsilon} \in \{\pm1\}^n\}$ , the maximum being attained at the vector of signs of $\mathbf{x}$ .
The support function $h_K(\mathbf{y})$ of Definition 18.4.2 is the supremum over $\mathbf{x} \in K$ of the linear functions $\mathbf{y} \mapsto \langle \mathbf{x}, \mathbf{y} \rangle$ . So it is convex wherever it is finite, and in particular the dual norm of Definition 18.4.4 is convex.
Every norm is the maximum of $\mathbf{x} \mapsto \langle \mathbf{x}, \mathbf{y} \rangle$ over $\left\| \mathbf{y} \right\|_* \le 1$ (Corollary 18.4.9). This describes the norm; it is not a new proof of its convexity, since §04 derived the corollary from the triangle inequality.
The largest eigenvalue: by Lemma 13.5.2, $\lambda_1(\mathbf{A}) = \max_{\left\| \mathbf{x} \right\| = 1}\langle \mathbf{A}\mathbf{x}, \mathbf{x} \rangle$ , and each $\mathbf{A} \mapsto \langle \mathbf{A}\mathbf{x}, \mathbf{x} \rangle$ is linear.
The Ky Fan sums $s_k$ , the case that prompted the promise. They are the subject of the next subsection.

18.10.4. Convex functions of a Hermitian matrix

Let $F = \mathbb{R}$ or $F = \mathbb{C}$ . The Hermitian $n \times n$ matrices over $F$ form a real vector space: if $\mathbf{A}^{*} = \mathbf{A}$ , $\mathbf{B}^{*} = \mathbf{B}$ and $s, t \in \mathbb{R}$ , then $(s\mathbf{A} + t\mathbf{B})^{*} = s\mathbf{A} + t\mathbf{B}$ . They do not form a complex one, since $(i\mathbf{I})^{*} = -i\mathbf{I}$ . This is the space on which Chapter 17 §06 called $s_k$ convex, and it is the setting here. When $F = \mathbb{C}$ it is an instance of the chapter’s convention that a complex space is treated as a real one.

Corollary 18.10.4 (The Top Eigenvalue Sums Are Convex)

Let $1 \le k \le n$ . On the real vector space of Hermitian $n \times n$ matrices over $F$ , the function $s_k(\mathbf{A}) = \lambda_1(\mathbf{A}) + \dots + \lambda_k(\mathbf{A})$ is convex. In particular $\mathbf{A} \mapsto \lambda_1(\mathbf{A})$ is convex, and $\mathbf{A} \mapsto \lambda_n(\mathbf{A})$ is concave.

Idea. Ky Fan’s theorem writes $s_k$ as a maximum of the functions $\mathbf{A} \mapsto \operatorname{tr}(\mathbf{Q}^{*}\mathbf{A}\mathbf{Q})$ , each linear on the real space of Hermitian matrices, so Proposition 18.10.3 applies. For $\lambda_n$ , change the sign of $\mathbf{A}$ .

Proof. By Theorem 17.6.2, $s_k(\mathbf{A}) = \max\{\operatorname{tr}(\mathbf{Q}^{*}\mathbf{A}\mathbf{Q}) : \mathbf{Q} \in M_{n\times k}(F),\ \mathbf{Q}^{*}\mathbf{Q} = \mathbf{I}_k\}$ . Fix such a $\mathbf{Q}$ . The matrix $\mathbf{Q}^{*}\mathbf{A}\mathbf{Q}$ is Hermitian, so its diagonal entries, and hence its trace, are real. By Theorem 0.9.6 (1), $\mathbf{A} \mapsto \operatorname{tr}(\mathbf{Q}^{*}\mathbf{A}\mathbf{Q})$ respects sums and real multiples. So it is a linear functional on the real space of Hermitian matrices, and $s_k$ is the maximum of this family. By Proposition 18.10.3, $s_k$ is convex, and $k = 1$ gives $\lambda_1$ .

For $\lambda_n$ , the eigenvalues of $-\mathbf{A}$ are the negatives of those of $\mathbf{A}$ , so $\lambda_n(\mathbf{A}) = -\lambda_1(-\mathbf{A})$ , as in the proof of Corollary 17.6.6. The map $\mathbf{A} \mapsto \lambda_1(-\mathbf{A})$ is convex, because it is the convex $\lambda_1$ composed with the linear map $\mathbf{A} \mapsto -\mathbf{A}$ , and a convex function composed with a linear map is convex, by substituting into Definition 18.10.1. So $\lambda_n$ is the negative of a convex function, that is, concave.

This is the fact Chapter 17 §06 anticipated, and its promise is now paid. Chapter 17 reached convexity by a different path: Corollary 17.6.5 gives $s_k(\mathbf{A} + \mathbf{B}) \le s_k(\mathbf{A}) + s_k(\mathbf{B})$ , and positive homogeneity $s_k(t\mathbf{A}) = ts_k(\mathbf{A})$ , $t \ge 0$ , turns subadditivity into convexity. Exercise C1 shows that the two paths are the same, and the warning at the end of Chapter 17 §06 still stands: a single $\lambda_k$ with $1 < k < n$ , the difference $s_k - s_{k-1}$ of two convex functions, is neither convex nor concave.

What is not proved here. For a convex $f$ on an interval, $\mathbf{A} \mapsto \operatorname{tr} f(\mathbf{A}) = \sum_i f(\lambda_i(\mathbf{A}))$ is convex on the Hermitian matrices with spectrum in that interval, a statement about sums over the spectrum and far weaker than the operator convexity of Chapter 17 §11. It is proved in Chapter 21, and nothing in this chapter uses it.

18.10.5. A second-derivative test

For a function on an interval, convexity says the slope never decreases. The mean value theorem turns an increasing derivative into a chord inequality.

Lemma 18.10.5 (Increasing Derivative Gives Convexity)

Let $I \subseteq \mathbb{R}$ be an open interval and let $g \colon I \to \mathbb{R}$ be differentiable. If $g'$ is increasing on $I$ , then $g$ is convex; if $g'$ is strictly increasing, then $g$ is strictly convex. In particular, if $g$ is twice differentiable with $g'' \ge 0$ on $I$ , then $g$ is convex, and if $g'' > 0$ on $I$ , then $g$ is strictly convex.

Idea. Split the chord at the intermediate point $z$ into two sub-chords, over $[x, z]$ and over $[z, y]$ . By the mean value theorem, each slope is a value of $g'$ inside its interval, so an increasing $g'$ makes the left slope at most the right one. A graph whose chord slopes increase in this way lies below the long chord.

Proof. Let $x, y \in I$ and $0 < t < 1$ ; the cases $t = 0$ , $t = 1$ and $x = y$ are equalities. Exchanging $x$ with $y$ and $t$ with $1 - t$ if necessary, we may assume $x < y$ . Put $z = tx + (1-t)y$ , so that $x < z < y$ , with $z - x = (1-t)(y - x), \qquad y - z = t(y - x) .$ By the mean value theorem, fact (A6) of Chapter 16’s introduction, applied on $[x, z]$ and on $[z, y]$ , there are $c_1 \in (x, z)$ and $c_2 \in (z, y)$ with $g(z) - g(x) = (1-t)(y-x)\,g'(c_1), \qquad g(y) - g(z) = t(y-x)\,g'(c_2) .$ Since $c_1 < c_2$ and $g'$ is increasing, $g'(c_1) \le g'(c_2)$ . Multiplying by $t(1-t)(y - x) > 0$ , $\begin{aligned} t\bigl(g(z) - g(x)\bigr) &= t(1-t)(y-x)\,g'(c_1) \\ &\le t(1-t)(y-x)\,g'(c_2) = (1-t)\bigl(g(y) - g(z)\bigr) . \end{aligned}$ Rearranged, this is $g(z) \le tg(x) + (1-t)g(y)$ . If $g'$ is strictly increasing, then $g'(c_1) < g'(c_2)$ , and every inequality is strict.

For the last sentence, let $a < b$ in $I$ . Fact (A6) applied to $g'$ gives $g'(b) - g'(a) = g''(c)(b - a)$ for some $c \in (a, b)$ . This is $\ge 0$ when $g'' \ge 0$ , and $> 0$ when $g'' > 0$ . So $g'$ is increasing, or strictly increasing, and the first part applies.

Derivatives of polynomials, here and below, come from Chapter 10 §09: a polynomial is a power series with finitely many non-zero coefficients, so it converges for every real argument and that section’s fact (A2) differentiates it term by term, while its fact (A3), the linearity of differentiation, handles sums and constant multiples; a partial derivative is such a derivative with the other variables fixed. For instance, $g(x) = x^4$ has $g'(x) = 4x^3$ , which is strictly increasing (the Quick check after Proposition 18.10.1), so $x^4$ is strictly convex on $\mathbb{R}$ . Likewise $x^3$ , with $g'' = 6x \ge 0$ on $(0, \infty)$ , is convex there, which is the claim made after the non-example.

In several variables the second derivative is the Hessian $\mathbf{H}_f(\mathbf{a})$ of Definition 14.6.2, and “ $g'' \ge 0$ ” becomes “positive semidefinite”. Chapter 14 §06 read the Hessian at a single critical point, where its definiteness decides a local extremum (Theorem 14.6.4). Here the Hessian is asked to be positive semidefinite at every point, and what it decides is global. Restricting $f$ to lines would need a chain rule the book has not imported, so the proof below uses only Chapter 14 §06’s (A1), that $\mathbf{H}_f(\mathbf{a})$ is symmetric, and its (A2), Taylor’s theorem with a remainder $r(\mathbf{h})$ satisfying $r(\mathbf{h})/\left\| \mathbf{h} \right\|^2 \to 0$ . It works with second differences, which (A2) controls directly.

Theorem 18.10.6 (Convexity from the Hessian)

Let $U \subseteq \mathbb{R}^n$ be a non-empty open convex set, and let $f \colon U \to \mathbb{R}$ be twice continuously differentiable.

(a) $f$ is convex on $U$ if and only if $\mathbf{H}_f(\mathbf{a}) \succeq 0$ for every $\mathbf{a} \in U$ .
(b) If $\mathbf{H}_f(\mathbf{a}) \succ 0$ for every $\mathbf{a} \in U$ , then $f$ is strictly convex on $U$ .

Idea. Taylor’s theorem at $\mathbf{z}$ , applied at $\mathbf{z} + s\mathbf{v}$ and at $\mathbf{z} - s\mathbf{v}$ and added, kills the gradient term: $\frac{f(\mathbf{z} + s\mathbf{v}) + f(\mathbf{z} - s\mathbf{v}) - 2f(\mathbf{z})}{s^2} \ \longrightarrow\ \mathbf{v}^{\top}\mathbf{H}_f(\mathbf{z})\mathbf{v} .$ For $(\Rightarrow)$ , convexity makes the left side $\ge 0$ , so the limit is too. For the other direction, restrict $f$ to a segment and subtract the chord. If the difference were positive somewhere, it would have an interior maximum, and at a maximum every second difference is $\le 0$ . That contradicts a strictly positive limit. So the argument handles $\mathbf{H}_f \succ 0$ first, and reaches $\mathbf{H}_f \succeq 0$ by adding $\varepsilon\left\| \mathbf{x} \right\|^2$ and letting $\varepsilon \to 0$ .

Proof. Write $\mathbf{H}(\mathbf{z}) = \mathbf{H}_f(\mathbf{z})$ . For $\mathbf{z} \in U$ , $\mathbf{v} \in \mathbb{R}^n$ and real $s \ne 0$ small enough that $\mathbf{z} \pm s\mathbf{v} \in U$ , put $\Delta(\mathbf{z}, \mathbf{v}, s) = f(\mathbf{z} + s\mathbf{v}) + f(\mathbf{z} - s\mathbf{v}) - 2f(\mathbf{z}) .$

Step 1: the second difference. We claim $\Delta(\mathbf{z}, \mathbf{v}, s)/s^2 \to \mathbf{v}^{\top}\mathbf{H}(\mathbf{z})\mathbf{v}$ as $s \to 0$ . If $\mathbf{v} = \mathbf{0}$ both sides are $0$ . Otherwise Chapter 14 §06’s (A2) at $\mathbf{z}$ , with $\mathbf{h} = s\mathbf{v}$ and with $\mathbf{h} = -s\mathbf{v}$ , gives $f(\mathbf{z} \pm s\mathbf{v}) = f(\mathbf{z}) \pm s\,\nabla f(\mathbf{z})\cdot\mathbf{v} + \tfrac12 s^2\,\mathbf{v}^{\top}\mathbf{H}(\mathbf{z})\mathbf{v} + r(\pm s\mathbf{v}) .$ Adding the two and subtracting $2f(\mathbf{z})$ , $\begin{aligned} \frac{\Delta(\mathbf{z}, \mathbf{v}, s)}{s^2} &= \mathbf{v}^{\top}\mathbf{H}(\mathbf{z})\mathbf{v} \\ &\qquad + \left\| \mathbf{v} \right\|^2\Bigl(\frac{r(s\mathbf{v})}{\left\| s\mathbf{v} \right\|^2} + \frac{r(-s\mathbf{v})}{\left\| s\mathbf{v} \right\|^2}\Bigr) , \end{aligned}$ and the bracket tends to $0$ because $\left\| \pm s\mathbf{v} \right\| \to 0$ . The same expansion shows that $f$ is continuous: $f(\mathbf{z} + \mathbf{h}) - f(\mathbf{z}) = \nabla f(\mathbf{z})\cdot\mathbf{h} + \tfrac12\mathbf{h}^{\top}\mathbf{H}(\mathbf{z})\mathbf{h} + \left\| \mathbf{h} \right\|^2\cdot r(\mathbf{h})/\left\| \mathbf{h} \right\|^2$ , and each term tends to $0$ as $\mathbf{h} \to \mathbf{0}$ .

Step 2: (a), $(\Rightarrow)$ . Let $f$ be convex, $\mathbf{a} \in U$ and $\mathbf{v} \in \mathbb{R}^n$ . For small $s \ne 0$ , $\mathbf{a} = \tfrac12(\mathbf{a} + s\mathbf{v}) + \tfrac12(\mathbf{a} - s\mathbf{v})$ , so $f(\mathbf{a}) \le \tfrac12 f(\mathbf{a} + s\mathbf{v}) + \tfrac12 f(\mathbf{a} - s\mathbf{v})$ , that is, $\Delta(\mathbf{a}, \mathbf{v}, s) \ge 0$ . Dividing by $s^2 > 0$ and letting $s \to 0$ , Step 1 gives $\mathbf{v}^{\top}\mathbf{H}(\mathbf{a})\mathbf{v} \ge 0$ , since a non-strict inequality survives a limit. The matrix $\mathbf{H}(\mathbf{a})$ is symmetric by Chapter 14 §06’s (A1), so $\mathbf{H}(\mathbf{a}) \succeq 0$ by Definition 13.1.1.

Step 3: a maximum principle. Let $\mathbf{x} \ne \mathbf{y}$ in $U$ , put $\mathbf{v} = \mathbf{y} - \mathbf{x}$ , and let $\phi \colon U \to \mathbb{R}$ be continuous with the following property: for every point $\mathbf{z} = \mathbf{x} + t\mathbf{v}$ with $0 < t < 1$ , the limit $L(\mathbf{z}) = \lim_{s\to0}\bigl(\phi(\mathbf{z} + s\mathbf{v}) + \phi(\mathbf{z} - s\mathbf{v}) - 2\phi(\mathbf{z})\bigr)/s^2$ exists and is strictly positive. We claim $\phi\bigl(\mathbf{x} + t\mathbf{v}\bigr) < (1-t)\phi(\mathbf{x}) + t\phi(\mathbf{y}) \qquad (0 < t < 1) .$ Define $h(t) = \phi(\mathbf{x} + t\mathbf{v}) - (1-t)\phi(\mathbf{x}) - t\phi(\mathbf{y})$ on $[0, 1]$ . Every point of the segment lies in $U$ , since $U$ is convex. So $h$ is continuous, and $h(0) = h(1) = 0$ . The subtracted part is affine in $t$ , so its second differences vanish, and $h(t+s) + h(t-s) - 2h(t) = \phi(\mathbf{z} + s\mathbf{v}) + \phi(\mathbf{z} - s\mathbf{v}) - 2\phi(\mathbf{z})$ with $\mathbf{z} = \mathbf{x} + t\mathbf{v}$ .

Suppose $h(t_1) \ge 0$ for some $t_1 \in (0, 1)$ . The interval $[0, 1]$ is closed and bounded, hence compact by fact (A3) of Chapter 16’s introduction, so by the extreme value theorem, fact (A4), $h$ attains a maximum value $M$ at some point. Then $M \ge h(t_1) \ge 0$ . If the maximum is attained only at $0$ or $1$ , then $M = 0 \le h(t_1)$ , so $t_1$ attains it too. Either way, $M = h(t^{*})$ for some $t^{*} \in (0, 1)$ . For $0 < s < \min(t^{*}, 1 - t^{*})$ , both $h(t^{*} \pm s) \le h(t^{*})$ , so the second difference of $h$ at $t^{*}$ is $\le 0$ , and so is its limit $L(\mathbf{x} + t^{*}\mathbf{v})$ . This contradicts $L > 0$ . Hence $h < 0$ on $(0, 1)$ , which is the claim.

Step 4: (b). Let $\mathbf{H}(\mathbf{z}) \succ 0$ for every $\mathbf{z} \in U$ . By Step 1, $\phi = f$ has $L(\mathbf{z}) = \mathbf{v}^{\top}\mathbf{H}(\mathbf{z})\mathbf{v} > 0$ whenever $\mathbf{v} \ne \mathbf{0}$ , and it is continuous. So Step 3 gives $f((1-t)\mathbf{x} + t\mathbf{y}) < (1-t)f(\mathbf{x}) + tf(\mathbf{y})$ for all $\mathbf{x} \ne \mathbf{y}$ in $U$ and $0 < t < 1$ . Renaming $t$ as $1 - t$ , this is strict convexity.

Step 5: (a), $(\Leftarrow)$ . Let $\mathbf{H}(\mathbf{z}) \succeq 0$ for every $\mathbf{z} \in U$ . Let $\mathbf{x} \ne \mathbf{y}$ in $U$ , $\mathbf{v} = \mathbf{y} - \mathbf{x}$ , $0 < t < 1$ , and $\varepsilon > 0$ . Put $\phi(\mathbf{z}) = f(\mathbf{z}) + \varepsilon\left\| \mathbf{z} \right\|^2$ , which is continuous. Expanding the norms, $\left\| \mathbf{z} + s\mathbf{v} \right\|^2 + \left\| \mathbf{z} - s\mathbf{v} \right\|^2 - 2\left\| \mathbf{z} \right\|^2 = 2s^2\left\| \mathbf{v} \right\|^2 ,$ so by Step 1 the limit for $\phi$ is $L(\mathbf{z}) = \mathbf{v}^{\top}\mathbf{H}(\mathbf{z})\mathbf{v} + 2\varepsilon\left\| \mathbf{v} \right\|^2 \ge 2\varepsilon\left\| \mathbf{v} \right\|^2 > 0$ . Step 3 applies. With $\mathbf{w} = (1-t)\mathbf{x} + t\mathbf{y}$ , it gives $\begin{aligned} f(\mathbf{w}) + \varepsilon\left\| \mathbf{w} \right\|^2 &< (1-t)\bigl(f(\mathbf{x}) + \varepsilon\left\| \mathbf{x} \right\|^2\bigr) \\ &\qquad + t\bigl(f(\mathbf{y}) + \varepsilon\left\| \mathbf{y} \right\|^2\bigr) . \end{aligned}$ Let $\varepsilon \to 0$ through $\varepsilon = 1/k$ . The inequality survives as a non-strict one, and gives $f(\mathbf{w}) \le (1-t)f(\mathbf{x}) + tf(\mathbf{y})$ . The cases $\mathbf{x} = \mathbf{y}$ , $t = 0$ and $t = 1$ are equalities. So $f$ is convex. This proves the theorem.

For $n = 1$ , part (a) says that a twice continuously differentiable $g$ on an open interval is convex exactly when $g'' \ge 0$ , and its “if” half is Lemma 18.10.5 again.

Quick check. The function $f(x) = x^4$ is strictly convex on $\mathbb{R}$ . Is its Hessian, the $1 \times 1$ matrix $(f''(x))$ , positive definite at every point? What does this say about part (b)?

Solution. No. $f''(x) = 12x^2$ vanishes at $x = 0$ , so the $1 \times 1$ matrix $(0)$ is positive semidefinite but not positive definite. Yet $f$ is strictly convex, as shown after Lemma 18.10.5. So the converse of part (b) fails: strict convexity does not force a positive definite Hessian.

Convexity is tested segment by segment, so $f$ is convex exactly when its restriction $t \mapsto f(\mathbf{x} + t\mathbf{v})$ to every line is convex. The phrase every line matters.

Warning. Convex along every line through one point is not enough. Let $f(x, y) = x^2y^2$ on $\mathbb{R}^2$ . On each line through the origin, $f(t\mathbf{v}) = t^4\,v_1^2v_2^2$ , a non-negative multiple of the convex $t^4$ , so each such restriction is convex. But $f$ is not convex. On the segment from $(1, 0)$ to $(0, 1)$ , a line that misses the origin, $f(1 - t, t) = t^2(1-t)^2$ is $0$ at both ends and $\tfrac1{16}$ at the midpoint. So the value at the midpoint exceeds the average $0$ of the end values.

The Hessian test sees the same failure without guessing the segment. Here $\mathbf{H}_f(x, y) = \begin{pmatrix} 2y^2 & 4xy \\ 4xy & 2x^2 \end{pmatrix}, \qquad \det\mathbf{H}_f(x, y) = -12x^2y^2 ,$ so at $(1, 1)$ the determinant is $-12 < 0$ . The two eigenvalues of this symmetric matrix have product $-12$ , so one is negative, and $\mathbf{H}_f(1, 1) \not\succeq 0$ . Part (a) confirms that $f$ is not convex.

18.10.6. Continuity

The warning about $\lvert x \rvert$ shows that convexity does not buy differentiability. It does buy continuity on an open set, and in finite dimension the proof is short: a bound from above near a point is enough, and Jensen’s inequality supplies one.

Theorem 18.10.7 (Convex Functions Are Continuous)

Let $U \subseteq \mathbb{R}^n$ be a non-empty open convex set and let $f \colon U \to \mathbb{R}$ be convex. Then $f$ is continuous on $U$ . More precisely, for every $\mathbf{a} \in U$ there are $\delta > 0$ and $L \ge 0$ with $\lvert f(\mathbf{a} + \mathbf{h}) - f(\mathbf{a})\rvert \le L\left\| \mathbf{h} \right\| \qquad \text{whenever } \left\| \mathbf{h} \right\| \le \delta .$

Idea. ① Bound $f$ above on a small ball around $\mathbf{a}$ . The ball sits inside the “diamond” spanned by the $2n$ points $\mathbf{a} \pm \rho\mathbf{e}_i$ , and Jensen bounds $f$ on the diamond by its largest value at those points. ② Turn an upper bound into a two-sided linear bound. Walk from $\mathbf{a}$ toward $\mathbf{a} + \mathbf{h}$ and on to the edge of the ball: convexity makes the rise over the short step at most a fraction of the rise over the whole way. Then walk the other way for the lower bound.

Proof. Fix $\mathbf{a} \in U$ . Since $U$ is open, Proposition 18.1.6 (a) gives $r > 0$ such that every point within distance $r$ of $\mathbf{a}$ lies in $U$ . Put $\rho = r/2$ . The $2n + 1$ points $\mathbf{a}$ and $\mathbf{a} \pm \rho\mathbf{e}_i$ lie in $U$ , so let $M$ be the largest value of $f$ at them.

Step 1: an upper bound. Let $\mathbf{h} = \sum_i h_i\mathbf{e}_i$ with $\left\| \mathbf{h} \right\|_1 \le \rho$ , and let $\sigma_i = 1$ if $h_i \ge 0$ and $\sigma_i = -1$ otherwise, so that $\lvert h_i\rvert\sigma_i = h_i$ . Then $\mathbf{a} + \mathbf{h} = \sum_{i=1}^{n}\frac{\lvert h_i\rvert}{\rho}\,(\mathbf{a} + \rho\sigma_i\mathbf{e}_i) + \Bigl(1 - \frac{\left\| \mathbf{h} \right\|_1}{\rho}\Bigr)\mathbf{a} ,$ a convex combination: the weights are non-negative and add up to $1$ . By Theorem 18.10.2, $f(\mathbf{a} + \mathbf{h}) \le M$ . Put $\delta = \rho/\sqrt n$ . If $\left\| \mathbf{h} \right\| \le \delta$ , then $\left\| \mathbf{h} \right\|_1 \le \sqrt n\left\| \mathbf{h} \right\| \le \rho$ by Proposition 16.1.2, so $f(\mathbf{a} + \mathbf{h}) \le M$ .

Step 2: the linear bound. Put $L = (M - f(\mathbf{a}))/\delta$ , which is $\ge 0$ because $\mathbf{a}$ is one of the points defining $M$ . Let $0 < \left\| \mathbf{h} \right\| \le \delta$ ; for $\mathbf{h} = \mathbf{0}$ there is nothing to prove. Put $s = \left\| \mathbf{h} \right\|/\delta \in (0, 1]$ and $\mathbf{u} = \mathbf{h}/s$ , so that $\left\| \mathbf{u} \right\| = \delta$ and $s\mathbf{u} = \mathbf{h}$ . First, $\mathbf{a} + \mathbf{h} = (1 - s)\mathbf{a} + s(\mathbf{a} + \mathbf{u}) ,$ so convexity gives $f(\mathbf{a} + \mathbf{h}) \le (1-s)f(\mathbf{a}) + sf(\mathbf{a} + \mathbf{u})$ , that is, $f(\mathbf{a} + \mathbf{h}) - f(\mathbf{a}) \le s\bigl(f(\mathbf{a} + \mathbf{u}) - f(\mathbf{a})\bigr) \le s\bigl(M - f(\mathbf{a})\bigr) ,$ using Step 1 at $\mathbf{u}$ . Second, $\mathbf{a} = \frac{1}{1+s}(\mathbf{a} + \mathbf{h}) + \frac{s}{1+s}(\mathbf{a} - \mathbf{u}) ,$ as one checks by multiplying out and using $s\mathbf{u} = \mathbf{h}$ . Here $\mathbf{a} - \mathbf{u}$ lies in $U$ , and convexity gives $(1+s)f(\mathbf{a}) \le f(\mathbf{a} + \mathbf{h}) + sf(\mathbf{a} - \mathbf{u})$ , that is, $f(\mathbf{a}) - f(\mathbf{a} + \mathbf{h}) \le s\bigl(f(\mathbf{a} - \mathbf{u}) - f(\mathbf{a})\bigr) \le s\bigl(M - f(\mathbf{a})\bigr) ,$ using Step 1 at $-\mathbf{u}$ . Together, $\lvert f(\mathbf{a} + \mathbf{h}) - f(\mathbf{a})\rvert \le s(M - f(\mathbf{a})) = L\left\| \mathbf{h} \right\|$ .

Step 3: continuity. If $\mathbf{x}_k \to \mathbf{a}$ , then $\left\| \mathbf{x}_k - \mathbf{a} \right\| \le \delta$ for all large $k$ , and for those $k$ Step 2 gives $\lvert f(\mathbf{x}_k) - f(\mathbf{a})\rvert \le L\left\| \mathbf{x}_k - \mathbf{a} \right\| \to 0$ . So $f$ is continuous at $\mathbf{a}$ , in the sequential sense of Chapter 16’s introduction. As $\mathbf{a}$ was arbitrary, this proves the theorem.

By Theorem 16.2.2 the choice of the Euclidean norm is immaterial: every norm on $\mathbb{R}^n$ gives the same continuous functions. Both hypotheses of the theorem are needed.

Warning. The domain must be open. On the closed interval $[0, 1]$ , let $f = 0$ on $[0, 1)$ and $f(1) = 1$ . It is convex: the right side $tf(x) + (1-t)f(y)$ is never negative, and the left side is $0$ unless $tx + (1-t)y = 1$ , which for $0 < t < 1$ forces $x = y = 1$ , where both sides equal $1$ . But $f(1 - 1/k) = 0 \not\to 1 = f(1)$ . A convex function can jump at a boundary point of its domain.

Remark. Finite dimension is needed too. On the polynomials in $C[0,1]$ , with the sup norm $\left\| p \right\|_\infty = \max_{t\in[0,1]}\lvert p(t)\rvert$ of Chapter 16 §01 restricted to them, the functional $\varphi(p) = p'(1)$ is linear, hence convex, on the whole space. The polynomials $p_k = x^{k^2}/k$ have $\left\| p_k \right\|_\infty = 1/k \to 0$ and $\varphi(p_k) = k \to \infty$ , so $\varphi$ is not continuous at $0$ . Step 1 is what fails: there is no finite set of points whose convex hull contains a ball.

The basic theory is now in place. A convex function is one with a convex epigraph; Jensen’s inequality extends its defining inequality to every finite average; every supremum of affine functions is one, which accounts for the Ky Fan sums; the Hessian tests for it; and on an open set it is continuous. What it has not yet done is prove an inequality the book did not already know. §11 does that: with a logarithm constructed from the exponential, Jensen’s inequality for $-\log$ gives the weighted arithmetic–geometric mean inequality, and from it come Young’s and Hölder’s inequalities, the triangle inequality for every $p$ -norm, and the dual norms that §04 left open.

18.10.7. Exercises

A. Check your understanding

Exercise (A1)

(a) Define “ $f$ is convex on $C$ ”, and explain why $C$ is required to be convex.
(b) Decide whether the following is correct, and justify your answer: if $f$ and $g$ are convex on $C$ , then so are $f + g$ and $\max(f, g)$ .
(c) Decide whether the following is correct, and justify your answer: if $f$ and $g$ are convex on $\mathbb{R}$ , then so is their product $fg$ .
(d) Decide whether the following is correct, and justify your answer: a convex function on $\mathbb{R}$ is differentiable.
(e) Decide whether the following is correct, and justify your answer: if $f \colon \mathbb{R}^2 \to \mathbb{R}$ is convex along every line through the origin, then $f$ is convex.
(f) Name the facts of analysis that the proof of Theorem 18.10.6 uses.

Solution.

(a) Let $C$ be a non-empty convex subset of a real vector space. Then $f \colon C \to \mathbb{R}$ is convex if $f(t\mathbf{x} + (1-t)\mathbf{y}) \le tf(\mathbf{x}) + (1-t)f(\mathbf{y})$ for all $\mathbf{x}, \mathbf{y} \in C$ and all $t \in [0, 1]$ (Definition 18.10.1). The left side evaluates $f$ at $t\mathbf{x} + (1-t)\mathbf{y}$ , and this point is in the domain for every choice exactly when $C$ is convex.
(b) Correct. Adding the inequalities for $f$ and for $g$ gives the inequality for $f + g$ . For the maximum, the remark after Proposition 18.10.3 applies: its proof works for any family of convex functions, and here the family is $\{f, g\}$ .
(c) Incorrect. $f(x) = x$ is affine and $g(x) = x^2$ is convex (Example (First convex functions)), but $fg = x^3$ is not convex on $\mathbb{R}$ : at $-2$ , $0$ and their midpoint $-1$ the non-example after Example (First convex functions) gives $-1 > -4$ .
(d) Incorrect. $\lvert x \rvert$ is convex and not differentiable at $0$ , as the first warning of the section shows.
(e) Incorrect. $f(x, y) = x^2y^2$ is convex along every line through the origin but not convex, since $f(\tfrac12, \tfrac12) = \tfrac1{16} > 0 = \tfrac12 f(1, 0) + \tfrac12 f(0, 1)$ .
(f) Chapter 14 §06’s assumptions (A1), the symmetry of the Hessian, and (A2), Taylor’s theorem with a second-order remainder; facts (A3) and (A4) of Chapter 16’s introduction, compactness of $[0, 1]$ and the extreme value theorem, in the maximum principle; and the algebra of limits, in the form “a non-strict inequality survives a limit”.

B. Practice

Exercise (B1: Which are convex?)

Determine which of the following functions are convex on the given domain. Justify your answer.

(a) $f(x, y) = 2x^2 - 2xy + y^2$ on $\mathbb{R}^2$ .
(b) $f(x, y) = x^2 + 4xy + y^2$ on $\mathbb{R}^2$ .
(c) $f(x) = \max(2x + 1,\ -x,\ 3)$ on $\mathbb{R}$ .
(d) $g(x) = 1/x$ on $(0, \infty)$ .
(e) $g(x) = 1/x$ on $\{x \in \mathbb{R} : x \ne 0\}$ .

Solution.

(a) Convex, indeed strictly convex. $f$ is a polynomial, so twice continuously differentiable, with constant Hessian $\mathbf{H} = \begin{psmallmatrix} 4 & -2 \\ -2 & 2 \end{psmallmatrix}$ , which is symmetric. For $\mathbf{v} = (v_1, v_2)$ , $\mathbf{v}^{\top}\mathbf{H}\mathbf{v} = 4v_1^2 - 4v_1v_2 + 2v_2^2 = 2\bigl(v_1^2 + (v_1 - v_2)^2\bigr) ,$ which is positive unless $v_1 = 0$ and $v_1 = v_2$ , that is, unless $\mathbf{v} = \mathbf{0}$ . So $\mathbf{H} \succ 0$ at every point, and Theorem 18.10.6 (b) applies.
(b) Not convex. Take $\mathbf{x} = (1, -1)$ and $\mathbf{y} = (-1, 1)$ , with midpoint $\mathbf{0}$ . Then $f(\mathbf{x}) = 1 - 4 + 1 = -2 = f(\mathbf{y})$ , while $f(\mathbf{0}) = 0 > \tfrac12(-2) + \tfrac12(-2) = -2$ . The inequality of Definition 18.10.1 fails with $t = \tfrac12$ .
(c) Convex. The three functions $2x + 1$ , $-x$ and the constant $3$ are affine, and $f$ is their maximum, so Proposition 18.10.3 applies.
(d) Strictly convex. For $x > 0$ and small $h \ne 0$ , $\frac{1}{h}\Bigl(\frac{1}{x+h} - \frac1x\Bigr) = -\frac{1}{x(x+h)} \ \longrightarrow\ -\frac{1}{x^2} ,$ so $g'(x) = -1/x^2$ . If $0 < a < b$ then $1/a^2 > 1/b^2$ , so $-1/a^2 < -1/b^2$ : $g'$ is strictly increasing on $(0, \infty)$ , and Lemma 18.10.5 gives strict convexity.
(e) The question has no answer: Definition 18.10.1 requires a convex domain, and this one is not. It contains $-1$ and $1$ but not their midpoint $0$ , so the defining inequality is undefined for $x = -1$ , $y = 1$ , $t = \tfrac12$ .

C. Going deeper

Exercise (C1: Subadditive and homogeneous)

Let $g \colon V \to \mathbb{R}$ be positively homogeneous: $g(t\mathbf{x}) = tg(\mathbf{x})$ for every $\mathbf{x} \in V$ and every real $t \ge 0$ .

(a) Prove that $g$ is convex if and only if $g(\mathbf{x} + \mathbf{y}) \le g(\mathbf{x}) + g(\mathbf{y})$ for all $\mathbf{x}, \mathbf{y} \in V$ .
(b) Deduce that every norm on $\mathbb{R}^n$ is convex, and that Corollary 17.6.5 and Corollary 18.10.4 are equivalent statements about $s_k$ .

Solution.

(a) $(\Rightarrow)$ Let $g$ be convex. By homogeneity with $t = 2$ and then convexity with $t = \tfrac12$ , $g(\mathbf{x} + \mathbf{y}) = 2g\bigl(\tfrac12\mathbf{x} + \tfrac12\mathbf{y}\bigr) \le 2\bigl(\tfrac12g(\mathbf{x}) + \tfrac12g(\mathbf{y})\bigr) = g(\mathbf{x}) + g(\mathbf{y}) .$ $(\Leftarrow)$ Let $g$ be subadditive, and let $0 \le t \le 1$ . By subadditivity and then homogeneity with the non-negative numbers $t$ and $1 - t$ , $g\bigl(t\mathbf{x} + (1-t)\mathbf{y}\bigr) \le g(t\mathbf{x}) + g\bigl((1-t)\mathbf{y}\bigr) = tg(\mathbf{x}) + (1-t)g(\mathbf{y}) .$
(b) A norm is positively homogeneous by (N2) of Definition 16.1.1, since $\lvert t \rvert = t$ for $t \ge 0$ , and subadditive by (N3); so it is convex by (a). This is a second proof of Example (First convex functions) (b). The function $s_k$ is positively homogeneous on the Hermitian matrices, since multiplying by $t \ge 0$ multiplies each eigenvalue by $t$ and keeps their order. So by (a), subadditivity of $s_k$ , which is Corollary 17.6.5, holds exactly when $s_k$ is convex, which is Corollary 18.10.4.

Exercise (C2: Tangent lines)

Let $I \subseteq \mathbb{R}$ be an open interval and let $g \colon I \to \mathbb{R}$ be differentiable and convex.

(a) Prove that $g(y) \ge g(x) + g'(x)(y - x)$ for all $x, y \in I$ .
(b) Deduce that $g(y) = \max_{x \in I}\bigl(g(x) + g'(x)(y - x)\bigr)$ for every $y \in I$ : a differentiable convex function is the maximum of its tangent lines.

Hint: in (a), apply the definition to the points $x$ and $y$ with weight $s$ on $y$ , and let $s \to 0$ .

Solution.

(a) If $y = x$ both sides are equal. Let $y \ne x$ and $0 < s \le 1$ . Convexity with weight $s$ on $y$ gives $g(x + s(y - x)) \le (1 - s)g(x) + sg(y)$ , that is, $(y - x)\cdot\frac{g\bigl(x + s(y - x)\bigr) - g(x)}{s(y - x)} \ \le\ g(y) - g(x) .$ The fraction is a difference quotient of $g$ at $x$ with step $s(y - x) \ne 0$ . Take $s = 1/k$ ; the step tends to $0$ , so the fraction tends to $g'(x)$ . A non-strict inequality survives the limit, so $(y - x)g'(x) \le g(y) - g(x)$ , as claimed.
(b) For fixed $y$ , each $\ell_x(y) = g(x) + g'(x)(y - x)$ is at most $g(y)$ by (a), and $\ell_y(y) = g(y)$ . So the maximum over $x$ exists, is attained at $x = y$ , and equals $g(y)$ . Each $\ell_x$ is an affine function of $y$ , so this is the converse of Proposition 18.10.3, for differentiable functions.

Exercise (C3: Where a convex function is largest)

(a) Let $f \colon \mathbb{R}^n \to \mathbb{R}$ be convex, and let $P$ be the convex hull $\operatorname{conv}\{\mathbf{x}_1, \dots, \mathbf{x}_m\}$ . Prove that $\max_{\mathbf{x} \in P}f(\mathbf{x}) = \max_i f(\mathbf{x}_i)$ .
(b) Let $f(x, y) = x^2 - xy + y^2$ and let $P$ be the triangle $\operatorname{conv}\{(2, 0), (0, 2), (-2, -2)\}$ . Find the maximum and the minimum of $f$ on $P$ , and say where each is attained.

Solution.

(a) Each $\mathbf{x}_i$ lies in $P$ , so the maximum over $P$ , if it exists, is at least $\max_if(\mathbf{x}_i)$ . Conversely, let $\mathbf{x} \in P$ . By Theorem 18.1.3, $\mathbf{x} = \sum_iw_i\mathbf{x}_i$ for some weights $w_i \ge 0$ with sum $1$ , and Theorem 18.10.2 gives $f(\mathbf{x}) \le \sum_iw_if(\mathbf{x}_i) \le \max_if(\mathbf{x}_i)$ . So $\max_if(\mathbf{x}_i)$ is an upper bound for $f$ on $P$ that is attained, hence the maximum. Compare Corollary 18.8.6, which says the same for a linear function on any compact convex set, with extreme points in place of the $\mathbf{x}_i$ .
(b) The Hessian is the constant symmetric matrix $\begin{psmallmatrix} 2 & -1 \\ -1 & 2 \end{psmallmatrix}$ , and $2v_1^2 - 2v_1v_2 + 2v_2^2 = v_1^2 + v_2^2 + (v_1 - v_2)^2 \ge 0$ , so it is positive semidefinite and $f$ is convex by Theorem 18.10.6 (a). By (a) the maximum is the largest vertex value: $f(2, 0) = 4$ , $f(0, 2) = 4$ and $f(-2, -2) = 4 - 4 + 4 = 4$ . So the maximum is $4$ , attained at all three vertices. For the minimum, $f(x, y) = \tfrac12\bigl(x^2 + y^2 + (x - y)^2\bigr) \ge 0$ , with equality only at $(0, 0)$ . And $(0, 0) = \tfrac13(2, 0) + \tfrac13(0, 2) + \tfrac13(-2, -2)$ lies in $P$ . So the minimum is $0$ , attained only at the interior point $(0, 0)$ . The maximum of a convex function sits at vertices; its minimum need not.