Course Announcement
UC Berkeley, Fall Semester 2001

Math 170: Introduction to Optimization

Instructor: Bernd Sturmfels (bernd@math, Evans 925),
Office Hours: Wednesday, 9:30am - 11:00am and Thursday 12:30pm - 2:00pm

Reader: Laura Matusevich (laura@math, Evans 737)
Office Hours: Mondays 2 - 3pm, Tuesdays and Thursdays 1pm - 2pm.

Time: Monday, Wednesday and Friday 1-2pm
Place: 87 Evans Hall
Text book: D.Bertsimas and J.N.Tsitsiklis: Introduction to Linear Optimization, Athena Scientific, Belmont, MA, 1997, ISBN: 1-886529-19-1.
Prerequsites: Knowledge of Linear Algebra (e.g.~Math 110).

This course gives an introduction to optimization at the advanced undergraduate level. The main emphasis will be on Linear Programming, which concerns optimizing a linear objective function subject to linear constraints. This problem plays a fundamental role in all the mathematical sciences and their applications. Our discussion of Linear Programming will stress the underlying geometry (polyhedra) and the basic duality theory. We shall also encounter two important extensions of Linear Programming, namely, Integer Programming and Semidefinite Programming. A range of algorithms for solving linear/integer/semidefinite programs will be discussed, including the classical simplex algorithm and the more recent interior point methods.

Approximate course outline:
August 27-31: Introduction (Chapter 1)
September 5-14: Geometry of Linear Programming (Chapter 2)
September 17-29: The Simplex Method (Chapter 3)
October 1-12: Duality Theory (Chapter 4)
October 15-19: Sensitivity Analysis (Chapter 5)
October 22 - November 2: Integer Programming (Chapters 10,11)
November 5-21: Ellipsoid Method and Interior Point Methods (Chapters 8,9)
November 26 - December 7: Semidefinite Programming

Homework and grading:
A weekly homework problem set is handed out on Wednesdays. The homework is due the following Wednesday. Collaboration is allowed, but each student must turn in their own homework sheet. No late homework, please. There is no midterm exam. The final exam might be given in take-home format or project format, depending on the class size and students' interests. The course grade will be determined by the maximum of the numbers 0.75 H + 0.25 F and 0.25 H + 0.75 F, where H is the score for the homework and F is the score for the final exam.