Week 1: After talking about the motivation behind studying linear programming, we will move to the basics of liner algebra. In particular, we will cover Gaussian elimination, rank-nullity, column space-row space duality. The definition and basics of linear programming will be covered.
The other part of the background will cover the basics of linear and affine combinations, 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 lead to simplex algorithm.(Contd)
Week 2: After talking about the motivation behind studying linear programming, we will move to the basics of liner algebra. In particular, we will cover Gaussian elimination, rank-nullity, column space-row space duality. The definition and basics of linear programming will be covered.
The other part of the background will cover the basics of linear and affine combinations, 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 lead to simplex algorithm.(Contd)
Week 3: After talking about the motivation behind studying linear programming, we will move to the basics of liner algebra. In particular, we will cover Gaussian elimination, rank-nullity, column space-row space duality. The definition and basics of linear programming will be covered.
The other part of the background will cover the basics of linear and affine combinations, 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 lead to simplex algorithm.
Week 4: This module will start with hyperplane separation theorems. Duality theory, one of the main reasons why linear programming has so many applications, will be covered in detail.
As an application of strong duality, we will start with Von Neumann’s minimax theorem. The minimax theorem will be used to show the existence of Nash equilibria (from John Nash of “a beautiful mind”); we will also cover Yao’s technique to give lower bounds in communication complexity setting. (Contd)
Week 5: This module will start with hyperplane separation theorems. Duality theory, one of the main reasons why linear programming has so many applications, will be covered in detail.
As an application of strong duality, we will start with Von Neumann’s minimax theorem. The minimax theorem will be used to show the existence of Nash equilibria (from John Nash of “a beautiful mind”); we will also cover Yao’s technique to give lower bounds in communication complexity setting.
Week 6: The relation between primal and dual can be used to show the famous max flow-min cut theorem. We will discuss primal-dual methods too, this will allow us to develop an algorithm for the max flow problem.
Week 7: In many instance, the quantity in focus does not turn out to be a linear program, instead it is modeled as a integer linear program (ILP). We will introduce the concept of relaxation of a linear program. The concept of relaxation and its rounding will be used to give approximation algorithm for set cover problem.
Week 8: We will discuss some applications of linear programming in machine learning. In particular, tasks like linear regression and classification will be approached with linear programming tools.
If time permits, we will see other applications (like in the area of Boolean functions) of linear programming and possible extensions.
DOWNLOAD APP
FOLLOW US