CS 698J/R: Topics in Linear programming
Course description:Linear Programming is a special class of mathematical optimization where the constraints and the cost function are linear. This class of problems have known efficient algorithms and wide applications in various fields.
The course will have detailed introduction to the field of linear optimization. The first part of the course will cover the basics of convex optimization and look at various aspects of linear programming which make it more tractable. Various known algorithms to solve linear programs will also be covered. In the later half, the focus will be on the applications of linear programming in theoretical computer science.
CS 698J/R: Notes
|31st July 2014||Introduction to mathematical optimization||Lecture 1|
|1st August 2014||Linear algebra||Lecture 2|
|7th August 2014||Linear combinations||Lecture 3|
|8th August 2014||Convex sets||Lecture 4|
|14th August 2014||Properties of convex sets||Lecture 5|
|16th August 2014||Linear programs||Lecture 6|
|21st August 2014||Simplex method: The idea||Lecture 7|
|22nd August 2014||Simplex method||Lecture 8|
|28th August 2014||Hyperplane separation theorems||Lecture 9|
|29th August 2014||Duality||Lecture 10|
|4th Sept 2014||Strong duality||Lecture 11|
|5th Sept 2014||Revision|
|11th Sept 2014||Revision|
|12th Sept 2014||Quiz||Lecture 14|
|25th Sept 2014||Max flow and min cut||Lecture 15|
|26th Sept 2014||Primal dual method||Lecture 16|
|9th October 2014||Interior point methods||Lecture 17|
|16th October 2014||Guest lecture: Sreyash Kenkre||Lecture 18|
|17th October 2014||Guest lecture: Sreyash Kenkre||Lecture 19|
|18th October 2014||Quiz 3||Lecture 20|
|19th October 2014||Guest lecture: Rishabh Vaid||Article , Video|
|25th October 2014||Multiplicative weight update method||Lecture 23|
|26th October 2014||LP-based algorithm for vertex cover||Lecture 24|
CS 698C/K: References
- Fundamentals of Convex Analysis, Jean Baptiste Hiriart Urruty and Claude Lemarechal (section A).
- Linear Programming, Dantzig and Thapa.
- Combinatorial Optimization: Algorithms and Complexity, Papadimitriou and Steiglitz.
- Convex Optimization, Boyd and Vandenberghe.
- Linear Programming: Foundations and extensions, Robert J. Vanderbei.
- Linear Algebra: An introductory approach, Charles W. Curtis (Chapter 1-4).
- Introduction to Linear Algebra, Gilbert Strang (Chapter 1-3,6)
- Linear Algebra, Hoffman and Kunze (Chapter 1-3).
- Functional Analysis, Walter Rudin (First four sections in Chapter 1).
Interior point method
- Interior point method 25 years later, Jacek Gondzio.
- Intuition behind primal dual interior point method, Peter Carbonetto.
- Interior point methods and Linear Programming, Robert Robere.
- Numerical Optimization, Jorge Nocedal and Stephen Wright.
Project: Multiplicative weight update method
Constraint satisfaction problems