General
Information
Course
Website: http://www.math.uwaterloo.ca/~harvey/F09/
Lecture
Time: Tuesdays &
Thursdays, 10:00-11:20am
Lecture
Room: DWE 3517
Instructor: Nicholas Harvey, MC 6068, harvey@math.uwaterloo.ca
·
Office
Hours: Thursdays, 11:30am-1:00pm
Teaching Assistant: Vris Cheung, MC 6202, yl2cheun@uwaterloo.ca
·
Usual
Office Hours: Mondays, 1:30am-3:00pm.
Overview
This is a
fast-paced, advanced-level course (in the spirit of MATH 145, 147, etc.). In
one course, we will cover all of CO 350 (Linear Optimization) and some of CO
351 (Network Flow Theory) and CO 367 (Nonlinear 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 official
prerequisites for this course are MATH 235/245 and MATH 237/247. The most
important prerequisite is a strong background in linear algebra, particularly
the ability to translate geometric concepts into algebraic statements, and
vice-versa. If you need a quick review, see the appendix in the textbook. If
you need a thorough review, you may enjoy the online videos of G.
Strang’s lectures. General familiarity with graph
theory (at the level of MATH 239/249) and algorithms would also be helpful.
Resources
·
Textbook: Understanding and
Using Linear Programming, by Jiří Matoušek and
Bernd Gärtner
o An
electronic copy is available from the UW library.
·
There will be some supplementary notes on convex
geometry, non-linear programming and semi-definite programming.
·
UW-Angel Homepage: Assignments
will be put there.
·
Other reference books:
o G. Strang. “Linear Algebra and its Applications”. Brooks Cole,
2005. (On reserve in the
DC library)
o D. Bertsimas
and J. Tsitsiklis. “Introduction to Linear
Optimization”. Athena Scientific, 1997. (On
reserve in the DC library)
o G. Dantzig.
“Linear Programming and Extensions”. Available Online!
Grading
Scheme
·
40%
Assignments
·
20%
Midterm Exam (Wed Oct 28th, 7-9pm, MC 4040)
o Rules: You may
bring a single sheet of 8.5x11” paper, double-sided, with anything written or
printed on it. No calculators or electronic devices permitted.
o Content: The midterm
will cover Lectures 1-12, with an emphasis on Lectures 2-9.
·
40% Final Exam (Monday Dec
21st, 12:30pm-3:00pm, RCH 205)
o Rules: You may
bring a single sheet of 8.5x11” paper, double-sided, with anything written or
printed on it. No calculators or electronic devices permitted.
o Content: The midterm
will cover all lectures, with a slight emphasis on Lectures 14-24.
Assignments
There will
be about 5 assignments in this class. The questions are handed out in class,
and made available on UW-Angel.
|
|
Handed
out |
Due
date |
|
1. |
09/22 |
09/29 |
|
2. |
10/02 |
10/14 |
|
3. |
10/22 |
11/3 |
|
4. |
11/5 |
11/17 |
|
5. |
11/20 |
12/3 |
Lecture
Schedule
|
|
Date |
Topics |
Relevant
Reading |
Online
Resources |
Slides |
|
1. |
09/15 |
Overview
& History of Mathematical Programming |
|
||
|
2. |
09/17 |
LP |
MG 1, 2.4, skim 3.2, 3.4, 4.3 |
||
|
3. |
09/22 |
3 definitions of corner points, Equivalence of definitions,
Equational form of LPs |
MG 4.4 |
|
|
|
4. |
09/24 |
Equational form of LPs, BFS for this form, bases |
MG 4.1, 4.2 |
|
|
|
5. |
09/29 |
Neighboring bases, Finding
better neighbors |
MG 5.1, 5.2, 5.3 |
Goemans’
notes Sections 6 & 7 |
|
|
6. |
10/01 |
Proof of optimality, Does the
algorithm terminate?, Bland’s Rule |
MG 5.7, 5.8 |
||
|
7. |
10/06 |
Finding a starting point,
Duality, Strong Duality Theorem |
MG 5.3, p70, 6.1-6.3 |
||
|
8. |
10/08 |
Farkas’ Lemma, Fourier-Motzkin
Elimination |
MG 6.4, 6.7 |
||
|
9. |
10/13 |
Complementary Slackness,
Computational Complexity, Basic Geometry |
MG p204 |
Goemans’
notes Section 10, Khachiyan, |
|
|
10. |
10/15 |
Ellipsoid Method Positive Definite Matrices,
Ellipsoids, Rank 1 Updates, Covering Hemispheres by Ellipsoids |
|
||
|
11. |
10/20 |
The Ellipsoid Method,
Covering Half-ellipsoids by Ellipsoids |
MG 7.1 |
||
|
12. |
10/22 |
Polynomial Time Algorithms,
Separation Oracles, Convex Optimization |
MG 7.1 |
Goemans’ notes, Wayne’s
slides, Hirsch
Conjecture, Hirsch
Polymath |
|
|
13. |
10/27 |
Midterm Review Session. No
new material. |
|
|
|
|
14. |
10/29 |
Convex Analysis, Optimization & Polyhedra Vector Calculus Review, Convex
Functions |
Notes 3.1, 3.2 (UW Angel) |
|
|
|
15. |
11/03 |
Subgradient Inequality, Mini-KKT Theorem, Smallest Enclosing
Ball |
Notes 3.2, |
||
|
16. |
11/05 |
Transformations of Polyhedra, Convex Hulls |
|
||
|
17. |
11/10 |
Faces and Diameter of Polyhedra, Hirsch Conjecture, Kalai-Kleitman
Bound |
|
||
|
18. |
11/12 |
Semidefinite Programming |
|
||
|
19. |
11/17 |
Combinatorial Optimization Total Unimodularity,
Bipartite matching |
MG 3.2, 8.2 |
Schrijver’s
History Section 2 |
|
|
20. |
11/19 |
Vertex Covers, Konig’s Theorem, Minimum s-t Cuts |
MG 8.2 |
||
|
21. |
11/24 |
Maximum Flows, Max-Flow
Min-Cut Theorem |
|
Max-Flow Min-Cut
Theorem, Schrijver’s History Section 4 |
|
|
22. |
11/26 |
Integral Polyhedra,
Weight-Splitting Method, |
|
||
|
23. |
12/01 |
Shortest Paths, Primal-Dual Analysis, |
|
||
|
24. |
12/03 |
Max Cut via Semidefinite Programming |
|
Puzzle
In Lecture 1
I posed a puzzle for you to solve. This is optional; there is no course credit for
solving it, but there will be a prize. Detailed information about the puzzle is
available here.