Convex and Conic Optimization

Spring 2020, Princeton University (graduate course)

This is the Spring 2020 version of this course. See the current version or previous versions.

Useful links

• Zoom (password has been emailed to registered students)
  • Lectures: Tue/Thu 1:30pm-2:50pm EST. Join here.
    • You can follow live notes during lecture.
  • AI office hours: Mon 4:30pm-6:30pm EST (Bachir) and Wed 4:30pm-6:30pm EST (Jeff). Join here.
  • AAA office hours: Wed 2pm-4pm EST. Join here.
• Course description
• Blackboard
• Piazza (used only for Q&A - you should sign in to Piazza via Blackboard)
• Download MATLAB
• Download CVX
• Download YALMIP

References

• A. Ben-Tal and A. Nemirovski, Lecture Notes on Modern Convex Optimization
• S. Boyd and L. Vandenberghe, Convex Optimization
• M. Laurent and F. Vallentin, Semidefinite Optimization
• R. Vanderbei, Linear Programming and Extentions

Lectures

• 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_examples.m]
   
• 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]
  [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

• Homework 1: Image compression and SVD, matrix norms, optimality conditions, dual and induced norms, properties of positive semidefinite matrices.
  [pdf], [ArashPouneh.jpg] 
  
   
• Homework 2: Convex analysis true/false questions, symmetries and convex optimization, distance between convex sets, theory-applications split in a course.
  [pdf], [distance_computation.fig]
  
   
• Practice midterm 1.
  S19: [pdf], S18: [pdf], S17: [pdf].
   
• Midterm 1.
  [pdf]
  
   
• Homework 3: Support vector machines (Hillary or Bernie?), norms defined by convex sets, totally unimodular matrices, Putting the F in ORFE.
  [pdf], [Hillary_vs_Bernie], [StockData.mat]
  
   
• Homework 4: A nuclear program for peaceful reasons, distance geometry, stability of a pair of matrices, SDPs with rational data and irrational feasible solutions.
  [pdf]
   
• Homework 5: The Lovasz sandwich theorem, SDP and LP relaxations for the stable set problem, Shannon capacity.
  [pdf], [Graph.mat] 
  
   
• Practice midterm 2.
  S19: [pdf], S18: [pdf], S17: [pdf], S16: [pdf].
  
   
• Midterm 2.
  [pdf]
   
• Homework 6: Equivalence of search and decision, complexity of SDP/SOCP feasibility, complexity of rank-constrained SDPs, monotone and convex regression with SOS optimization.
  [pdf], [regression_data.mat] 
  
   
• Practice final. 
  S19: [pdf], S18: [pdf], S17: [pdf], S16: [pdf].
  
   
• Final exam.
  [pdf]