BAP: Lecture 11 (Mar 19, 2002)

The notes for this lecture are available in

latex,
postscript, and
pdf

In this lecture, we

Saw von Neumann's algorithm for linear programming. Material for this part of the lecture came from Condition Number Complexity of an Elementary Algorithm for Resolving a Conic Linear System by Marina Epelman and Rob Freund.
A polar description of a special case of the linear programming problem.
Primal and Dual simplex methods for solving that linear program.
An elementary proof that the value of that primal is the same as the value of that dual.

In class, we saw demos of these algorithms. The code for these demos lives in the directory http://math.mit.edu/~spielman/BAP/lect11/
The demo of the von Neumann algorithm is in script

vnLPdemo.m

The demo of the primal simplex method is in

pSimpDemo.m

A slowed-down version is in

pSimpDemoSlow.m

and a version in which we plant a basic feasible solution is

pSimpDemoFeas.m

A crude depition of the dual method came from

frags.m