ORF 523, S15

Convex and Conic Optimization

Spring 2015, Princeton University (graduate course)

(This is the Spring 2015 version of this course. For the most recent version 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.

  • aaa: Notes by Amir Ali Ahmadi.
  • gh: Notes scribed by Georgina Hall (in LaTeX).
  • Lecture 1: A taste of P and NP: scheduling on Doodle + maximum cliques and the Shannon capacity of a graph.
    [pdf], [ppt]
     
  • Lecture 2: Mathematical background.
    aaa [pdf], gh [pdf]
     
  • Lecture 3: Local and global minima, optimality conditions, AMGM inequality, least squares.
    aaa [pdf], gh [pdf]
  • Lecture 4: Convex sets and functions, epigraphs, quasiconvex functions, convex hullls, Caratheodory's theorem, convex optimization problems.
    aaa [pdf], gh [pdf ]
  • Lecture 5: Separating hyperplane theorems, the Farkas lemma, and strong duality of linear programming.
    aaa [pdf], gh [pdf]
     
  • Lecture 6: Characterizations of convex functions, strict and strong convexity, optimality conditions for convex problems.
    aaa [pdf], gh [pdf]
     
  • Lecture 7: Convexity-preserving rules, convex envelopes, support vector machines.
    aaa [pdf], gh [pdf]
     
  • Lecture 8: LP, QP, QCQP, SOCP, SDP.
    aaa [pdf], gh [pdf]
     
  • Lecture 9: Some applications of SDP in dynamical systems and eigenvalue optimization.
    aaa [pdf], gh [pdf]
     
  • Lecture 10: Some applications of SDP in combinatorial optimization: stable sets, the Lovasz theta function, and Shannon capacity of graphs.
    aaa [pdf], gh [pdf]
     
  • Lecture 11: Nonconvex quadratic optimization and its SDP relaxation, the S-Lemma.
    aaa [pdf], gh [pdf]
     
  • Lecture 12: Robust optimization.
    aaa [pdf], gh [pdf]
     
  • Lecture 13: Computational complexity in numerical optimization.
    [pdf], [ppt]
     
  • Lecture 14: Complexity of local optimization, the Motzkin-Straus theorem, matrix copositivity.
    aaa [pdf], gh [pdf]
     
  • Lecture 15: Complexity of detecting convexity, concluding remarks on computational complexity.
    [pdf], [ppt]
     
  • Lecture 16: Sum of squares programming and relaxations for polynomial optimization.
    [pdf]
    [YALMIP_Demos]
     
  • Lecture 17: Convex relaxations for NP-hard problems with worst-case approximation guarantee.
    aaa [pdf], gh [pdf]
     
  • Lecture 18: Current trends in portfolio optimization (guest lecture by Dr. Reha Tutuncu)
    [pdf]
     
  • Lecture 19: Approximation algorithms (ctnd.), limits of computation, concluding remarks.
    [pdf], [ppt]

 

Problem sets and exams

Solutions are posted on Blackboard.

  • Homework 1: Image compression and SVD, matrix norms, optimality conditions.
    [pdf], [kuhn.jpg]

     
  • Homework 2: Support vector machines (SVMs), convex analysis, optimal control.
    [pdf], [data file]

     
  • Homework 3: Markowitz on real data + nuclear norm and SDP + distance geometry + stability of a matrix family.
    [pdf], [StockData.xls]

     
  • Midterm
    [pdf]

     
  • Homework 4: Convex relaxations in combinatorial optimization, the Lovasz sandwich theorem.
    [pdf], [data file]

     
  • Homework 5: SDP relaxations for QCQP, robust optimization, robust control, NP-hardness reductions.
    [pdf], [circledraw.m], [princetoncampus.png]

     
  • Homework 6: Complexity of SDP feasibility, sum of squares relaxation for nonconvex optimization, shape-constrained regression.
    [pdf], [regression_data] 

     
  • Final assignment
    [pdf]