General Information
Course Website: http://www.math.uwaterloo.ca/~harvey/F10/
Lecture Time: Tuesdays
& Thursdays, 10:00-11:20am
Lecture Room: MC 4040
Instructor: Prof. Nicholas Harvey, MC 6068, harvey@math.uwaterloo.ca
·
Office Hours: Thursdays,
11:30am-1:00pm
The best way to reach me is by email, or in office
hours, or by making an appointment to meet. You’re unlikely to find me in my
office at a random time.
Teaching
Assistants
·
Vris Cheung, MC 6202, yl2cheun@math.uwaterloo.ca. Office Hours: ?
·
Marcel Silva, MC 6219, mksilva@uwaterloo.ca. Office Hours: ?
Overview
This is a fast-paced, mathematically-oriented
introduction to optimization. It should be viewed as an advanced-level version
of CO 350 (much like the relationship between MATH 249 and 239). If you enjoy
rigorous mathematics, and would like to learn about an important area of
20th-century applied math, then this class is for you. CO 350 covers a subset
of the CO 355 topics at a slower pace, and with less mathematical depth. It is
recommended to students who do not relish the mathematical challenge of CO 355.
Topics
We will cover linear optimization, duality theory,
the simplex method, the ellipsoid method,
semi-definite optimization, as well as the basics of convex analysis, convex
optimization, integral polyhedral and combinatorial
optimization. The spirit is primarily mathematical; we will not dwell on
practical applications (in operations research, finance, etc.). We will however
discuss various connections to combinatorics and
computer science.
Prerequisites
The
most important prerequisite for this course is a thorough understanding of
linear algebra and high-dimensional geometry. If you did well in MATH 146/245/249, you are probably well-equipped for
this class. If you did poorly in MATH 136/235/239, you will probably find this
class to be very difficult. We will also discuss algorithms and computational
complexity. If you have taken CS 341 and CS 360/365, that might be helpful, but
it is not essential.
Resources
·
Course
Notes: “Mathematical Optimization: A Concise Introduction”
·
Optional
Textbook:
o This book is very detailed and well-written, but
quite expensive. It covers the topics of this class at a greater depth than we
will have time for.
D. Bertsimas and J. Tsitsiklis. Introduction
to Linear Optimization. Athena
Scientific, 1997.
·
Previous offerings (by me):
·
Other
reference books:
o The textbook I used last year is a real gem.
Understanding and
Using Linear Programming, by Jiří Matoušek and Bernd Gärtner
o This is a great book for learning linear algebra.
G. Strang. “Linear Algebra and its Applications”.
Brooks Cole, 2005.
o This
is a classic book on linear programming, by its inventor. It is fun to browse
for its historical perspective.
G. Dantzig. “Linear Programming and Extensions”.
It is freely available online.
Grading Scheme
o 30%
assignments (about 5, plus a preliminary quiz)
o 70% final exam
Note for students with disabilities
The Office for Persons with Disabilities (OPD),
located in Needles Hall, Room 1132, collaborates with all academic departments
to arrange appropriate accommodations for students with disabilities without
compromising the academic integrity of the curriculum. If you require academic accommodations to
lessen the impact of your disability, please register with the OPD at the
beginning of each academic term.