ORF 523, S20

Convex and Conic Optimization    Spring 2020, Princeton University (graduate course)


(This is the Spring 2020 version of this course. For the current version, click here. For previous versions, click here.) 

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.

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_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

Solutions are posted on Blackboard. 

  • 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]