Convex Optimization I

Concentrates on recognizing and solving convex optimization problems that arise in applications. Convex sets, functions, and optimization problems. Basics of convex analysis. Least-squares, linear and quadratic programs, semidefinite programming, minimax, extremal volume, and other problems. Optimality conditions, duality theory, theorems of alternative, and applications. Interior-point methods. Applications to signal processing, statistics and machine learning, control and mechanical engineering, digital and analog circuit design, and finance.

Objectives

• to give students the tools and training to recognize convex optimization problems that arise in applications
• to present the basic theory of such problems, concentrating on results that are useful in computation
• to give students a thorough understanding of how such problems are solved, and some experience in solving them
• to give students the background required to use the methods in their own research work or applications

Intended audience

This course should benefit anyone who uses or will use scientific computing or optimization in engineering or related work (e.g., machine learning, finance). More specifically, people from the following departments and fields: Electrical Engineering (especially areas like signal and image processing, communications, control, EDA & CAD); Aero & Astro (control, navigation, design), Mechanical & Civil Engineering (especially robotics, control, structural analysis, optimization, design); Computer Science (especially machine learning, robotics, computer graphics, algorithms & complexity, computational geometry); Operations Research (MS&E at Stanford); Scientific Computing and Computational Mathematics. The course may be useful to students and researchers in several other fields as well: Mathematics, Statistics, Finance, Economics.

Textbook

The textbook is Convex Optimization, available online, or in hard copy from your favorite book store.

Requirements

• Weekly homework assignments, due each Friday at midnight, starting the second week. We will use Gradescope for homework submission, with the details on Ed. We will have a late day policy on homeworks. Each student has one late day, i.e., you may submit one homework (except for homework 0) up to 24 hours late. Always reach out if you’re facing unusual disruptions to your classwork. You are allowed, even encouraged, to work on the homework in small groups, but you must write up your own homework to hand in. Each question on the homework will be graded on a scale of {0, 1, 2}.

• Midterm quiz. The format is a timed online 75 minute exam, at the end of the 3rd week. The midterm quiz covers chapters 1–3, and the concept of disciplined convex programming (DCP).

• Final exam. The format is a 24 hour take home exam, scheduled for the end of the last week of classes. You can take it during any 24 hour period over a multi-day period we’ll fix later. We can arrange for you take it earlier (as a beta tester, and only if you really need to) but not later. The final exam will require the use of CVXPY.

In Winter 2023–24 we will be using an updated set of slides developed last summer by Parth Nobel and Stephen Boyd.

1. Introduction
2. Convex sets
3. Convex functions
4. Convex optimization problems
5. Duality
6. Approximation and fitting
7. Statistical estimation
8. Geometric problems
9. Numerical linear algebra background
10. Unconstrained minimization
11. Equality constrained minimization
12. Interior-point methods
13. Conclusions

The full set of slides is available as one PDF file here.

The original slides, used until Summer 2023, are available here.

Additional lecture slides:

1. Convex optimization examples
2. Stochastic programming
3. Chance constrained optimization
4. Filter design and equalization

Two lectures from EE364b:

1. L1 methods for convex-cardinality problems
2. L1 methods for convex-cardinality problems, part II

CVX* tutorial sessions:

1. Disciplined convex programming and CVX
2. CVX slides (code)
3. Convex.jl slides
4. CVXPY tutorial website

Note that in Winter 2023–24, we will be using an supporting only CVXPY.