CMSC34500 - Optimization

Nati Srebro (firstname AT uchicago DOT edu)
TA: Andy Cotter (lastname AT tti-c DOT org)

2008/06/09

The final exam will take place between 10:30-12:30 on Tuesday, June 10th, in Eckhart 308. The exam will be open book (all those listed in the textbooks section of the course description, below), and open handwritten notes.

2008/05/30

Notes for recitation 9 are up.
Written assignment 6 is up. It is due on midnight on the morning of Thursday, June 5th (Wednesday night).

2008/05/28

Programming assignment 6 is up. It is due on midnight on the morning of Tuesday, June 3rd (Monday night).
Update (2008/06/08 5:45pm) : in problem 1.2, you should test various values of n and mu, not n and k

2008/05/15

Programming assignment 5 is up. It is due on midnight on the morning of Thursday, May 22nd (Wednesday night).

2008/05/14

Quiz solutions from recitation 6 are up.

2008/05/12

Written assignment 5 is up. It is due on midnight on the morning of Tuesday, May 20th (Monday night).
Update (2008/05/14 12:00pm) : it seems that a lot of people didn't notice the assignment, so it's been extended to next Tuesday; also fixed a typo

2008/05/02

Written assignment 4 is up. It is due on midnight on the morning of Tuesday, May 6th (Monday night).
Programming assignment 4 is up. It is due on midnight on the morning of Thursday, May 8th (Wednesday night). This is probably the longest programming assignment so far, so start early!
Update (2008/05/02 11:45am) : changed notation, fixed some errors, and removed an optional problem (this resulted in some of the problems being renumbered)
Update (2008/05/02 1:30pm) : cleaned up and fixed up the provided line search (the old version will work, but use the new version anyway)
Update (2008/05/07 2:30pm) : fixed the values of n and m in problem 2

2008/04/29

Notes for recitation 4 are up.

2008/04/23

Written assignment 3 is up. It is due on midnight on the morning of Tuesday, April 29th (Monday night).
Update (2008/04/23 6:45pm) : fixed a number of errors
Update (2008/04/28 10:45pm) : the expression for alpha in line 5 of the algorithm in section 1.3 should be the same as that in problem 1.1.1. Since the homework is due in roughly one hour, everyone in the class has an automatic one-day extension (to Wednesday morning, at midnight) on problem 1.3 only

2008/04/17

Programming assignment 3 is up. It is due on midnight on the morning of Tuesday, April 22nd (Monday night).

2008/04/11

Written assignment 2 is up. It is due on midnight on the morning of Thursday, April 17th (Wednesday night).
Update (2008/04/15 7:45pm) : on problem 1a, you may assume that the function f is differentiable.
Update (2008/04/16 4:30pm) : Problems 9.18, 9.19 and 9.23ac (not b!) are now optional
Notes for recitation 2 are up.

2008/04/08

Programming assignment 2 is up. It is due on midnight on the morning of Tuesday, April 15th (Monday night).

2008/04/07

The time and location of lectures has changed! They will now take place every Tuesday and Thursday at 3:00-4:20pm, in Eckhart 308.
TA office hours will held on Tuesdays from 4:30-5:30pm (right after lecture), at TTI.

2008/04/04

Notes for recitation 1 are up. Topics covered are convexity of l^p norms, gradients, Hessians, and a couple of examples from chapter 3 of Boyd & Vandenberghe.

2008/04/03

Written assignment 1 is up. It is due on midnight on the morning of Thursday, April 10th (Wednesday night).
Update (9:45pm) : fixed formatting error in the last problem.
Update (2008/04/04 12:45pm) : fixed the aforementioned formatting problem in the html version (the pdf version was fixed last night).

2008/04/02

Programming assignment 1 is up. It is due on midnight on the morning of Tuesday, April 8th (Monday night).
The course mailing list has been set up. If you haven't been getting emails, sign up here.

Overview

We will study how to formulate and solve convex optimization problems. Topics will include theory of convex optimization and convex duality; common optimization techniques for unconstrained and constrained problems including Newton's method, conjugate gradient methods and barrier methods for handling constraints; standard formulations including linear programs, quadratic programs and semi-definite programs; sample applications including applications in machine learning and as a tool for combinatorial optimization.

Lectures will take place every Tuesday and Thursday at 3:00-4:20pm, in Eckhart 308. Additionally, there will be weekly TA recitations at 3:00-4:00pm on Friday in the TTI conference room, in which assignments will be discussed, and some additional material (all of which will be "things you should already know") will be presented. On Tuesdays, immediately following lecture (4:30-5:30pm), there will be a TA office hour, also at TTI.

