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

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 

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

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

  • 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

  • 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