A Course in Convexity (Graduate Studies in Mathematics, V. 54) (Graduate Studies in Mathematics, 54)

Convexity is a simple idea that manifests itself in a surprising variety of places. This fertile field has an immensely rich structure and numerous applications. Barvinok demonstrates that simplicity, intuitive appeal, and the universality of applications make teaching (and learning) convexity a gratifying experience. The book will benefit both teacher and student: It is easy to understand, entertaining to the reader, and includes many exercises that vary in degree of difficulty. Overall, the author demonstrates the power of a few simple unifying principles in a variety of pure and applied problems. The prerequisites are minimal amounts of linear algebra, analysis, and elementary topology, plus basic computational skills. Portions of the book could be used by advanced undergraduates. As a whole, it is designed for graduate students interested in mathematical methods, computer science, electrical engineering, and operations research. The book will also be of interest to research mathematicians, who will find some results that are recent, some that are new, and many known results that are discussed from a new perspective. Title Contents Preface Chapter I. Convex Sets at Large 1. Convex Sets. Main Definitions, Some Interesting Examples and Problems 2. Properties of the Convex Hull. Caratheodory's Theorem 3. An Application: Positive Polynomials 4. Theorems of Radon and Helly 5. Applications of Helly's Theorem in Combinatorial Geometry 6. An Application to Approximation 7. The Euler Characteristic 8. Application: Convex Sets and Linear Transformations 9. Polyhedra and Linear Transformations 10. Remarks Chapter II. Faces and Extreme Points 1. The Isolation Theorem 2. Convex Sets in Euclidean Space 3. Extreme Points. The Krein-Milman Theorem for Euclidean Space 4. Extreme Points of Polyhedra 5. The Birkhoff Polytope 6. The Permutation Polytope and the Schur-Horn Theorem 7. The Transportation Polyhedron 8. Convex Cones 9. The Moment Curve and the Moment Cone 10. An Application: 'Double Precision' Formulas for Numerical Integration 11. The Cone of Non-negative Polynomials 12. The Cone of Positive Semidefinite Matrices 13. Linear Equations in Positive Semidefinite Matrices 14. Applications: Quadratic Convexity Theorems 15. Applications: Problems of Graph Realizability 16. Closed Convex Sets 17. Remarks Chapter III. Convex Sets in Topological Vector Spaces 1. Separation Theorems in Euclidean Space and Beyond 2. Topological Vector Spaces, Convex Sets and Hyperplanes 3. Separation Theorems in Topological Vector Spaces 4. The Krein-Milman Theorem for Topological Vector Spaces 5. Polyhedra in L 6. An Application: Problems of Linear Optimal Control 7. An Application: The Lyapunov Convexity Theorem 8. The 'Simplex' of Probability Measures 9. Extreme Points of the Intersection. Applications 10. Remarks Chapter IV. Polarity, Duality and Linear Programming 1. Polarity in Euclidean Space 2. An Application: Recognizing Points in the Moment Cone 3. Duality of Vector Spaces 4. Duality of Topological Vector Spaces 5. Ordering a Vector Space by a Cone 6. Linear Programming Problems 7. Zero Duality Gap 8. Polyhedral Linear Programming 9. An Application: The Transportation Problem 10. Semidefinite Programming 11. An Application: The Clique and Chromatic Numbers of a Graph 12. Linear Programming in L°° 13. Uniform Approximation as a Linear Programming Problem 14. The Mass-Transfer Problem 15. Remarks Chapter V. Convex Bodies and Ellipsoids 1. Ellipsoids 2. The Maximum Volume Ellipsoid of a Convex Body 3. Norms and Their Approximations 4. The Ellipsoid Method 5. The Gaussian Measure on Euclidean Space 6. Applications to Low Rank Approximations of Matrices 7. The Measure and Metric on the Unit Sphere 8. Remarks Chapter VI. Faces of Polytopes 1. Polytopes and Polarity 2. The Facial Structure of the Permutation Poly tope 3. The Euler-Poincare Formula 4. Polytopes with Many Faces: Cyclic Polytopes 5. Simple Polytopes 6. The h- vector of a Simple Poly tope. Dehn-Sommerville Equations 7. The Upper Bound Theorem 8. Centrally Symmetric Polytopes 9. Remarks Chapter VII. Lattices and Convex Bodies 1. Lattices 2. The Determinant of a Lattice 3. Minkowski's Convex Body Theorem 4. Applications: Sums of Squares and Rational Approximations 5. Sphere Packings 6. The Minkowski-Hlawka Theorem 7. The Dual Lattice 8. The Flatness Theorem 9. Constructing a Short Vector and a Reduced Basis 10. Remarks Chapter VIII. Lattice Points and Polyhedra 1. Generating Functions and Simple Rational Cones 2. Generating Functions and Rational Cones 3. Generating Functions and Rational Polyhedra 4. Brion's Theorem 5. The Ehrhart Polynomial of a Polytope 6. Example: Totally Unimodular Polytopes 7. Remarks Bibliography Index Convexity is a simple idea that manifests itself in a surprising variety of places. This fertile field has an immensely rich structure and numerous applications. Barvinok demonstrates that simplicity, intuitive appeal, and the universality of applications make teaching (and learning) convexity a gratifying experience. The book will benefit both teacher and It is easy to understand, entertaining to the reader, and includes many exercises that vary in degree of difficulty. Overall, the author demonstrates the power of a few simple unifying principles in a variety of pure and applied problems. The notion of convexity comes from geometry. Barvinok describes here its geometric aspects, yet he focuses on applications of convexity rather than on convexity for its own sake. Mathematical applications range from analysis and probability to algebra to combinatorics to number theory. Several important areas are covered, including topological vector spaces, linear programming, ellipsoids, and lattices. Specific topics of note are optimal control, sphere packings, rational approximations, numerical integration, graph theory, and more. And of course, there is much to say about applying convexity theory to the study of faces of polytopes, lattices and polyhedra, and lattices and convex bodies. The prerequisites are minimal amounts of linear algebra, analysis, and elementary topology, plus basic computational skills. Portions of the book could be used by advanced undergraduates. As a whole, it is designed for graduate students interested in mathematical methods, computer science, electrical engineering, and operations research. The book will also be of interest to research mathematicians, who will find some results that are recent, some that are new, and many known results that are discussed from a new perspective. Barvinok Demonstrates That Simplicity, Intuitive Appeal, And The Universality Of Applications Make Teaching (and Learning) Convexity A Gratifying Experience. The Prerequisites Are Minimal Amounts Of Linear Algebra, Analysis, And Elementary Topology, Plus Basic Computational Skills. Portions Of The Book Could Be Used By Advanced Undergraduates. As A Whole, It Is Designed For Graduate Students Interested In Mathematical Methods, Computer Science, Electrical Engineering, And Operations Research. The Book Will Also Be Of Interest To Research Mathematicians, Who Will Find Some Results That Are Recent, Some That Are New, And Many Known Results That Are Discussed From A New Perspective.--jacket. Ch. I. Convex Sets At Large -- Ch. Ii. Faces And Extreme Points -- Ch. Iii. Convex Sets In Topological Vector Spaces -- Ch. Iv. Polarity, Duality And Linear Programming -- Ch. V. Convex Bodies And Ellipsoids -- Ch. Vi. Faces Of Polytopes -- Ch. Vii. Lattices And Convex Bodies -- Ch. Viii. Lattice Points And Polyhedra. Alexander Barvinok. Includes Bibliographical References (p. 357-362) And Index. "Barvinok demonstrates that simplicity, intuitive appeal, and the universality of applications make teaching (and learning) convexity a gratifying experience. The prerequisites are minimal amounts of linear algebra, analysis, and elementary topology, plus basic computational skills. Portions of the book could be used by advanced undergraduates. As a whole, it is designed for graduate students interested in mathematical methods, computer science, electrical engineering, and operations research. The book will also be of interest to research mathematicians, who will find some results that are recent, some that are new, and many known results that are discussed from a new perspective."--BOOK JACKET. We define convex sets and explore some of their fundamental properties.