Grading:
There will be weekly homework sets and a midterm exam (in-class).
The midterm covers Chapters 1,2,3,4.
The final is a term paper (take-home).
The grading scheme is:
Homework 35%,
Midterm 30%,
Term Paper 35%.
Homework:
There will be a weekly homework assignment,
to be handed in on Tuesdays at 11:00am, at the end of class.
Late homework will not be accepted. No exceptions.
The assignments, posted below, refer to the text book.
No homework after spring break, so you can focus on your term paper.
Midterm Exam:
The midterm covers
the first four chapters and is
held in class on Thursday, March 2.
This is an open book exam.
The exam and solutions are posted
here.
Final Exam: You will write a term paper on a topic
of their choice related to the class. This can focus on
foundational
mathematics (e.g. geometry
and combinatorics of convex sets), or
involve computing and software, or develop an
application of
optimization that interests you. Your choice. You may work on this by yourself or in teams of two.
Please submit a proposal for your project
by Thursday, March 23. This should fit on
one page and contain:
names of author(s), title,
sources, and a brief description.
The final version of the paper is due on Thursday, May 11.
Student Presentations:
Short talks on the term papers are scheduled
for April 24,25,26,27.
Click
here
for the schedule. Registered students
are expected to attend all lectures.
DAILY SCHEDULE:
Jan 17: 1.1 Variants, 1.2 Examples, 1.3 Piecewise linear convex objective functions
Jan 19: 1.4 Graphical solution, 2.1 Polyhedra and convex sets
Jan 24: 2.2 Vertices, 2.3 Standard form, 2.4 Degeneracy
Jan 26: 2.5-2.6 Existence and optimality of extreme points,2.7 Bounded polyhedra
Jan 31: 2.8 Fourier-Motzkin elimination, 3.1 Optimality conditions
Feb 2: 3.2-3.3 Simplex method
Feb 7: 3.4 Anticycling, 3.5 Phase One, 3.6 Column Geometry
Feb 9: Mathematical Software for Optimization
Feb 14: 3.7 Computational Efficiency, 4.1 Motivation for Duality
Feb 16: 4.2 Dual problem, 4.3 Duality theorem
Feb 21: 4.4 Marginal cost, 4.5 Dual simplex method
Feb 23: 4.6 Farkas Lemma, 4.7 Separating hyperplanes, 4.8 Cones
Feb 28: 4.9 Representation of polyhedra, Review
Mar 2: MIDTERM EXAM
Mar 7: 5.2 Global dependence on right-hand side, 5.3 Set of dual optimal solutions
Mar 9: 5.4 Global dependence on cost, 5.5 Parametric programming
Mar 14: 10.1 Modeling techniques, 10.2 Guidelines for strong formulations
Mar 16: 10.3 Modeling with exponentially many constraints, 11.1 Cutting plane methods
Mar 21: 11.2 Branch and bound, 11.3 Dynamic programming
Mar 23: 11.4 Integer programming duality
Apr 4: Interior point methods
Apr 6: Semidefinite programming
Apr 11: Polynomial optimization via sums of squares
Apr 13: No class: work on term paper
Apr 18: No class: work on term paper
Apr 20: No class: work on term paper
Apr 24, Mon 5-7pm (939 Evans Hall): Student presentations
Apr 25, Tue 9:30-11am (3107 Etcheverry): Student presentations
Apr 26, Wed 5-7pm (939 Evans Hall): Student presentations
Apr 27, Thu 9:30-11am (3107 Etcheverry): Student presentations
Homework assignments:
due Jan 24: (Section 1.7) Exercises 1.1, 1.4, 1.7, 1.8, 1.12, 1.14, 1.19
due
Jan 31: (Section 2.10) Exercises 2.1, 2.3, 2.4, 2.6, 2.7, 2.9, 2.10
due Feb 7: (Sections 2.10 and 3.9) Exercises 2.18, 2.21, 2.22,
3.2, 3.3, 3.5, 3.6, 3.10
due Feb 14: (Section 3.9) Exercises 3.16, 3.17, 3.19, 3.20, 3.22, 3.26, 3.28, 3.29, 3.30
due Feb 21: (Section 4.12) Exercises 4.1, 4.2, 4.4, 4.5, 4.6, 4.12, 4.13, 4.16
due Feb 28: (Section 4.12) Exercises 4.21, 4.24, 4.25, 4.29, 4.30, 4.31, 4.35, 4.36, 4.39
due Mar 14: (Section 5.7) Exercises 5.3, 5.8, 5.10, 5.11, 5.13, 5.15
due Mar 21: (Sections 10.5 and 11.10) Exercises 10.1, 10.5, 10.10, 10.12, 10.14, 11.1, 11.2, 11.3