Convexity

Three chapters in a row have met convexity and moved on. Chapter 16 §01 drew the unit balls of three norms and remarked that each is convex, because the triangle inequality forces $\left\| t\mathbf{u} + (1-t)\mathbf{v} \right\| \le 1$ whenever $\left\| \mathbf{u} \right\|, \left\| \mathbf{v} \right\| \le 1$ (Definition 16.1.2). Chapter 13 §01 set as an exercise that the positive semidefinite matrices are closed under sums and non-negative multiples (Exercise (C2: The cone of positive matrices)). Chapter 17 §06 proved that the sum of the $k$ largest eigenvalues is subadditive, and so a convex function of the matrix (Corollary 17.6.5), and said that this was only to be expected of a maximum of linear functions. And Chapter 17 §08 showed, again in an exercise, that the possible diagonals of the Hermitian matrices with a given spectrum contain the segment between any two of their points (Exercise (C3: The possible diagonals form a convex set)). Each time, convexity was checked on the spot and not studied. One debt is older still: Chapter 16’s plan listed dual norms, and Chapter 16 never defined one.

This chapter studies convexity for its own sake. A set is convex when it contains the segment between any two of its points, and the theory built on that single condition has two faces. One face is combinatorial. Every point of a convex hull in dimension $n$ is an average of at most $n + 1$ of the original points, and from that count follow the theorems of Radon and Helly on how convex sets intersect. The other face is geometric, and it carries most of the weight. A point outside a closed convex set can be separated from it by a hyperplane, and the hyperplane comes from the nearest point of the set, generalizing the orthogonal projection of Chapter 11. From separation come the rest: a convex set described by the half-spaces that contain it, the dual norm as the support function of the unit ball, Farkas’s lemma and the duality of linear programming, the minimax theorem for matrix games, and the fact that a compact convex set is the hull of its extreme points. The chapter ends with convex functions, which is where the Ky Fan observation of Chapter 17 belongs.

The field is $\mathbb{R}$ throughout. Convexity asks for weights $t$ with $0 \le t \le 1$ , and “between $0$ and $1$ ” needs an order on the scalars, which $\mathbb{C}$ does not have. A complex space is treated as a real one when it is needed, by allowing only real scalars: the Hermitian $n \times n$ matrices, for instance, form a real vector space and not a complex one, and that is how positive semidefinite matrices and eigenvalue functions enter. Spaces are finite-dimensional, and each section says whether a result needs only the vector space, a norm, or an inner product. Most of the chapter works in $\mathbb{R}^n$ with the standard inner product.

The analysis this chapter imports

The list is Chapter 16’s, facts (A1)–(A6) of that chapter’s introduction, cited by the same name at the point of use: “by the extreme value theorem, fact (A4) of Chapter 16’s introduction”. This chapter needs chiefly two of them. (A3), the compactness of closed bounded sets, and (A4), the extreme value theorem, are what make a nearest point, a maximum over a hull, or an extreme point exist rather than merely be approached. §02 uses (A3) to prove that the hull of a compact set is compact, and the separation and extreme-point theorems of §§03 and 08 rest on both. (A1), completeness, gives the suprema that define gauges and support functions. For the second-derivative test of convexity in §10, the one-variable case uses (A6), the mean value theorem, and the several-variable case uses the symmetry and Taylor assumptions that Chapter 14 §06 recorded for its own second-derivative test. §11 builds the logarithm from the exponential of Chapter 10 §09 (that section’s facts (A1)–(A3)) and needs (A5), the intermediate value theorem, to show every positive number has one.

The words closed and open are defined in §01, in the sequential form in which Chapter 16’s introduction defines continuity, and a closedness argument uses nothing but that definition and the elementary algebra of limits. A section that needs any analytic fact outside Chapter 16’s list says so where it uses it.

What you need

Chapter 0 §06 and §09 — the triangle inequality for complex numbers, which §11 uses twice, and the trace, which §10 uses once: Theorem 0.6.4, Theorem 0.9.6.
Chapter 1 — independence and dimension, used to count points: Definition 1.4.1, Theorem 1.6.3, Theorem 1.3.1, Theorem 1.6.5, and the dimension formula Theorem 1.7.3. Zorn’s lemma (Theorem 1.8.1) is mentioned once, to mark where the infinite-dimensional Hahn–Banach theorem would begin.
Chapter 2 — Rank–Nullity: Theorem 2.3.1.
Chapter 4 — cosets, which are the affine subspaces of this chapter: Definition 4.4.2, Lemma 4.4.3.
Chapter 3 §04 and §05 — the Invertible Matrix Theorem and the rank facts §09 counts the vertices of a polyhedron with: Theorem 3.4.4, Theorem 3.5.7, Theorem 3.5.5.
Chapter 5 — linear functionals and hyperplanes, the raw material of every separation argument: Definition 5.1.1, Theorem 5.1.1, Definition 5.5.2, Theorem 5.5.3, Proposition 5.6.4. This chapter is named for its language and not as a step in an argument: §§01, 03, 04, 05 and 09 cite it in the text, to say which abstract object a half-space or an affine hyperplane is, and two examples use it, but no proof here rests on it. Once $V = \mathbb{R}^n$ , what is worked with is the concrete $\mathbf{x} \mapsto \mathbf{a}^{\top}\mathbf{x}$ .
Chapter 10 §09 — the exponential of a number, with that section’s imported facts (A1)–(A3), from which §11 builds the logarithm and real powers: Theorem 10.9.4. The reference sits in the text of §11 that sets the construction up, not inside a proof.
Chapter 11 — the inner product and the orthogonal projection, which §03 generalizes from subspaces to closed convex sets: Definition 11.1.1, Theorem 11.1.5, Theorem 11.3.2, Definition 11.3.2, Theorem 11.3.3, Theorem 11.3.5.
Chapter 12 §05 — the real spectral theorem, which is how §08 finds the extreme points of the density matrices and of the interval $\mathbf{0} \preceq \mathbf{X} \preceq \mathbf{I}$ : Corollary 12.5.2.
Chapter 13 — positivity: Definition 13.1.1, Theorem 13.1.4, Definition 13.5.1.
Chapter 14 §06 — the Hessian and the second-derivative test, Definition 14.6.2 and Theorem 14.6.4, with that section’s Taylor assumption. As with Chapter 10, §10 names these in the text, to say what it is generalizing and which imported facts it borrows; the proofs cite the assumptions, not the theorem.
Chapter 16 — norms, their unit balls and their equivalence, compactness, and the operator norm: Definition 16.1.1, Definition 16.1.2, Proposition 16.1.2, Lemma 16.1.1, Theorem 16.2.2, Corollary 16.2.3, Corollary 16.2.5, Definition 16.3.2, Theorem 16.3.3.
Chapter 17 — the places where convexity was met: Theorem 17.6.2 and Corollary 17.6.5, Definition 17.8.1 and Theorem 17.8.5, Lemma 17.8.6, Definition 17.11.1 and Proposition 17.11.8.

