CS 698C/K: Applications of semidefinite programming in complexity theory
Course outline:
Semidefinite Programming has emerged as a great tool to solve problems in
diverse areas such as combinatorial optimization and engineering. It is interesting as a class of problems because it is much more
general than linear programming but not much harder to solve. Specially in Computer Science there has been lot of results using this tool.
The course will have detailed introduction to the field of semidefinite programming and will cover various interesting applications
like the best known approximation algorithm for max-cut (Goemans-Williamson) and the
upper bound on Shannon Capacity.
Course notes
| Date |
Topic |
Link |
| 30th Dec 2013 |
Introduction to mathematical optimization |
Lecture 1 |
| 1st Jan 2014 |
Linear programming and convex optimization |
Lecture 2 |
| 6th Jan 2014 |
Convex sets |
Lecture 3 |
| 8th Jan 2014 |
Examples of convex sets |
Lecture 4 |
| 13th Jan 2014 |
Properties of convex sets |
Lecture 5 |
| 15th Jan 2014 |
Hyperplane separation theorems |
Lecture 6 |
| 20th Jan 2014 |
Dual cones |
Lecture 7 |
| 22th Jan 2014 |
Convex functions |
Lecture 8 |
| 27th Jan 2014 |
Matrices |
Lecture 9 |
| 29th Jan 2014 |
Spectral decomposition |
Lecture 10 |
| 3rd Feb 2014 |
Positive semidefinite matrix |
Lecture 11 |
| 5th Feb 2014 |
Positive semidefinite cone |
Lecture 12 |
| 10th Feb 2014 |
Semidefinite programming |
Lecture 13 |
| 12th Feb 2014 |
Examples of semidefinite programming |
Lecture 14 |
| 24th Feb 2014 |
Midsem solutions |
|
| 26th Feb 2014 |
Duality theory |
Lecture 15 |
| 3rd March 2014 |
Strong duality |
Lecture 16 |
| 5th March 2014 |
Maximum cut |
Lecture 17 |
| 10th March 2014 |
Lovasz theta number |
Lecture 18 |
| 12th March 2014 |
Properties of Lovasz theta number |
Lecture 19 |
| 24th March 2014 |
Concentration inequalities |
Lecture 20 |
References
Optimization
- Linear Programming, Dantzig and Thapa.
- Combinatorial Optimization: Algorithms and Complexity, Papadimitriou and Steiglitz.
- Convex Optimization, Boyd and Vandenberghe.
Linear Algebra
- My notes.
- Linear Algebra: An introductory approach, Charles W. Curtis (Chapter 1-4).
- Introduction to Linear Algebra, Gilbert Strang (Chapter 1-3,6)
- Linear Algebra, Hoffman and Kunze (Chapter 1-3).
Functional Analysis
- My notes.
- Functional Analysis, Walter Rudin (First four sections in Chapter 1).
