Continuous optimization

Description
Class meetings: Lecture Mon 12:30-14:00 (Room 0.83, Northern Building) and Problem-solving classes Thu 10:15-11:45 (Rooms 3-517 and 1-820, Southern Building). If you have any questions, you can email me to set up an appointment.

Grading: There will be two midterms (Oct 20 and Dec 08), each consisting of 6 problems to be written between 10:00-12:00. Both midterms are open book and open notes (no outside help is allowed).

A set of homework problems will be assigned each week, and their solutions will be discussed during the following problem-solving class. At the beginning of each problem-solving class, there will be a 10-minute test consisting of a single exercise, which will always be a variant of one of the homework problems from the previous week. You may use your own written notes and homework solutions during the test. Each test is worth 1 point.

After the test, students will be expected to present solutions to the homework problems. Presenting a correct solution is worth 1 point. If several students have solved the same problem and are willing to present it, priority will be given to the student who has earned the fewest points so far.

Each midterm is worth up to 50 points. Points earned from the weekly 10-minute tests and from presenting homework solutions are added on top of the midterm scores. For the problem-solving class, final grades are based on the total number of points: 2 from 40 points, 3 from 55, 4 from 70, and 5 from 85.

There will also be an oral exam on the lecture material during the exam period, at pre-announced times.

Lecture notes
N. Vishnoi. Algorithms for convex optimization.
L.C. Lau. Convexity and optimization.
S. Boyd, L. Vandenberghe. Convex Optimization.

Week 1
We recalled the basic concepts from analysis needed for the course (gradient, Hessian, first- and second-order approximations). We then introduced convex sets with examples, and established the first- and second-order characterizations of convexity. We also showed that locally optimal solutions of convex functions are globally optimal.
(Chapters 1-4 in Vishnoi’s book)

Week 2
We defined convex programs, introduced the dual program using the Lagrangian, and verified weak duality. We then considered Slater’s condition, and proved strong duality under some mild assumptions.
(Chapter 5 in Vishnoi’s book, Lectures 4-5 in Lau’s lecture notes)

Week 3
No lecture.

Week 4
We discussed gradient descent algorithms in general, and explained why moving in the direction of the negative of the gradient is locally optimal. Then we gave an algorithm for the case when the gradient is Lipschitz continuous.
(Chapter 6 in Vishnoi’s book)

Week 5
We moved to the idea of approximating the convex function by simpler ones, and moving at each step to the minimum point of the approximating function. We introduced the Bregman divergence of convex functions, and stated an algorithm for minimizing a convex function of bounded gradient over the probability simplex.
(first half of Chapter 7 in Vishnoi’s book)