Convex and Conic Optimization

Spring 2025, Princeton University (graduate course)

This is the Spring 2025 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], [mclaughlin.jpg]
   
• Homework 2: Convex analysis, minimum fuel optimal control.
  [pdf]
   
• Homework 3: Norms defined by convex sets, totally unimodular matrices, doubly stochastic matrices.
  [pdf]
   
• Practice midterms:
  [pdf], [pdf], [pdf]
   
• Midterm:
   
• Homework 4: 
   
• Homework 5: 
   
• Homework 6: 
   
• Practice final exams:
   
• Final exam: