ORIE 6326: Convex Optimization

Overview

Convex optimization generalizes least-squares, linear and quadratic programming, and semidefinite programming, and forms the basis of many methods for non-convex optimization. This course focuses on recognizing and solving convex optimization problems that arise in applications, and introduces a few algorithms for convex optimization. Topics include: 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. Algorithms: interior-point, subgradient, proximal gradient, operator splitting methods such as ADMM, stochastic gradient, branch and bound methods. Applications to statistics and machine learning, signal processing, control and mechanical engineering, and finance.

Prerequisites: Strong working knowledge of linear algebra, a modern scripting language (such as Python, Matlab, Julia, R). Some analysis (open and closed sets, boundaries and interiors, limits) will also be extremely useful.

Topics

The treatment in this class draws strongly on other excellent courses in convex optimization. The lectures from the first part of the course follow Stephen Boyd's EE364a. For the second half, on algorithms, we have borrowed from Stephen Boyd's EE364b, Lieven Vandenberghe's EE236c, Ryu and Boyd's primer on monotone operator methods, Pontus Gisselson's course on large-scale convex optimization, Sebastian Bubeck's book Convex Optimization: Algorithms and Complexity, and Gabriel Goh's analysis of momentum.

1. Introduction

2. Theory

   1. Convex sets

   2. Convex functions

   3. Convex optimization problems

   4. Duality

3. Applications

   1. Approximation and fitting

   2. Statistical estimation

   3. Geometric problems

4. Interior point methods: high accuracy on medium-scale data

   1. Convexity by induction: transforming to conic form

   2. Overview of interior point methods

   3. Gradient descent

   4. Newton and Quasi-Newton

   5. Numerical linear algebra (QR, Cholesky, and CG)

5. First order methods: moderate accuracy on large-scale data

   1. Subgradients

   2. Subgradient methods

   3. Lower bounds and acceleration

   4. Operators

   5. Operator splitting methods

   6. Stochastic subgradient methods

6. Non-convex optimization

   1. Branch and bound