Convex optimization problems appear in a huge number of applications and can be solved very efficiently, even for problems with millions of variables. However, recognizing what can be transformed into a convex optimization problem can be challenging. This course will teach you how to recognize, formulate, and solve these problems. We will briefly survey theoretical results in convex analysis, but the majority of the course will focus on formulating and solving problems that come up in practice. Applications will include signal processing, statistics & machine learning, finance, circuit design, mechanical structure design, control, power systems, and other areas based on student interest. This course is designed for advanced undergraduates and beginning graduate students.
Prerequisites: multivariable calculus (18.02), linear algebra (18.06 or 18.061), basic probability, basic programming, mathematical maturity (e.g., 6.042)
After this course, you should be able to...
recognize and formulate convex optimization problems that appear in various fields.
use open source software to solve these optimization problems.
decide which solver is best for your problem.
Textbook: Convex Optimization, by Stephen Boyd and Lieven Vandenberghe
Software: Convex.jl and convex optimization solvers.
Lectures are every Tuesday and Thursday from 1:00-2:30 PM, in 32-124. Most lectures will be taught by Theo Diamandis, but there may be a guest lecture or two.
Overview of optimization: least squares linear programs convex programs
Examples: portfolio optimization, mechanical design, machine learning, etc.
Convex sets & their properties
Convex functions & their properties
Disciplined Convex Programming (DCP) & convex optimization software
Problem classes: LPs, QPs, QCQPs, SOCPs, GPs
Multiobjective optimization (e.g., regularized least squares, Markowitz portfolio optimization)
Case studies: model predictive control (how SpaceX lands rockets); circuit design
Regression problems (regularized, robust, quantile)
Case studies: minimax polynomial fitting (how does my computer compute sin, exp, etc.); image & audio denoising
The Lagrange dual function and the dual problem
Case study: bounds for the two-way partitioning problem
Optimality conditions & sensitivity analysis
Case studies: assigning power to communication channels ("water-filling"); FX arbitrage and no-arbitrage prices
Maximum likelihood & maximum a posteriori probability estimation (MLE & MAP)
Nonparametric distribution estimation
Case studies: Logistic regression, Support Vector Machine (SVM)
TBD based on class interest
Possible topics: more application areas, mixed integer programming, semidefinite programming, robust optimization
I will try to post course notes before the corresponding lectures. The notes are organized by topic instead of by lecture. Please let me know if you find any typos, either on Piazza or via email (tdiamand@mit.edu).
Problem sets are assigned on Thursday and due the following Thursday at 11:59pm. Each problem set will ask you to model and solve convex optimization problems that come from various application areas. You'll need to use Julia and Convex.jl for the problem sets. See instructions here.
Most homework problems will be taken from the Convex Optimization additional exercises. Data files can be found here. It's easy to load these variables with include("filename.jl").
HW 0: please sign up for Piazza and fill out the course survey. Also make sure you have Julia installed and Convex.jl working (instructions).
All homework will be submitted on Gradescope. Course code: 3JBNZX
There will be an optional course project during the last week of IAP that will allow you to apply convex optimization to a problem of interest. The final product will be a short mathematical description of this problem (akin to the descriptions you see on the problem sets) and a solution. Course grading is designed such that this project can take the place of the final problem set.
Attendance is encouraged and will reflected in your final grade. You will received 1pt for each lecture attended, up to a maximum of 6pts.
This course is offered for 6 units of credit, and the grading is P/D/F. To receive credit, you must get 14 or more points. The main goal of this course is to learn about optimization and solve some fun problems.
| Total | 22pts |
|---|---|
| Problem sets | 12 pts |
| Attendance | 6pts |
| Project | 4pts |
Tu/Th 2:30 - 3:30pm in 36-153, directly after class
Study night Wed 5pm - 7pm in [01/18: 32-144, 01/25: 32-141, 02/01: 32-144]
Room is booked 4pm - 8pm if you want to work there early/late
Much of the material for this course comes from the following courses:
Stephen Boyd's Convex Optimization I (link)
Lieven Vandenberghe's Convex Optimization (link)
Ryan Tibshirani's Convex Optimization (link)