Course Announcement (pdf file)
The final exam is here.
Lecture notes:
lec01, lec02,
lec03
lec03 with hw1,
lec04,
lec05,
lec06,
lec07,
lec07 with hw2,
lec08,
lec09,
lec10,
lec11,
lec12,
lec13,
lec14,
lec15,
lec15 with hw3,
lec16,
lec17,
lec18,
lec19,
lec20,
lec20 with hw4,
lec21,
lec22,
lec23,
lec24,
lec25,
lec26,
lec27.
LaTeX lecture template
Assignments: hw1, hw1 solutions, hw2, hw2 solutions, hw3, hw3 solutions, hw4, hw4 solutions.
List of books on reserve in Uris library. See also here. Murty's book is also available on line here.
A paper by Ferris and Pang (in SIAM Review 39:669--713, 1997) on applications of linear and nonlinear complementarity problems.
Some slides by Anitescu on using LCPs to model multi-rigid-body dynamics with contact and friction.
A paper by Kojima, Mizuno, and Yoshise (in Mathematical Programming 44:1--26, 1989) on a polynomial interior-point method for linear complementarity problems.
Komei Fukuda's FAQs on polyhedral computation and convex polyhedra.
Santos's paper giving a counterexample to the Hirsch conjecture.
Ziegler's paper Who solved the Hirsch conjecture?.
Kalai and Kleitman's paper on the diameter of polyhedra, and my note improving the bound.
Kalai's paper on his randomized simplex pivot rule with subexponential expected behavior.
A paper by Kaibel, Mechtel, Sharir, and Ziegler, showing that the random-edge simplex method on a 3-dimensional linear programming problem with n facets takes expected number of pivots between 4n/3 and 3n/2. While every simplex method on such a problem takes at most a linear number of pivots (at most 3n + 6, using Euler's relation), this is of interest because this simplest of randomized rules for a long time defied analysis in the general case, which led Kalai to his more complicated rule in the paper above. Now it is known to have exponential examples: see "Who solved the Hirsch conjecture?" above.
My paper on polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems.
Slides from my talk on "The Many Facets of Linear Programming" with some topics related to the efficiency of the simplex method, and in particular pictures of a quartz crystal (polytope good for the simplex method) and a disco ball (good for an interior-point method). See pages 1 -- 14. The associated paper.
Survey paper by Bland, Goldfarb and Todd on the ellipsoid method.
A paper by Bertsimas and Vempala showing howing random walks can make the method of centers of gravity tractable.
Paper on dual variables in the ellipsoid method.
Slides from my talk on conic programming with examples of applications (mostly of semidefinite programming) in various areas.
Fourteen lectures by Arkady Nemirovski on efficient methods in convex programming, with lots of material on localizer and gradient-based methods. Other lecture notes may be found at this site.
A paper by Anderson and Lewis on a simplex-like algorithm for semi-infinite linear programming.
A paper by Marron, Todd and Ahn on two-class discrimination using conic programming.
Useful sites