Course Number: CS655A (for PG), CS655B (for UG)
Units: 3-0-0-0-4 (CS655A, PG), 3-0-0-0-9 (CS655B, UG)
Pre-requisite: Basic linear algebra.
The course will focus on basics of convexity theory, linear programming and application of linear programming in computer science. There will be broadly three parts of the course interrelated with each other.
The first part will cover the basics of convex sets, cones and polyhedras; essential to understand the structure behind convex optimization and motivate why so many special cases of it can be solved efficiently. This will also cover hyperplane separation theorems. Linear programming will be introduced and duality theory will be covered in detail.
The second part will talk about major algorithms which are used today to solve linear programming. The major three algorithms, simplex, ellipsoid and interior point method will be discussed. As an assignment they will have to convert a problem into a linear program and solve it using the existing linear programming solvers.
The final part will cover some applications in computer science. Specifically we will cover the multiplicative update method and a recent result where linear programming gives best approximation algorithm for a set of constraint satisfaction problems. Applications in network flows will also be covered.