- 01/31 # 1
- Introduction (slides on Canvas)
- 02/02 # 2
- Math review [
**AAA**(Lec 2 notes),**BV**(Appendix A)] - 02/07 # 3
- Optimality conditions for unconstrained optimization [notes,
**AAA**(Lec 3),**CZ**(Chapter 6)] - 02/09 # 4
- AMGM inequality proof (example). Convex optimization problem. [
**AAA**(Lec 3, 4)] - 02/14 # 5
- Convex sets, properties and examples [
**AAA**(Lec 4, 5),**BV**(Chapter 2)] - 02/16 # 6
- Convex hulls and Caratheodory theorems (standard and approximate) [
**AAA**(Lec 4),**V**(Chapter 1.3),**V-HDP**(Intro)] - 02/21 # 7
- Convex functions, their properties, convex envelopes [see next class]
- 02/23 # 8
- Optimality of convex optimization [
**BV**(Chapter 3),**AAA**(Lec 7, 8)] - 02/28 # 9
- Separability of convex sets, Farkas lemma and strong duality of linear programming. [
**AAA**(Lec 5),**BV**(Chapter 2)], - 03/02 # 10
- Support vector machines [svm,
**BV**(8.6),**AAA**(Lec 8)] - 03/07 # 11
- Konig theorem (total unimodularity and tightness of linear relaxation) [
**AAA**(Lec 6) ] - 03/09
- Midterm in class.
- 03/21 # 12
- Classes of optimization problems, from LP to SDP [
**AAA**(Lec 9),**AG**,**BV**(Ch 4),**LV**(Ch 2)] - 03/23 # 13
- SDP problems, standard form and duality, CP duality [
**AAA**(Lec 9),**LV**(Ch 2)] - 03/28 # 14
- Applications of SDP in eigenvalue optimization, including system stability[
**AAA**(Lec 10),**LV**(Ch 2)] - 03/30 # 15
- Robust optimization and S-lemma [robust optimization note,
**AAA**(Lec 16, 12),**BV**(Ch 4),**BBC**] - 04/04 # 16
- S-lemma proof [
**AAA**(Lec 16),**BV**(Appendix B2),**LV**] - 04/06 # 17
- Lovasz SDP relaxation for the graph stability number and Shannon capacity [
**AAA**(Lec 11),**LV**(Ch 6)] - 04/11 # 18
- Graph MaxCut SDP relaxation and Grothendieck's inequality [
**V**(Ch 3),**LV**(Ch 7)] - 04/13 # 19
- Goemans Williamson algorithm, Cut norm estimation, SDP for probability estimates [
**V**(Ch 3),**LV**(Ch 7),**KN**] - 04/18 # 20
- SDP for probability estimates, complexity theory [computational complexity note,
**KT**(8.1),**AAA**(Lec 13)] - 04/20 # 21
- Complexity theory [see above]
- 04/25 # 22
- Hardness of optimization problems [
**AAA**(Lec 14, 15)] - 04/27 # 23
- Discussion [class note,
**AAA**(Lec 15),**M**(Ch 4)]

- [BV]
- S. Boyd and L. Vandenberghe, Convex Optimization
- [LV]
- M Laurent, F. Vallentin, Semidefinite Optimization
- [V-HDP]
- R. Vershynin, High-Dimensional Probability An Introduction with Applications in Data Science
- [V]
- R. Vershynin, Lectures in Geometric Functional Analysis
- [CZ]
- E. Chong, S. Zak, An Introduction to optimization
- [AAA]
- Typed lecture notes covering the majority of this class material (Instructor A.A. Ahmadi, Scribe G. Hall)
- [AG]
- Second-order cone programming (Alizadeh, Goldfarb)
- [KN]
- Grothendiek-type inequalities in combinatorial optimization (Khot, Naor)
- [BBC]
- Theory and applications of Robust Optimization (Bertsimas, Brown, Caramanis)
- [KT]
- Algorithms design (Kleinberg, Tardos)
- [M]
- Randomized algorithms for matrices and data (M. Mahoney)
- [PW]
- M. Pilanci, M. Wainwright, Randomized Sketches of Convex Programs with Sharp Guarantees
- [BF]
- A. Bluhm, D. S. Franca, Dimensionality reduction of SDPs through sketching