## Convex and Conic Optimization

### Spring 2017, Princeton University (graduate course)

(This is the Spring 2017 version of this course. For the Spring 2016 version click here. For the Spring 2015 version click here.)

#### Useful links

- 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 [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: Bipartite matching, minimum vetex cover, Konig's theorem, totally unimodular matrices and integral polyhedra.

aaa [pdf], gh[pdf] - Lecture 7: Characterizations of convex functions, strict and strong convexity, optimality conditions for convex problems.

aaa [pdf], gh[pdf]

- Lecture 8: Convexity-preserving rules, convex envelopes, support vector machines.

aaa [pdf], gh[pdf]

- Lecture 9: LP, QP, QCQP, SOCP, SDP.

aaa [pdf], gh [pdf] - Lecture 10: Some applications of SDP in dynamical systems and eigenvalue optimization.

aaa [pdf], gh [pdf] - Lecture 11: Some applications of SDP in combinatorial optimization: stable sets, the Lovasz theta function, and Shannon capacity of graphs.

aaa [pdf], gh [pdf] - Lecture 12: Nonconvex quadratic optimization and its SDP relaxation, the S-Lemma.

aaa [pdf], gh [pdf] - Lecture 13: Computational complexity in numerical optimization.

[pdf] - Lecture 14: Complexity of local optimization, the Motzkin-Straus theorem, matrix copositivity.

aaa [pdf], gh [pdf] - Lecture 15: Sum of squares programming and relaxations for polynomial optimization.

[pdf]

[YALMIP_Demos] - Lecture 16: Robust optimization.

aaa [pdf], gh [pdf] - Lecture 17: Kernels, random embeddings, and deep learning (William Pierson Field lecture by Dr. Vikas Sindhwani, Google Research)

[pdf] - Lecture 18: Convex relaxations for NP-hard problems with worst-case approximation guarantees.

aaa [pdf], gh [pdf] - Lecture 19: 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 and copositive matrices.

[pdf], [Shams.jpg] - Homework 2: Convex analysis, theory-application split in a course, distance between convex sets, detecting uniqueness of solutions to LPs.

[pdf], [distance_computation.fig] - Practice midterm 1.

[pdf], [pdf]

- Midterm 1.

[pdf] - Homework 3: Support vector machines (Hillary or Bernie?), radiation treatment planning, symmetries and convex optimization, TUM matrices, doubly stochastic and permutation matrices.

[pdf] - Homework 4: Nuclear norm and SDP, distance geometry, stability of a matrix family, invariant sets of dynamical systems.

[pdf]

- Homework 5: The Lovasz sandwich theorem, SDP and LP relaxations for stable set, Shannon capacity

[pdf] - Practice midterm 2.

[pdf] - Midterm 2.

[pdf]

- Homework 6: NP-hardness of testing compactness of basic semialgebraic sets, equivalence of search and decision, Complexity of SDP feasibility, SOS relaxation and stability of matrix products again.

[pdf] - Practice final.

[pdf], [pdf] - Final exam.

[pdf]