Convexity is a simple idea that manifests itself in a surprising variety of places. The main focus of this book is on mathematical applications of convexity rather than on studying convexity for its own sake. These applications range from analysis and probability to algebra, combinatorics, number theory. Finite- and infinite-dimensional optimization problems, such as the Transportation Problem, the Diet Problem, problems of optimal control, statistics and approximation are discussed as well.
In Chapter I, Convex Sets at Large are defined and some of their fundamental properties are explored: what a convex set looks like as a whole, how convex sets may intersect and how they behave with respect to linear transformations, what a convex set looks like in a neighborhood of a point. The landmark results of this chapter are classical theorems of Carathéodory, Radon and Helly and the geometric construction of the Euler characteristic. These results are applied to study positive multivariate polynomials, the problem of uniform (Chebyshev) approximation and some interesting valuations on convex sets, such as the intrinsic volumes. Exercises address some other applications (such as the Gauss-Lucas Theorem), discuss various ramifications of the main results (such as the Fractional Helly Theorem or the Colored Carathéodory Theorem). Two important classes of convex sets, polytopes and polyhedra, are introduced. In Chapter II, Faces and Extreme Points, local properties of closed convex sets in Euclidean space are discussed. A finite-dimensional closed convex set always has an interior when considered in a proper ambient space and, therefore, has a non-trivial boundary. The author explores the structure of the boundary and defines and studies faces and extreme points. The structure of some particular convex sets is analyzed: the Birkhoff polytope, transportation polyhedra, the moment cone, the cone of non-negative univariate polynomials and the cone of positive semidefinite matrices. The main tools are the Isolation Theorem in a general vector space and the Krein-Milman Theorem in Euclidean space. Applications include the Schur-Horn Theorem describing the set of possible diagonals of a symmetric matrix having prescribed eigenvalues, efficient formulas for numerical integration, a characterization of the polynomials that are non-negative on the interval and numerous quadratic convexity results, such as the Brickman Theorem, which describe various situations when the image of a quadratic map turns out to be convex. Quadratic convexity allows one to visualize often counterintuitive results about the facial structure of the cone of positive semidefinite matrices through the existence and rigidity properties of configurations of points in Euclidean space.
In Chapter III, Convex Sets in Topological Vector Spaces are studied. The Krein-Milman Theorem for locally convex topological vector spaces is proved and the extreme points of some convex sets which can be considered as infinite-dimensional extensions of familiar Euclidean objects are explored. In particular, an \(L^\infty\)-analogue of a polyhedron and a “simplex” of probability measures are considered. Applications include problems of optimal control and probability and some “hidden convexity” results based on Lyapunov’s Theorem. This approach is geometric and, whenever possible, similarities between finite- and infinite-dimensional situations are stressed. Exercises address some of the peculiar features of the infinite dimension: existence of dense hyperplanes, discontinuous linear functionals and disjoint convex sets that cannot be separated by a hyperplane.
The author starts Chapter IV, Polarity, Duality and Linear Programming, with polarity in Euclidean space, proves that it extends to a valuation on the algebra of closed convex sets, completes the proof of the Weyl-Minkowski Theorem and proves a necessary and sufficient condition for a point to belong to the moment cone. The duality theory for linear programming in topological vector spaces ordered by cones is developed. Many of the familiar problems such as the Diet Problem, the Transportation Problem, the problem of uniform approximation and the \(L^\infty\) linear programming problems related to optimal control are revisited and some new problems, such as problems of semidefinite programming and the Mass-Transfer Problem are studied. Characterizations of optimal solutions to these problems are obtained.
Chapter V, Convex Bodies and Ellipsoids, explores the metric structure of convex bodies in Euclidean space. Ellipsoids are introduced and it is proved that up to a factor depending on the dimension of the ambient space, any convex body looks like an ellipsoid. How well a convex body can be approximated by a polynomial hypersurface (ellipsoids correspond to quadratic polynomials) is discussed. The Ellipsoid Method for solving systems of linear inequalities is considered. Using the technique of measure concentration for the Gaussian measure in Euclidean space, new results on existence of low rank approximate solutions to systems of linear equations in positive semidefinite matrices are obtained and these results are applied to problems of graph realizability with a distortion. The measure and metric on the unit sphere are briefly discussed. Exercises address ellipsoidal approximations of particularly interesting convex sets (such as the Traveling Salesman Polytope and the set of non-negative multivariate polynomials), various volume inequalities and some results related to the measure concentration technique.
Chapter VI, Faces of Polytopes, explores the combinatorial structure of polytopes: the number of faces of a given dimension that a polytope can have, how the faces fit together and what is the facial structure of some particularly interesting polytopes, such as the permutation polytope and the cyclic polytope. This approach is based on considering a sufficiently generic linear function on a polytope and using some combinatorial (counting) or metric arguments.
Chapter VII, Lattices and Convex Bodies, discusses some discrete aspects of convexity. A lattice in Euclidean space is defined and how lattices interact with convex bodies is explored. It is focused on metric rather than combinatorial aspects of this interaction. The landmark results of this chapter are the theorems of Minkowski and Minkowski-Hlawka with applications to number theory problems and construction of dense sphere packings (which are related to coding), flatness results and the Lenstra-Lenstra-Lovász basis reduction algorithm. Problems address properties of some particular lattices, such as \(\mathbb Z^n\), \(D_n\), \(A_n\), \(E_6\), \(E_7\) and \(E_8\); results on enumeration of lattice points in convex bodies, such as Pick’s Formula and its extensions; and other interesting results, such as Doignon’s lattice version of Helly’s Theorem.
Chapter VIII, Lattice Points and Polyhedra, discusses the enumeration of lattice points in polyhedra. The main tools are generating functions, also known as exponential sums, and some identities in the algebra of polyhedra. A parallel theory for exponential integrals is developed in the exercises. The case of the standard integer lattice \(\mathbb Z^d\subset\mathbb R^d\) is considered. The case of a general lattice \(\Lambda\subset \mathbb R^d\) reduces to that of \(\mathbb Z^d\) by a change of the coordinates.
The book will benefit both teacher and student. It is easy to understand, and entertaining to the reader.