Linear and Semidefinite Programming and Combinatorial Optimization
By: Avner Magen
This course deals with the problem of optimizing linear function in linear or other convex domains, and application to the theory of algorithms, mainly for the approximation of NP-hard problems. The heart of the course will be linear programming. We will first investigate the algebraic and geometric foundations of this object, and then turn to study the algorithmic approaches to solve it. We will present the famous and commonly used Simplex-Method, and then study the first polynomial algorithm to the problem, namely the Ellipsoid algorithm. Another, less algorithmic path we will take is studying the the concept of duality and the duality-theorem in LP. This is possibly the most fundamental theorem in the theory of optimization, and provides an extremely efficient tool to many optimization problems. We will discuss few of the applications of the theorem, Von Neumann minmax principle in game-theory, Yao's minmax principle and the "primal-dual" algorithmic paradigm. We will then discuss positive-semi-definite programming and the way it can be solved using the Ellipsoid algorithm. The last part of the course will deal with methods of approximating NP-hard problems using the convex optimization tools we established in the earlier parts.
Link to material: http://www.cs.toronto.edu/~avner/teaching/S5-2411/index.html