ORF 522 Linear Optimization, Convex Analysis (Princeton, ORFE, Fall 2009)

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

• Lecture 13: Introduction to Network Flows

• Lecture 14: Network Simplex

• Lecture 15: Network Simplex for Capacitated Problems and the Ford-Fulkerson Algorithm

• Lecture 16: Applications in Finance of Linear Programs and Duality

• Lecture 17: Integer Linear Programs

• Lecture 18: Cutting Planes, Branch-and-bound, Knapsack, Dynamic Programming

• Lecture 19: A Window on Semidefinite Programming

• Lecture 20: Linear Equations on Semidefinite Matrices

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