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
Teaching
Assistants
·
Vris Cheung, MC 6202, yl2cheun@math.uwaterloo.ca.
·
Marcel Silva, MC 6219, mksilva@uwaterloo.ca.
Assignments
|
|
Handed
out |
Due
date |
Questions |
Solutions |
|
0. |
9/14 |
9/21 |
||
|
1. |
9/21 |
9/28 |
||
|
2. |
10/05 |
10/14 |
||
|
3. |
10/19 |
11/2 |
||
|
4. |
11/2 |
11/11 |
||
|
5. |
11/18 |
12/2 |
Lecture Schedule
|
|
Date |
Topics |
Relevant
Reading |
Slides |
|
1 |
9/14 |
Definition
of Mathematical Programs and Linear Programs |
Chapter 1 |
|
|
2 |
9/16 |
LPs:
Examples, Fundamental Theorem, Dual Example |
Sections
2.1, 2.2 |
|
|
3 |
9/21 |
Duals,
Weak Duality, Strong Duality, Farkas Lemma |
Sections
2.2, 2.3 |
|
|
4 |
9/23 |
Farkas Lemma, Fourier-Motzkin Elimination |
Sections
2.3, 2.4 |
|
|
5 |
9/28 |
Proof of
Strong Duality, Proof of Fundamental Theorem, Complementary Slackness |
Section
2.4 |
|
|
6 |
9/30 |
Polyhedra, Convex Sets & Functions, Ellipsoids |
Section
2.6 |
|
|
7 |
10/5 |
Covering
half-ellipsoids by ellipsoids |
||
|
8 |
10/7 |
The
Ellipsoid Method |
Matousek-Gartner 7.1 |
|
|
9 |
10/12 |
Semi-definite
Programs |
||
|
10 |
10/14 |
Extreme points,
Vertices, BFSs, Faces, Hirsch conjecture |
Section
2.7 |
|
|
11 |
10/19 |
Kalai-Kleitman theorem on diameter of polyhedra |
|
|
|
12 |
10/21 |
Zero-sum
Games, Multiplicative Weight Update Method |
||
|
13 |
10/26 |
Convex
Functions in Rn |
Sections
3.1, 3.2 |
|
|
14 |
10/28 |
Non-linear
Optimization, Optimality Conditions |
Sections
3.3, 3.4 |
|
|
15 |
11/2 |
KKT
Theorem, Smallest Ball Problem |
Matousek-Gartner 8.7 |
|
|
16 |
11/4 |
Max Cut |
||
|
17 |
11/9 |
Combinatorial
Optimization, Bipartite Matching |
Section
4.1 |
|
|
18 |
11/11 |
Max Flow
& Min Cut |
Section
4.4 |
|
|
19 |
11/16 |
Vertex
Cover |
Matousek-Gartner 3.3, 8.2 |
|
|
20 |
11/18 |
The
Simplex Method |
Sections
2.8, 2.9 |
|
|
21 |
11/23 |
The World’s
Worst Spanning Tree Algorithm |
||
|
22 |
11/25 |
Vertices
of the Spanning Tree Polytope |
||
|
23 |
11/30 |
Review |
|
|
|
24 |
12/2 |
Review |
|
Further Reading
Ellipsoid Method
Semidefinite Programs
Diameter of Polyhedra
Counterexample
to Hirsch Conjecture
Multiplicative Weight
Update Method
KKT
Theorem
Max
Flow / Min Cut Theorem
History by Schrijver, Section 4