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
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
(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:
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.