Marco Cuturi - Teaching

ORF 522 Linear Optimization and Convex Analysis (fall 2009)

Theoretical concepts underlying linear programming, with computer implementations of some of the different methods. Topics covered include basic convexity results, the simplex method, duality theory, linear integer programs, interior point methods, related numerical issues, modeling paradigms, additional convex analysis on polytopes.

Slides

• Lecture 1: Introduction to the Course

• Lecture 2: Linear Programs and Linear Equations

• Lecture 3: Basic Convexity

• Lecture 4: The Geometry of the Solutions of a Linear Program

• Lecture 5: The Simplex

• Lecture 6: Tableaux

• Lecture 7: Initial Solutions and Troubleshooting

• Lecture 8: Complexity of the Simplex

• Lecture 9: Duality

• Lecture 10: Farkas Lemma, the Dual Simplex, Sensitivity

• Lecture 11: Ellipsoid Methods

• Lecture 12: Introduction to Interior Point Methods

Code

Simplex Demo

A Graphical User Interface (click to download) in Matlab to visulize the simplex progression on random problems in 3-dimensions. Download the package, unzip it, open matlab in that folder and type SimplexDemo3D to run the GUI. Below is a screenshot.

Ellipsoid Method and Affine Scaling

A few scripts (click to download) that illustrate the behavior of the ellipsoid method and the affine scaling algorithm with short and long steps on a simple 3D linear program constrained by 20 random inequalities. Download the file, read the readme file and run the scripts directly from the command window. Screenshots below

• Ellipsoid Method

• Affine Scaling

• Affine Scaling with Short and Long Steps