6.S098: Intro to Applied Convex Optimization (original) (raw)

1. Overview
2. Schedule
3. Notes
4. Assignments
5. Other

Overview

Course Syllabus

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)

Course Objectives

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.

Resources

Textbook: Convex Optimization, by Stephen Boyd and Lieven Vandenberghe

Software: Convex.jl and convex optimization solvers.

Schedule

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.

Jan 10: Introduction to Optimization

• Overview of optimization: least squares →\to linear programs →\to convex programs
• Examples: portfolio optimization, mechanical design, machine learning, etc.
• Convex sets & their properties

Jan 12: Convex Analysis & Optimization

• Convex functions & their properties
• Disciplined Convex Programming (DCP) & convex optimization software

Jan 17: Convex Optimization Problems and Applications

• 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

Jan 19: Applications: Approximation, Signal Processing

• Regression problems (regularized, robust, quantile)
• Case studies: minimax polynomial fitting (how does my computer compute sin, exp, etc.); image & audio denoising

Jan 24: Duality (i.e., understanding the output of your solver)

• The Lagrange dual function and the dual problem
• Case study: bounds for the two-way partitioning problem

Jan 27: Duality II

• Optimality conditions & sensitivity analysis
• Case studies: assigning power to communication channels ("water-filling"); FX arbitrage and no-arbitrage prices

Jan 31: Applications: Statistics & Machine Learning

• Maximum likelihood & maximum a posteriori probability estimation (MLE & MAP)
• Nonparametric distribution estimation
• Case studies: Logistic regression, Support Vector Machine (SVM)

Feb 2: Advanced Topics

• TBD based on class interest
• Possible topics: more application areas, mixed integer programming, semidefinite programming, robust optimization

Notes

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).

1. Optimization overview
2. Convex sets and functions
3. Convex optimization problem classes
4. Applications: approximation, signal processing, machine learning
5. Duality
6. Semidefinite programming and conic programs
7. Solvers

Assignments

Problem sets

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).
• HW 1
• HW 2
• HW 3

All homework will be submitted on Gradescope. Course code: 3JBNZX

Project

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.

Project Information

Other

Attendance

Attendance is encouraged and will reflected in your final grade. You will received 1pt for each lecture attended, up to a maximum of 6pts.

Lecture attendance form

Grading

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.

Office Hours

• 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

Acknowledgements

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)