Notes from 2018

Handwritten scanned copies of my notes from previous semesters (pdf files):

- Introduction, basic feasible solutions,
duality, and the simplex algorithm.
- Introduction: Lecture 1: Pages 1-8. Pages 5-8 are covered in the first three handouts
- Basic feasible solutions, degeneracy: Lecture 2: Pages 9-19. Here are typewritten notes for part of this material: html pdf
- Duality: Lecture 3: Pages 20-29. Here are typewritten notes: (i) motivating the dual problem html pdf (ii) showing how to construct a dual problem html pdf (iii) and giving some duality theorems html pdf
- The simplex algorithm: Lecture 4: Pages 30-42. Here are typewritten notes (i) giving an example of simplex html, pdf, (ii) discussing an iteration in general html, pdf, (iii) obtaining a dual solution from simplex and proving strong duality html, pdf, (iv) giving a formal statement of the algorithm html, pdf, (v) and containing more discussion of simplex html, pdf.
- Multiple optimal solutions, handling free variables and upper bounds: Lecture 5: Pages 43-50. Here are typewritten notes on (i) handling upper bounds in the simplex algorithm html pdf (ii) and the relationship between multiple optimal solutions and degeneracy html, pdf.

- Revised simplex, resolution.
- Lecture 6: Revised simplex method, pages 1-8. Typewritten notes (i) part 1 html, pdf (ii) and part 2 html, pdf. Dual simplex method html, pdf. Introduction to AMPL.
- Lecture 7: Fourier-Motzkin elimination, pages 16-22; example html, pdf. Using Farkas to prove strong duality, page 29: html, pdf. Resolution, pages 9-15, html, pdf.
- Lecture 8: The Weyl and Minkowski theorems, pages 23-28: html, pdf (updated from class to include more examples).

- The Klee Minty cube: Lecture 7.
- Probabilistic analysis of the simplex method: Lecture 7. Focus on the results on pages 4, 5, and 9.
- The ellipsoid method: Lecture 9. Here are typewritten notes html, pdf. Here is the New York Times page on the discovery of the ellipsoid algorithm from November 27, 1979.
- Dantzig-Wolfe decomposition,
cutting stock problems, network simplex, multicommodity network flows.
- Lecture 9: introduction to Dantzig-Wolfe, pages 1-5; html, pdf, with the definition of an extreme ray for a pointed polyhedron. An example of Dantzig-Wolfe decomposition: html, pdf,
- Lecture 10: pages 6-18. Dantzig-Wolfe iteration and behavior, block angular structure: html, pdf. Also, interpreting Dantzig-Wolfe decomposition as a cutting plane method for the Lagrangian dual: html, pdf. See also a computational study of Dantzig-Wolfe decomposition from 2001.
- Lecture 11: Lagrangian relaxation, cutting stock problems, pages 19-27: html, pdf. Some material from Ecker and Kupferschmid on a column generation approach to crew scheduling. An example of solving a Lagrangian dual problem with a cutting plane approach. html, pdf.
- Lecture 12: Graph theory (also available as a pdf with more pictures but more page breaks). LP formulations of network flow problems: html, pdf.
- Lecture 13: snowed out.
- Lecture 14: The network simplex algorithm: html, pdf. Multicommodity network flow problems: html, pdf.
- Lecture 15: A network interdiction problem: html, pdf.

- Stochastic programming.
- Lecture 15: pages 1-5. Introductory material: html. Here's some material on the newsvendor problem: html, pdf.
- Lecture 16: pages 6-11. The L-shaped decomposition method: html, pdf. An example: html, pdf.
- Lecture 17: pages 17-26. Sample average approximation: html, pdf. Different methods for handling risk: html, pdf. Here is an ampl model file, a data file with the network and scenario information, and a data file with the CVaR parameters for a network capacity expansion problem. Here is an ampl model file and data file to find the robust solution of an LP; here is the output. The results on sample average approximation can be found in a tutorial on stochastic programming by Shapiro and Philpott.

- Introduction
to interior point methods:
strict complementarity, the central path,
primal-dual framework, complexity theory, affine methods,
the centering direction, a potential-reduction method.

Pages 24-29 covered in Lecture 19. Typewritten handout on the primal affine method: html, pdf.

Pages 1-8 covered in Lecture 20. Strict complementarity: html, pdf.

Pages 9-17 covered in Lecture 21. See also the typewritten handouts on the central path html, pdf and primal-dual methods html, pdf.

Pages 18-22 covered in Lecture 22. Some complexity terminology: html, pdf. - Barrier methods.

Pages 6-18 covered in Lecture 22. A general framework for proving complexity of interior point algorithms, and a short step path following algorithm: html, pdf. - Long-steps, quadratic convergence, predictor-corrector,
finite termination, crossover, infeasible methods.

Pages 6-10 covered in Lecture 23. See also notes on the Mizuno-Todd-Ye predictor-corrector algorithm: html, pdf.

Page 14 covered in Lecture 23. See notes on a crossover scheme: html, pdf.

Pages 11-13, 15-16 covered in Lecture 24. See notes on limit points: html, pdf. - Homogenized methods,
Mehrotra's predictor-corrector, sparse linear algebra,
interior point cutting plane methods.

Pages 1-4 covered in Lecture 24. See question 4 on the midterm exam from 2010 and question 4 on the takehome midterm exam from 2004.

Pages 5-9 covered in Lecture 23. See also notes on the Mehrotra predictor-corrector algorithm: html, pdf.~~Pages 10-14 summarized in ten minutes in Lecture 24~~.

Pages 19-25 covered in Lecture 24, using slides 3/72 to 30/72 of this talk on interior point cutting plane methods. The talk is based on a paper. - SDP
and SOCP.

Pages 1-7, 18-20 covered in Lecture 25. SDP relaxation for MaxCut: html, pdf. Duals of semidefinite programs: html, pdf. Examples of duals of semidefinite programs: html, pdf.

Pages 8-15, 17 and 21 covered in Lecture 26. Barrier methods for semidefinite programs: html, pdf. Simultaneous diagonalization: html, pdf.

Pages 16 and 22-32 covered in Lecture 27. Some more material on semidefinite programming: html, pdf. Second order cone programming: html, pdf.

Sensor location as an SDP covered in Lecture 28: html, pdf.

Page 33 on robust optimization covered in Lecture 28: html, pdf.

Conic optimization covered in Lecture 28: html, pdf.

~~Lecture 28: Pages 35/72 to 53/72 and 67/72 to 69/72 from this talk on interior point cutting plane methods should be covered. It is based on a paper.~~

The book Convex Optimization, by Boyd and Vandenberghe, contains a wealth of material on SDP, SOCP, and conic programming. - Completely positive programming. Lecture 28: html, pdf.
~~The material on linear programs with complementarity constraints in Lecture 28 is from two talks: slides 4/54 to 14/54 from this one and slides 12/41 to 24/41 from this one.~~

John Mitchell's homepage.