Ideas for teaching a bit of linear optimization to advanced undergraduates?

Question

I am interested in ideas what to teach when the task is to teach a bit of (linear) optimization to third year undergraduate mathematics students.

More specifically:

• Assume 'a bit' means I'd have about eight hours of lecturing time.

• The students know standard linear algebra results and some multivariable real analysis (including basic optimality criteria via derivatives, and also Lagrange multiplier method). They do not know much (or any) numerical mathematics in a narrow sense, but at least in part have some knowledge of programming and algorithms.

An immediate idea is discussing the simplex algorithm. But what else?

I am tangentially familiar with various mathematically interesting subjects around this, but I do not know what could be feasible to discuss. I am also not strictly committed on the idea that it is all about linear optimization.

Answers could include a plan for these lectures or also recommendations for individual subjects that could be feasible to cover in the given context. Pointers to lecture notes in that direction or other relevant literature are welcome as well.

Answer 1

Four things come to mind.

1) You could focus on how the linearity of the objective function and the convexity of the feasible region yields that local optima are global, and how the linear nature of the constraints allow you to restrict your attention to corner points. This would accent the fundamental differences between linear and nonlinear optimization.

1) If you want to show how mathematics is interrelated -- you can show how optimal mixed strategies for two person zero-sum games can be found by linear programming. A famous anecdote which you could share with the students is how, when Dantzig was explaining linear programming to Von Neumann, the latter intuited the link with game theory and conjectured that there must be some underlying duality in linear programming (which Dantzig proved about a year later). Von Neumann's Minimax theorem and the fundamental duality theorem of linear programming are essentially the same thing. There are a couple of texts such as "An Introduction to Linear Programming and Game Theory" by Thie and Keough which explore this connection.

2) The Klee-Minty example of linear programs for which the simplex algorithm takes exponentially many steps is really quite interesting. The simplex algorithm is the most quotable case of a practical algorithm for which worst-case and average-case complexity are radically different.

3) The assignment problem is fairly accessible. There is some interesting linear algebra in explaining how you get integer solutions in this case even though the simplex algorithm will often give fractional answers for other problems. This problem is a good lead-in to combinatorial optimization and integer programming.

Answer 2

I have not tried anything similar myself, but if I had to, I would start by looking at Gilbert Strang's book "Introduction to applied mathematics" in chapter 8 "Optimization" (8.1 is "Introduction to linear programming"). My version is probably not the latest one and misses some recent developments (it seems to be written when interior point methods were just invented) but it really is a pleasant reading and has the right tone for students.

Answer 3

Just an idea: If your students know some statistics, including least squares regression, you could introduce optimization via some machine learnings methods, such as the lasso. The lasso can be solved as a quadratic programming problem, but simpler methods like coordinate descent work perfectly well.

One book where this is detailed is "Statistical Learning with Sparsity The Lasso and Generalizations" by Trevor Hastie, Robert Tibshirani and Martin Wainwright (CRC Press).

Answer 4

One of my classes actually has linear optimization on their corriculum (Switzerland, Berufsmatur). I teach according to the book "Mathematik in der Berufsschule". It's focused on students who want to go into economics. The way it's taught is very visual and seems well suited for your class if you have but 2 variables.

Every linear condition is drawn on a graph with the corresponding side that possible colored in or marked with an arrow. Then you color the space of feasable solutions.

Then you draw the equation of what you want optimized, but add a variable "c". Thus you can draw any parallel line. Now take a ruler and slide it in parallel until you find the last point that's still in the space of feasable solutions. For Maxima, you slide it up, for Minima you slide it down.