Roadmap

Convex sets and hulls. The definition, the first examples (half-spaces, the balls of every norm, the standard simplex, the positive semidefinite matrices, the vectors majorized by a fixed vector), the operations that preserve convexity, and the convex hull as the set of all convex combinations. Affine hulls, which are Chapter 4’s cosets. Closed and open sets.
Carathéodory’s theorem. In dimension $n$ , every point of a hull is a convex combination of at most $n + 1$ of the points, and no fewer will do in general. Hence the hull of a compact set is compact. Radon’s theorem, and Helly’s theorem on intersections.
Separating hyperplanes. The nearest point of a closed convex set, characterized by an obtuse-angle condition that becomes Chapter 11’s orthogonality when the set is a subspace. Strict separation of a point from a closed convex set, supporting hyperplanes, and the finite-dimensional Hahn–Banach theorem. Why two disjoint closed convex sets need not be strictly separated.
Gauges, support functions, dual norms. Every bounded, closed, symmetric convex set that contains a ball around $\mathbf{0}$ is the unit ball of a norm, which is the converse of Chapter 16’s convexity remark. The support function, the polar set, and the dual norm, with the proof that the dual of the dual norm is the original norm. This supplies the dual norms that Chapter 16 left out.
Cones and Farkas’s lemma. Convex cones and their duals; a finitely generated cone is closed, which is the subtle step; the alternative theorem of Farkas; and a closed cone with a non-closed linear image, showing why finite generation matters.
Linear programming. Weak and strong duality from Farkas’s lemma, complementary slackness, and a worked problem solved together with its dual. This answers the remark in Chapter 3 §07 that flows with capacities are a problem about inequalities.
The minimax theorem. Matrix games, mixed strategies over the simplex, and von Neumann’s theorem, contrasted with the Courant–Fischer min–max of Chapter 17, whose proof is a dimension count rather than convexity.
Extreme points. A compact convex set is the convex hull of its extreme points (Minkowski’s theorem). The extreme points of the unit balls of the three norms, of the density matrices, and of the doubly stochastic matrices; for the last, Birkhoff’s theorem that the permutation matrices are all of them is stated and left to Chapter 19. A compact convex set whose extreme points do not form a closed set.
Polytopes. Hulls of finitely many points against bounded intersections of finitely many half-spaces, and the Minkowski–Weyl theorem that they are the same sets. Vertices as the basic feasible points of linear programming.
Convex functions. The epigraph, Jensen’s inequality, the second-derivative test, and continuity. A pointwise supremum of affine functions is convex, which accounts for Chapter 17’s Ky Fan sums.
Three classical inequalities. The logarithm and real powers, built from Chapter 10’s exponential; the weighted arithmetic–geometric mean inequality as Jensen’s inequality for $-\log$ ; Young’s and Hölder’s inequalities; Minkowski’s inequality, so that every $\left\| \cdot \right\|_p$ is a norm on $F^n$ ; and the dual of every $p$ -norm, which completes §04. The chapter’s summary closes this section.

Named moves

Count, then drop a point. Too many points in too few dimensions are dependent, affinely or linearly. Move the weights along the dependence until one of them reaches zero, and drop that point without leaving the hull. Carathéodory’s theorem, its version for cones, and Radon’s theorem are all this move.
Nearest point, then the normal direction. To separate a point from a closed convex set, take the nearest point of the set and use the vector from it to the outside point as the normal of the hyperplane. The separation theorems are the geometry of this one projection.
Dualize. A closed convex set is determined by the half-spaces containing it, and a closed convex cone by its dual cone. Every statement about the one side has a statement about the other: Farkas’s lemma is that move made into a theorem, and linear-programming duality is Farkas applied to one combined system.
A supremum of linear functions is convex. Support functions, dual norms, the largest eigenvalue and the Ky Fan sums are all suprema of linear functions, and each inherits its convexity from that alone.
Lift, then eliminate. To see what a set looks like from fewer coordinates, eliminate one variable at a time: Fourier–Motzkin elimination pairs each upper bound with each lower bound, and is what proves the Minkowski–Weyl theorem of §09.
Compactness turns a supremum into a maximum. Chapter 16’s move, used again: once a hull or a set of weights is known to be compact, a maximum or a nearest point is attained at a point that can be named and fed back into the argument.