LPCO
12 Jan -- 12 Apr 2024
Class Timings: Wednesday and Friday (11:30 to 13:00)
Tentative Schedule
- Lecture 1: Admin matters, Introduction, Optimization problems, Convexity, Convex opt, general overview.
- Lecture 2: Two forms of LP (canonical and equational form), basic feasible solutions.
- Lecture 3: Some Geometry behind LP (linear spaces, affine spaces, ...).
- Lecture 4: Starting examples of the simplex method, and introduction to the simplex tableau.
- Lecture 5: A historical viewpoint of the simplex method, completing the argument for correctness of the method.
- Lecture 6: Getting initial feasible solutions, pivot rules, termiantion and cycling.
- Lecture 7: Lower bound on worst case (Klee-Minty example), Kalai-Kleitman bound on diameter of polyhedra.
- Lecture 8: Randomized algorithms for lp (Clarkson's algorithms, Matousek-Sharir-Welzl).
- Lecture 9: Randomized algorithms for lp continued (Clarkson's algorithms, Matousek-Sharir-Welzl).
- Lecture 10: Randomized algorithms for lp continued (Clarkson's algorithms, Matousek-Sharir-Welzl).
- Lecture 11: Abstract LP-type problems.
- Lecture 12: Fundamental theorem of linear inequalities.
- Lecture 13: Equivalence of Polyhedral cones and finitely generated cones (Farkas-Minkowski-Weyl).
- Lecture 14: Fundamental Theorem of Polyhedra theory and (variants of) Farkas's Lemma.
- Lecture 15: Duality in LP (algebraic viewpoint, and proof via Simplex method).
- Lecture 16: Duality in LP (proof based on Farkas's lemma, geometric viewpoint and applications).
- Lecture 17: Ellipsoid method (introduction, optimization reduced to feasibility, basics of ellipsoids).
- Lecture 18: Ellipsoid method (lower bounds on volume of simplices, algorithm details).
- Lecture 19: Ellipsoid method (algorithm analysis, feasibility to separation, weak violation using weak separation oracle).
- Lecture 20: Interior point methods (via non-linear constrained optimization).
- Lecture 21: Interior point methods (the algorithm).
- Lecture 22: Interior point methods (convergence analysis).
- Lecture 23: The perfect matching polytope.
- Lecture 24: Goemans-Williamson -- Approximating max-cut.
- Lecture 25: GW -- tightness of the approximation ratio. Vector programming and SDP.
- Lecture 26: Dualtiy in SDP.
Notes will be updated after every lecture.
References
Books and Papers
- B. Gartner and J. Matousek: Understanding and using linear programming
- Schrijver: Theory of Linear and Integer Programming
-
Homework
