Convex and Conic Optimization
Spring 2024, Princeton University (graduate course)
This is the Spring 2024 version of this course. See the previous versions.
Useful links
- The course syllabus
- Course description
- Canvas (for Q&A, sign up to Ed Discussion via Canvas)
- Download MATLAB
- MATLAB Tutorial
- Download CVX (or CVXPY if you are a Python user)
- Download YALMIP
References
- A. Ben-Tal and A. Nemirovski, Lecture Notes on Modern Convex Optimization [link]
- S. Boyd and L. Vandenberghe, Convex Optimization [link]
- M. Laurent and F. Vallentin, Semidefinite Optimization [link]
- R. Vanderbei, Linear Programming and Extentions [link]
Lectures
The lecture notes below summarize most of what I cover on the whiteboard during class. Please complement them with your own notes. Some lectures take one class session to cover, some others take two.
- Lecture 1: A taste of P and NP: scheduling on Doodle + maximum cliques and the Shannon capacity of a graph.
[pdf]
- Lecture 2: Mathematical background.
[pdf]
- Lecture 3: Local and global minima, optimality conditions, AMGM inequality, least squares.
[pdf]
- Lecture 4: Convex sets and functions, epigraphs, quasiconvex functions, convex hullls, Caratheodory's theorem, convex optimization problems.
[ pdf ]
- CVX Demo
[cvx_examples.m] (MATLAB), [cvxpy_examples.ipynb] (Python)
- Lecture 5: Separating hyperplane theorems, the Farkas lemma, and strong duality of linear programming.
[ pdf ]
- Lecture 6: Bipartite matching, minimum vetex cover, Konig's theorem, totally unimodular matrices and integral polyhedra.
[ pdf ]
- Lecture 7: Characterizations of convex functions, strict and strong convexity, optimality conditions for convex problems.
[ pdf ]
- Lecture 8: Convexity-preserving rules, convex envelopes, support vector machines.
[ pdf ]
- Lecture 9: LP, QP, QCQP, SOCP, SDP.
[pdf]
- Lecture 10: Some applications of SDP in dynamical systems and eigenvalue optimization.
[pdf]
- Lecture 11: Some applications of SDP in combinatorial optimization: stable sets, the Lovasz theta function, and Shannon capacity of graphs.
[pdf]
- Lecture 12: Nonconvex quadratic optimization and its SDP relaxation, the S-Lemma.
[pdf]
- Lecture 13: Computational complexity in numerical optimization.
[pdf]
- Lecture 14: Complexity of local optimization, the Motzkin-Straus theorem, matrix copositivity.
[pdf]
- Lecture 15: Sum of squares programming and relaxations for polynomial optimization.
[pdf] (notes)
[pdf] (slides)
[YALMIP_Demos]
- Lecture 16: Robust optimization.
[pdf]
- Lecture 17: Convex relaxations for NP-hard problems with worst-case approximation guarantees.
[pdf]
- Lecture 18: Approximation algorithms (ctnd.), limits of computation, concluding remarks.
[pdf]
Problem sets and exams
Solutions are posted on Canvas.
- Homework 1: Image compression and SVD, matrix norms, existence of optimal solutions, descent directions, dual and induced norms, properties of positive semidefinite matrices.
[pdf], [conway.jpg]
- Homework 2: Convex analysis, minimum fuel optimal control.
[pdf]
- Homework 3: Support vector machines (Hillary or Bernie?), norms defined by convex sets, totally unimodular matrices, radiation treatment planning.
[pdf], [Hillary_vs_Bernie]
MATLAB specific data files: [treatment_planning_data.m]
Python specific data files: [treatment_planning_data.py], [Atumor.csv], [Aother.csv]
- Practice midterms:
[pdf], [pdf], [pdf]
- Midterm:
[pdf]
- Homework 4: Nuclear norm minimization, distance geometry, stability of matrix pairs, SDPs with no rational feasible solutions
[pdf]
- Homework 5: The Lovasz sandwich theorem, SDP and LP relaxations for the stable set problem, Shannon capacity.
[pdf], [Graph.mat]
- Homework 6: Equivalence of search and decision, complexity of rank-constrained SDPs, monotone and convex regression with SOS optimization.
[pdf], [regression_data.mat]
- Practice final exams:
[pdf], [pdf]
- Final exam:
Available on Gradescope. You have 48 hours to submit it from the moment of download. Latest submission time is May 15, 10pm ET.