ORF523

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


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

Useful links
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, properties of positive semidefinite matrices.
    [pdf],  [Shams.jpg] 
     
  • Homework 2: Convex hulls, symmetries and convex optimization, containment among polytopes, distance between convex sets, theory-applications split in a course.
    [pdf], [distance_computation.fig]

  • Practice midterm 1.
    S18: [pdf], S17: [pdf], S16: [pdf].
     
  • Midterm 1.
    [pdf]

  • Homework 3: Support vector machines (Hillary or Bernie?), norms defined by convex sets, totally unimodular matrices, Farkas lemma, radiation treatment planning.
    [pdf], [treatment_planning_data.m], [Hillary_vs_Bernie.mat]

  • Homework 4: A nuclear program for peaceful reasons, distance geometry, stability of a pair of matrices, robust linear programs.
    [pdf]
     
  • Homework 5: The Lovasz sandwich theorem, SDP and LP relaxations for the stable set problem, Shannon capacity.
    [pdf], [Graph.mat] 

  • Practice midterm 2.
    S18: [pdf], S17: [pdf], S16: [pdf].

  • Midterm 2.
    [pdf]
      
  • Homework 6:  Equivalence of search and decision, complexity of SDP feasibility, NP-hardness of testing inclusion between low-degree basic semialgebraic sets.  
    [pdf]

  • Practice final. 
    S18: [pdf], S17: [pdf], S16: [pdf].

  • Final exam.
    [pdf]