## CS 655: Topics in Linear Programming

### 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

### 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.

### 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 1-4).
• Introduction to Linear Algebra, Gilbert Strang (Chapter 1-3,6)
• Linear Algebra, Hoffman and Kunze (Chapter 1-3).

### Functional Analysis

• Functional Analysis, Walter Rudin (First four sections in Chapter 1).