There will be two problem sets every week: one written, and one programming. The programming assignment will be due at midnight on Tuesday morning, and the written at midnight on Thursday. In general, the written assignments should be more difficult. There will also be an in-class midterm and final. The problem sets will probably contribute roughly 60% to your grade, and the exams 40%, but this is not set in stone.

Policies

On all assignments, collaboration is encouraged. The only conditions are that you write up your solutions yourself, and understand everything in them.

Partial credit will be given. If you don't get a problem, put in a note saying "I didn't finish", along with whatever you've been able to figure out.

If you require an extension, then discuss it with your TA before the assignment is due. Late homeworks will generally not be accepted.

Textbooks

The only required course textbook is:

Stephen Boyd, Lieven Vandenberghe. "Convex Optimization". Cambridge University Press. 2004

It is available online here.

You may also wish to refer to:

Dimitri P. Bertsekas. "Nonlinear Programming". Athena Scientific. 1999
Jorge Nocedal, Stephen J. Wright. "Numerical Optimization". Springer. 1999

The section on quasi-Newton methods in Nocedal & Wright may be particularly helpful.

If you need a linear algebra reference, we recommend:

Roger A. Horn, Charles R. Johnson. "Matrix Analysis". Cambridge University Press. 1987

Syllabus
Week 1	March 30 - April 5
Tuesday Lecture: Introduction Thursday Lecture: What is convexity? (Boyd and Vandenberghe: sections 2.1-2.3, 2.5, 3.1-3.2, 3.4. Bertsekas: sections B.1, B.2) Friday Recitation: Hessians, 1d optimization, programming assignment 1 (pdf html)
Week 2	April 6 - April 12
Tuesday Lecture: Unconstrained optimization (Boyd and Vandenberghe: chapter 9. Bertsekas: sections 1.1-1.4) Programming assignment 1 due (pdf, html, data for problem 2.2) Thursday Lecture: Unconstrained optimization - Newton's method (Boyd and Vandenberghe: charper 9. Bertsekas: section 1.4) Written assignment 1 due (pdf, html) (Last updated 2008/04/04 12:45pm) Friday Recitation: Inequalities from chapter 9, steepest descent with l¹ norm, affine invariance of Newton's method, precomputing line searches (pdf)
Week 3	April 13 - April 19
Tuesday Lecture: Conjugate gradient and quasi-Newton methods (Bertsekas: sections 1.6-1.7) Programming assignment 2 due (pdf, data for problem 1.2.2) Thursday Lecture: Constrained programs - LPs, QPs, QCQPs (Boyd and Vandenberghe: sections 4.1-4.4) Written assignment 2 due (pdf) Friday Recitation: Problems from and issues raised by written assignment 1
Week 4	April 20 - April 26
Tuesday Lecture: Cones, SOCPs, SDPs (Boyd and Vandenberghe: sections 2.4, 4.4, 4.6) Programming assignment 3 due (pdf) Thursday Lecture: Duality (Boyd and Vandenberghe: section 3.3, chapter 5) Friday Recitation: Convex conjugates, and their relationship with duality (pdf)
Week 5	April 27 - May 3
Tuesday Lecture: Duality (Boyd and Vandenberghe: chapter 5) Written assignment 3 due (pdf) (Last updated 2008/04/28 10:45pm) Thursday Lecture: Linear Programming Friday Recitation: PA4, Wolfe's condition, issues with conjugate gradient for non-quadratic objectives
Week 6	May 4 - May 10
Tuesday Lecture: Interior point methods Written assignment 4 due (pdf) Thursday Lecture: More on interior point methods Programming assignment 4 due (pdf, data and source code) (Last updated 2008/05/07 2:30pm) Quiz (pdf) Friday Recitation: Quiz solutions (pdf)
Week 7	May 11 - May 17
Tuesday Lecture: Approximation and fitting Thursday Lecture: Statistical estimation and regularization Friday Recitation: Linear programming. QR factorization
Week 8	May 18 - May 24
Tuesday Lecture: Support vector machines Written assignment 5 due (pdf) (Last updated 2008/05/14 12:00pm) Thursday Lecture: Multicriterion Programming assignment 5 due (pdf, data) Friday Recitation: Active set method for solving QPs
Week 9	May 25 - May 31
Tuesday Lecture: Relaxing non-convex optimization Thursday Lecture: Interior point, relaxing-and-rounding Friday Recitation: Linear algebra (pdf)
Week 10	June 1 - June 4
Tuesday Lecture: Subgradient methods Programming assignment 6 due (pdf, matlab file for reading data in problem 2) (Last updated 2008/06/08 5:45pm) Thursday Written assignment 6 due (pdf)