C&O 355: Mathematical Optimization

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

Dantzig biographies: short and long

 

2.

09/17

LP
LP Formulations, Examples, Feasible Region, Corner Points, Local-Search Algorithm

MG 1, 2.4, skim 3.2, 3.4, 4.3

Anim1, Anim2, 2D LP Applet

PPTX, PDF

3.

09/22

3 definitions of corner points, Equivalence of definitions, Equational form of LPs

MG 4.4

 

PPTX, PDF

4.

09/24

Equational form of LPs, BFS for this form, bases

MG 4.1, 4.2

 

PPTX, PDF

5.

09/29

Neighboring bases, Finding better neighbors

MG 5.1, 5.2, 5.3

Goemans’ notes Sections 6 & 7

PPTX, PDF, Example

6.

10/01

Proof of optimality, Does the algorithm terminate?, Bland’s Rule

MG 5.7, 5.8

Bland, Bland’s rule

PPTX, PDF

7.

10/06

Finding a starting point, Duality, Strong Duality Theorem

MG 5.3, p70, 6.1-6.3

Von Neumann, Algebraic Geometry and Optimization

PPTX, PDF

8.

10/08

Farkas’ Lemma, Fourier-Motzkin Elimination

MG 6.4, 6.7

Farkas, Farkas’ Lemma,

Fourier, Motzkin

PPTX, PDF

9.

10/13

Complementary Slackness, Computational Complexity, Basic Geometry

MG p204

Goemans’ notes Section 10, Khachiyan,
Great Mathematical Sputnik of 1979

PPTX, PDF,
CS Example,
Geometry Notes

10.

10/15

Ellipsoid Method

Positive Definite Matrices, Ellipsoids, Rank 1 Updates, Covering Hemispheres by Ellipsoids

 

Positive Definite Matrices

PPTX, PDF,
Ellipsoid Notes

11.

10/20

The Ellipsoid Method, Covering Half-ellipsoids by Ellipsoids

MG 7.1

The Ellipsoid Method,

Householder Reflections

PPTX, PDF, Ellipsoid Notes

12.

10/22

Polynomial Time Algorithms, Separation Oracles, Convex Optimization

MG 7.1

Goemans’ notes, Wayne’s slides, Hirsch Conjecture, Hirsch Polymath

PPTX, PDF

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,
MG 8.7

KKT Theorem, Boyd’s lecture

PPTX, PDF

16.

11/05

Transformations of Polyhedra, Convex Hulls

 

Minkowski

PPTX, PDF

17.

11/10

Faces and Diameter of Polyhedra, Hirsch Conjecture, Kalai-Kleitman Bound

 

Kalai, Kleitman, Kalai-Kleitman

PDF Notes

18.

11/12

Semidefinite Programming

 

Lau’s notes, Lovasz’ survey, Lovasz

PPTX, PDF

19.

11/17

Combinatorial Optimization

Total Unimodularity, Bipartite matching

MG 3.2, 8.2

Schrijver’s History Section 2

PPTX, PDF

20.

11/19

Vertex Covers, Konig’s Theorem, Minimum s-t Cuts

MG 8.2

Konig, Fulkerson, Fulkerson Obit.

PPTX, PDF

21.

11/24

Maximum Flows, Max-Flow Min-Cut Theorem

 

Max-Flow Min-Cut Theorem, Schrijver’s History Section 4

PDF Notes

22.

11/26

Integral Polyhedra, Weight-Splitting Method,
Shortest Paths

 

Hoffman, Frank

PPTX, PDF,
PDF Notes

23.

12/01

Shortest Paths, Primal-Dual Analysis,
Local-Ratio Method, Max Cut

 

Local-Ratio Method, Max Cut

PPTX, PDF

24.

12/03

Max Cut via Semidefinite Programming

 

Goemans, Williamson

PPTX, PDF

 

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.