3rd February 2003 - Linear programming
Following on from last week, Ed and Angela are going to sort out unresolved issues and move onto Lagrangian methods and duality.
- Please read: Geoffrey J. Gordon's notes [1]. Lagrangian formulation of LP, relationship to saddle-point optimization, game theory, duality, log-barrier methods, and central path.
- If at all possible, please also read Daniel Kleitman course notes: chapters 26 and 27 and 28. An intuitive overview of Linear Programming, the Simplex algorithm, and Duality, with applications to Network Flow/Min-Cut.
- If you have lots of time, Richard Weber's notes are also excellent. Ed says that chapters 5, 6, 7, 9, 10 and 11 (!) are all relevant.
If you have trouble obtaining the reading material, please contact Iain. Other related material is available on the journal club's Mathematical Programming Algorithms page.
[1] kghostview chucks up on Geoffrey Gordon's notes, although /usr/X11R6/bin/gv is fine. If you have problems viewing or printing, try using uncompress followed by ps2ps before viewing.