LPCO
05 Aug  07 Dec 2015
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 (KleeMinty example), KalaiKleitman bound on diameter of polyhedra.
 Lecture 8: Randomized algorithms for lp (Clarkson's algorithms, MatousekSharirWelzl).
 Lecture 9: Randomized algorithms for lp continued (Clarkson's algorithms, MatousekSharirWelzl).
 Lecture 10: Randomized algorithms for lp continued (Clarkson's algorithms, MatousekSharirWelzl).
 Lecture 11: Abstract LPtype problems.
 Lecture 12: Fundamental theorem of linear inequalities.
 Lecture 13: Equivalence of Polyhedral cones and finitely generated cones (FarkasMinkowskiWeyl).
 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 nonlinear constrained optimization).
 Lecture 21: Interior point methods (the algorithm).
 Lecture 22: Interior point methods (convergence analysis).
 Lecture 23: The perfect matching polytope.
 Lecture 24: GoemansWilliamson  Approximating maxcut.
 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