Hours - Lecture:3
Hours - Lab:0
Hours - Recitation:0
Hours - Total Credit:3
Typical Scheduling:Not regularly scheduled. Fall 2012
Convex Geometry, by Greg Blekherman. Special Topics offered in Fall 2012.
Thorough knowledge and understanding of linear algebra.
"A course in Convexity", A. Barvinok. Further Sources: "An elementary introduction to modern convex geometry", K. Ball (survey article), "Convex bodies: the Brunn-Minkowski theory", R. Schneider
- The course should be accessible to first or second year graduate students. Students from ACO and ISyE might be interested in the couse, as well as
theoretical computer science students.
Course Outline: In short, I plan to cover chapters I, II, IV and V of the main textbook before covering some special topics (time permitting). Possible special topics include polytopes, lattice point enumeration (with applications to integer programming) and measure concentration in convex geometry. Polytopes and lattice point enumeration can be taught from the main textbook,while measure concentration will require the use of Ball's survey article.
Topics to be included in the main part:
-Denitions. Radon's theorem. Helly's Theorem. Caratheordory's Theorem.
-Polyhedra. Fourier-Motzkin elimination.
-Boundary Structure of convex sets. Separation Theorems. Extreme points. Krein-Milman
Theorem. Convex Cones.
-Applications to combinatorial polytopes. Application to moment problems.
-Cone of positive semidenite matrices. Cone of nonnegative polynomials and applications.
-Introduction to linear programming, dual problems, duality gap.
-Ellipsoids, approximation of convex bodies by ellipsoids, maximum volume ellipsoid, ellipsoid method for linear programming.
-Measure concentration on the unit sphere. Johnson-Lindenstrauss Lemma. Applications to
low rank matrix approximations.