CS 655: Topics in Linear Programming
Announcements
Course Notes
Topic  Link 
Introduction to linear programming, basics of linear algebra, definitions.  Introduction 
Convex sets, properties, simplex method and degeneracy  Convexity 
Separating hyperplanes, duality theory, strong duality  Duality 
Maximum flow, minimum cut and primal dual approach  Primal dual method 
Administrative details:
 Time: 3:304:45 WF, Venue: KD 102
 TA's: Abhishek Dang and Bhaskar Mukhoty.
 Anticheating policy: from CSE Dept
 Drop policy: from DUGC

Grading:
 Exams (70): 3 Quizzes: 5 + 10 + 10, Midsem: 15, Endsem: 25.
 Project (35)
Course description:
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.
The course will provide detailed introduction to the field of linear optimization.
We will start by covering the basics of convex optimization and linear algebra briefly. The background material will not be covered in detail; it is expected that either students know it or can read and recall it. We will move to the definition of linear programs next and show how to model various problems as a linear program. The last part of the first half will give outline of some approaches to solve a linear program.
The later part of the course will focus on applying linear programming in theoretical computer science. We will cover many interesting applications in diverse fields such as network algorithms, complexity theory and approximation theory. If time permits, a small introduction to semidefinite programming will be given with a basic application.
References
Optimization
 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
 Linear Algebra: An introductory approach, Charles W. Curtis (Chapter 14).
 Introduction to Linear Algebra, Gilbert Strang (Chapter 13,6)
 Linear Algebra, Hoffman and Kunze (Chapter 13).
Functional Analysis
 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.