ABOUT THE COURSE: Linear programming is a special class of mathematical optimization problems where the constraints as well as the cost function is linear. This class of problems have known efficient algorithms, deep structural properties and wide applications in various fields. In this course we not only introduce and learn about linear programming, but also see its uses in different areas of computer science (algorithms, algorithmic game theory, theoretical computer science, machine learning).INTENDED AUDIENCE: Senior undergraduate (3rd or 4th year) and masters/phd students in CSEPREREQUISITES: Linear algebra
Linear programming and its applications to computer science
Indian Institute of Technology Kanpur and NPTEL via Swayam
Overview
Syllabus
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.
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.
Taught by
Prof. Rajat Mittal
