< Liza Rebrova research website

Some things to get started

Syllabus

Main textbooks and links:

[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
[AAA]
Previous year class website (Prof A. Ahmadi)

List of topics from Spring 2022:

# 1
Introduction
# 2
Math review
# 3
Optimality conditions for unconstrained optimization
# 4
Convex sets and functions, Caratheodory and Approximate Caratheodory theorems
# 5
Convex optimization problem. Separability of convex sets and Farkas lemma
# 6
Farkas lemma and strong duality of linear programming. Example (from meeting times to graph covers and matchings)
# 7
Min vertex cover = max matching on bipartite graphs. Convex functions and optimzality
# 8
Properties of convex functions continued and SVM
# 9
Support vector machines
# 10
Hierarchy of classes of convex problems, Semidefinite Programming
# 11
Duality of Semidefinite and Conic Programming
# 12
Eigenvalue optimization as SDP
# 13
Stability in optimal control as SDP
# 14
Probabilistic estimates as SDP
# 15
Graph combinatorial optimization and SDP relaxation
# 16
Nonconvex quadratic optimization and SDP relaxation
# 17
Complexity theory
# 18
Hard polynomial optimization
# 19
SOS optimization
# 20
Approximate integer optimization, Grothendieck's inequality
# 21
Approximate optimization, MAXCUT and other applications
# 22
Solving convex problems, about interior points annd barrier functions
# 23
Sketching for convex programs and concluding remarks

Software

You can use Matlab or Python for the homework assignments. Potentially, you could also use other common programming languages, please reach out to me or AI before doing so. Some useful links:
1.
Python-based modeling software CVXPY to solve optimization problems
2.
Matlab-based modeling software CVX to solve optimization problems
3.
Download Matlab with Princeton licence