Course Meeting Times
Lectures: 2 sessions / week, 1.5 hours / session
Course Description
This course will focus on fundamental subjects in convexity, duality, and convex optimization algorithms. The aim is to develop the core analytical and algorithmic issues of continuous optimization, duality, and saddle point theory using a handful of unifying principles that can be easily visualized and readily understood.
The course places emphasis on proofs as well as geometric intuition. It is more sophisticated than 6.251J Introduction to Mathematical Programming and 6.252J Nonlinear Programming, and has some but not much overlap with these two courses.
Goals of this course:
- To develop insight and deep understanding of a fundamental optimization topic
- To treat with mathematical rigor an important branch of methodological research, and to provide an account of the state of the art in the field
- To get an understanding of the merits, limitations, and characteristics of the rich set of available algorithms
Prerequisites
A course in linear algebra (preferably abstract) and a course in real analysis, such as 18.06 and 18.100. Proofs will matter, but the rich geometry of the subject helps guide the mathematics.
Textbook
Bertsekas, Dimitri. Convex Optimization Theory. Athena Scientific, 2009. ISBN: 9781886529311.
Chapter 6: Convex Optimization Algorithms (
PDF)
Summary of concepts and results (PDF) (Courtesy of Athena Scientific. Used with permission.)
Additional References
Rockafellar, Ralph. Convex Analysis. Princeton University Press, 1996. ISBN: 9780691015866. [Preview with Google Books]
Boyd, Stephen, and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004. ISBN: 9780521833783. [Preview with Google Books] 6.079 Introduction to Convex Optimization follows this textbook.
Bertsekas, Dimitri, Angelia Nedic, and Asuman Ozdaglar. Convex Analysis and Optimization. Athena Scientific, 2003. ISBN: 9781886529458.
Topics Covered
The text is modular, and the following sequence involves no loss of continuity.
| TOPICS | READINGS |
|---|---|
| Basic convexity concepts | Sections 1.1–1.4 |
| Convexity and optimization | Chapter 3 |
| Hyperplanes and conjugacy | Sections 1.5–1.6 |
| Polyhedral convexity | Chapter 2 |
| Geometric duality framework | Chapter 4 |
| Duality theory: Lagrangian duality, Fenchel duality, conic duality, saddle point theory | Sections 5.1–5.3, 5.5 |
| Subgradients and optimality conditions | Section 5.4 |
| Algorithms: subgradient methods, polyhedral approximation methods, proximal and bundle methods, interior point methods, optimal algorithms and complexity | Chapter 6 |
Grading
| ACTIVITIES | PERCENTAGES |
|---|---|
| Homework | 25% |
| Midterm | 25% |
| Term paper | 50% |