Spring 2014

**Office hours:** Tuesdays 2-4pm, Wednesdays 11am-1pm, or by appointment.

**Material
on reserve** in the library.

**Scores** are available on LMS

- Homework 1: Mean 42.9/50, median 42, min 36, max 48, standard deviation 3.3.
- Homework 2: Mean 51.6/60, median 52, min 37, max 60, standard deviation 6.7.
- Homework 3: Mean 34.5/40, median 36.5, max 40, standard deviation 6.2.
- Homework 4: Mean 46.3/50, median 48, max 50, standard deviation 4.2.
- Totals on homeworks 1-4 for students who have handed in all the homeworks:

196 195 192 190 188 187 185 185 184 181 180 179 177 176 176 174 173 170 168 163 163 160 156 155

**Projects:**

** Midterm Exam: **
The midterm exam was in class on Friday, April 11.
Here is a link to some
more information.
Here are the
solutions.
**Old exams**:

- The midterm exam from 2012. Here are the solutions. The mean was 66%.
- The midterm exam from 2010. Mean: 71%. Here are the solutions.
- The midterm exam from 2008. Mean: 68%. Here are the solutions.
- The midterm exam from 2006. Mean: 69%. Here are the solutions.
- The take home midterm exam from 2004. Here are the solutions.
- The take home midterm exam from 2002. Here are the solutions.
- The take home midterm exam from 2000. Here are the solutions.

** Homework:**

- Homework 1. Here are the solutions.
- Homework 2. Here are the solutions.
- Homework 3. Here are the solutions.
- Homework 4. Here are the solutions.
- Homework 5. Here is a link to the AMPL model file for question 5. Here are the solutions.

**Information about
AMPL**.
A version of AMPL along with current versions of solvers
(including cplex 12.6) is available
here.

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

- Introduction, basic feasible solutions,
duality, and the simplex algorithm.
- Introduction: January 21: Pages 1-8. Pages 5-8 are covered in the first three handouts
- Basic feasible solutions, degeneracy: January 24: Pages 9-19.
- Duality: January 28: Pages 20-29.
- The simplex algorithm: January 31: Pages 30-42. See also two handouts.
- Multiple optimal solutions, handling free variables and upper bounds: February 4: Pages 43-50. See also a handout.

- Revised simplex, resolution.
- The Klee Minty cube: February 11.
- Probabilistic analysis of the simplex method: February 11. Focus on the results on pages 4, 5, and 9.
- The ellipsoid method: February 14.
- Dantzig-Wolfe decomposition,
cutting stock problems, network simplex, multicommodity network flows.
- February 14: introduction to Dantzig-Wolfe, pages 1-5.
- February 21 and 25: Dantzig-Wolfe iteration and behavior, block angular structure, pages 6-17. Also, an example of Dantzig-Wolfe decomposition.
- February 25 and 28: Lagrangian relaxation, cutting stock problems, pages 18-27.
- March 4 and 7: Network simplex, multicommodity network flow problems, pages 28-37. Here are some notes on network flows.

- Stochastic programming (updated March 24, 2014).
- March 18: pages 1-5.
- March 21: pages 6-11, 17-19.
- March 25: pages 20-26.
- 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-27, 29, 1, 3-7 covered on March 28.

Pages 7-8, 2, 9-17 covered on April 1.

Pages 18-22 covered on April 4.~~Pages 32-40 covered on April 4.~~ - Barrier methods.

Pages 6-18 covered on April 4. - Long-steps, quadratic convergence, predictor-corrector,
finite termination, crossover, infeasible methods.

Pages 11-16 covered on April 8.

Pages 6-10 covered on April 15. - Homogenized methods,
Mehrotra's predictor-corrector, sparse linear algebra,
interior point cutting plane methods.

Pages 1-4 covered on April 8.

Pages 5-9 covered on April 15.

Pages 10-14 summarized in ten minutes on April 15.

Pages 19-25 covered on April 18.

Slides 3/72 to 30/72 of this talk on interior point cutting plane methods were covered on April 18. The talk is based on a paper. - SDP
and SOCP.

Pages 1-7 covered on April 18.

Pages 18-20 covered on April 22.

Pages 13-15, 17, 27, and 30 covered on April 25.

Pages 8-12, 22-26, 31-32 covered on April 29.

Pages 16, 28-29, and 33 covered on May 2. The example on sensor location is here.

Page 21 covered on May 6.

May 6: 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. May 6.
- The material on linear programs with complementarity constraints on May 6 is from two talks: slides 4/54 to 14/54 from this one and slides 12/41 to 24/41 from this one.

- Linear algebra. (Jan 24.)
- Subspaces, affine sets, convex sets, and cones. (Jan 24.)
- Dimension, polyhedra, and faces. (Jan 24.)
- An iteration of the simplex algorithm and the algorithm. (Feb 3.)
- Handling upper bounds in the simplex algorithm. (Feb 7.)
- The dual simplex algorithm. (Feb 10.)
- Extreme points and extreme rays of polyhedra. (Feb 17.)
- An example of Dantzig-Wolfe decomposition. (February 21.)

**Papers and resources:**

- The book Convex Optimization, by Boyd and Vandenberghe, contains a wealth of material on SDP, SOCP, and conic programming.
*Introduction to Stochastic Programming*by Birge and Louveaux is available online via the RPI library.- A computational study of Dantzig-Wolfe decomposition, the doctoral thesis of James Tebboth.
- Myths and counterexamples in linear programming (and other areas of optimization). This site shows that you have to be careful about your assumptions when you state some things that are "obvious" in linear programming.
- Issue 87 of the Mathematical Optimization Society newsletter Optima, discussing the geometry of polyhedra and simplex pivoting rules.

John Mitchell's homepage. Mathematics Course Materials.