CIS 610, Summer 1, 2009

Brief description:

Syllabus:

1. Affine and Euclidean geometry, spectral theorems, SVD, pseudo-inverses and PCA,
2. Convex sets, polytopes, polyhedra and basics of linear programming

The material in (2) provides firm foundations for linear programming and convex programming.

1. Basics of Affine Geometry
   • Affine spaces, affine combinations (barycenters)
   • Affine subspaces, affine independence, affine frames, convex combinations
   • Affine maps, affine groups
   • A glimpse at affine geometry (Pappus, Desargues)
   • Hyperplanes and affine forms, intersection of affine spaces.
   (Chapter 1-2 of GMA)
2. Euclidean Geometry
   • Inner Products, Euclidean Spaces
   • Orthogonality, Orthogonal and Orthonormal bases, Gram-Schmidt
   • A glimpse at Fourier Series
   • Linear Isometries (also called orthogonal transformations), the orthogonal group, orthogonal matrices, the Groups O(n), SO(n)
   • Hyperplane reflections and the Cartan-Dieudonne' Theorem
   • QR-decomposition
   • Householder matrices and QR-decomposition
   (Chapters 6 and 7 of GMA)
3. Spectral theorems in Euclidean geometry and Hermitian spaces,
   • Normal linear maps, self-adjoint linear maps, skew self-adjoint linear maps
   (Chapter 11 of GMA)
4. Singular value decomposition and polar forms
   • Polar form
   • Singular value decomposition (SVD)
   • Pseudo-inverses
   • Least squares and PCA
   (Chapters 12 and 13 of GMA)
5. Convex sets and Polytopes
   
   • Basic properties of convex sets, Half spaces determined by hyperplanes
   • Caratheodory's theorem on convex hulls
   • Radon's theorem
   • Helly's theorem.
   • Existence of center points
   • Separation theorems: Hahn-Banach theorem and others.
   • Supporting hyperplanes, Minkowski's theorem.
   • The Farkas lemma
   • Vertices and Extremal points, Krein and Milman's theorem.
   • Polytopes and polyhedra: H-polytopes and V-polytopes. Cones. Vertices, faces and facets.
   • Polarity and duality. The main theorem.
   • Fourier-Motzkin elimination, the equivalence of H-polyhedra and V-polyhedra revisited
     We may also discuss applications to the Support Vector Machine Method
   (Chapter 3 of GMA + Notes)
6. Foundations of Linear Programming
   
   • Linear programming
   • Primal and Dual Programs
   • Lagrangian functions and Strong Duality
   • Application to fractional packing and covering problems
   • Introduction to primal-dual combinatorial algorithms

Back to Gallier Homepage

published by:

Jean Gallier