A course in convexity / Alexander Barvinok.

Format:

Book

Author/Creator:

Barvinok, Alexander, 1963-

Series:

Graduate studies in mathematics 1065-7339 ; v. 54.

Graduate studies in mathematics, 1065-7339 ; v. 54

Language:

English

Subjects (All):

Convex geometry.

Functional analysis.

Programming (Mathematics).

Physical Description:

x, 366 pages : illustrations ; 26 cm.

Place of Publication:

Providence, R.I. : American Mathematical Society, 2002.

Contents:

Chapter I. Convex Sets at Large 1

1. Convex Sets. Main Definitions, Some Interesting Examples and Problems 1

2. Properties of the Convex Hull. Caratheodory's Theorem 7

3. An Application: Positive Polynomials 12

4. Theorems of Radon and Helly 17

5. Applications of Helly's Theorem in Combinatorial Geometry 21

6. An Application to Approximation 24

7. The Euler Characteristic 28

8. Application: Convex Sets and Linear Transformations 33

9. Polyhedra and Linear Transformations 37

10. Remarks 39

Chapter II. Faces and Extreme Points 41

1. The Isolation Theorem 41

2. Convex Sets in Euclidean Space 47

3. Extreme Points. The Krein-Milman Theorem for Euclidean Space 51

4. Extreme Points of Polyhedra 53

5. The Birkhoff Polytope 56

6. The Permutation Polytope and the Schur-Horn Theorem 58

7. The Transportation Polyhedron 60

8. Convex Cones 65

9. The Moment Curve and the Moment Cone 67

10. An Application: "Double Precision" Formulas for Numerical Integration 70

11. The Cone of Non-negative Polynomials 73

12. The Cone of Positive Semidefinite Matrices 78

13. Linear Equations in Positive Semidefinite Matrices 83

14. Applications: Quadratic Convexity Theorems 89

15. Applications: Problems of Graph Realizability 94

16. Closed Convex Sets 99

17. Remarks 103

Chapter III. Convex Sets in Topological Vector Spaces 105

1. Separation Theorems in Euclidean Space and Beyond 105

2. Topological Vector Spaces, Convex Sets and Hyperplanes 109

3. Separation Theorems in Topological Vector Spaces 117

4. The Krein-Milman Theorem for Topological Vector Spaces 121

5. Polyhedra in L[infinity] 123

6. An Application: Problems of Linear Optimal Control 126

7. An Application: The Lyapunov Convexity Theorem 130

8. The "Simplex" of Probability Measures 133

9. Extreme Points of the Intersection. Applications 136

10. Remarks 141

Chapter IV. Polarity, Duality and Linear Programming 143

1. Polarity in Euclidean Space 143

2. An Application: Recognizing Points in the Moment Cone 150

3. Duality of Vector Spaces 154

4. Duality of Topological Vector Spaces 157

5. Ordering a Vector Space by a Cone 160

6. Linear Programming Problems 162

7. Zero Duality Gap 166

8. Polyhedral Linear Programming 172

9. An Application: The Transportation Problem 176

10. Semidefinite Programming 178

11. An Application: The Clique and Chromatic Numbers of a Graph 182

12. Linear Programming in L[infinity] 185

13. Uniform Approximation as a Linear Programming Problem 191

14. The Mass-Transfer Problem 196

15. Remarks 202

Chapter V. Convex Bodies and Ellipsoids 203

1. Ellipsoids 203

2. The Maximum Volume Ellipsoid of a Convex Body 207

3. Norms and Their Approximations 216

4. The Ellipsoid Method 225

5. The Gaussian Measure on Euclidean Space 232

6. Applications to Low Rank Approximations of Matrices 240

7. The Measure and Metric on the Unit Sphere 244

8. Remarks 248

Chapter VI. Faces of Polytopes 249

1. Polytopes and Polarity 249

2. The Facial Structure of the Permutation Polytope 254

3. The Euler-Poincare Formula 258

4. Polytopes with Many Faces: Cyclic Polytopes 262

5. Simple Polytopes 264

6. The h-vector of a Simple Polytope. Dehn-Sommerville Equations 267

7. The Upper Bound Theorem 270

8. Centrally Symmetric Polytopes 274

9. Remarks 277

Chapter VII. Lattices and Convex Bodies 279

1. Lattices 279

2. The Determinant of a Lattice 286

3. Minkowski's Convex Body Theorem 293

4. Applications: Sums of Squares and Rational Approximations 298

5. Sphere Packings 302

6. The Minkowski-Hlawka Theorem 305

7. The Dual Lattice 309

8. The Flatness Theorem 315

9. Constructing a Short Vector and a Reduced Basis 319

10. Remarks 324

Chapter VIII. Lattice Points and Polyhedra 325

1. Generating Functions and Simple Rational Cones 325

2. Generating Functions and Rational Cones 330

3. Generating Functions and Rational Polyhedra 335

4. Brion's Theorem 341

5. The Ehrhart Polynomial of a Polytope 349

6. Example: Totally Unimodular Polytopes 353.

Notes:

Includes bibliographical references (pages 357-362) and index.

ISBN:

0821829688

OCLC:

50347977