CO 769 Syllabus (Winter 2013)

three references:
Semidefinite Optimization and Convex Algebraic Geometry
Handbook on Semidefinite, Conic and Polynomial Optimization, 2012 (Springer)
Handbook of Semidefinite Programming: Theory, Algorithms, and Applications, 2000 (Kluwer).

We will cover (time permitting) elements from the following topics.

• Basics of Semidefinite Programming (SDP)
  • Motivation (relaxations of hard combinatorial problems; connection to quadratic-quadratic programming)
  • Optimality and Duality (facial reduction, self-dual embeddings)
  • Basic primal-dual algorithms
• Applications of SDP
  • Matrix Completions; (special cases: Euclidean distance matrix completion, sensor network localization)
  • Combinatorial Optimization ( degeneracy and applications; and Theorem of Alternative for Slater Condition )
    • general binary quadratic programming relaxations (equivalence of four relaxations); quadratic assignment, travelling salesman, graph equipartition, bandwidth problem in graphs, max-cut
    • Exploiting structure in SDP, survey:
      • pages 1to6, chordal structure, low rank;
      • algebraic symmetry
  • Sparse principal component analysis, PCA
  • Robust optimization
• Algorithms
  • Self-regular interior-point methods
  • Block coordinate descent
  • Projection methods
  • Gauss-Newton method and quadratic SDP