CO 769 Syllabus (Winter 2016)
Cone Optimization, Facial Reduction and its Applications

four references:

1. Class Notes and Survey Paper (D. Drusvyatskiy and H. Wolkowicz)
2. Semidefinite Optimization and Convex Algebraic Geometry (online), MOS-SIAM Series on Optimization, 2013, Editors: Grigoriy Blekherman , Pablo A. Parrilo and Rekha R. Thomas
3. Handbook on Semidefinite, Conic and Polynomial Optimization ( electronic from library), 2012 (Springer) Editors: Anjos, Miguel F., Lasserre, Jean B.
4. Handbook of Semidefinite Programming: Theory, Algorithms, and Applications, 2000 (Kluwer), Editors: Henry Wolkowicz, Romesh Saigal, Lieven Vandenberghe

The course will be self-contained. We will cover (time permitting) elements from the following topics.

1. Motivation
   1. What is facial reduction and why use it?
   2. Related work
2. Basics of Semidefinite Programming (SDP)
   1. Dual characterizations of strict feasibility in linear and semidefinite programming
   2. Optimality and Duality
   3. Basic primal-dual algorithms
3. Virtues of strict feasibility
   1. Regularity, stability, and distance to infeasibility
   2. Strong duality and boundedness of multipliers
   3. Subgradients of the value function
   4. Numerical convergence
   5. Strict feasibility is it "typical"?
4. Facial reduction
   1. Preprocessing in linear programming
   2. Facial reduction in conic optimization
   3. Semi-definite cone is self-replicating
   4. Facial reduction in semi-definite programming
5. Numerical issues of the paradigm
   1. Sturm's error bounds and alternating projections
   2. Consequences for stability
   3. Problems with singularity degree one
   4. Towards a practical implementation of facial reduction
6. Applications and Illustrations
   1. Quadratic assignment problem
   2. Graph partitioning
   3. Second lift of Max-Cut
   4. Semidefinite lifts of combinatorial problems generally
   5. Euclidean distance matrices and sensor networks
   6. Elimination method for sparse SOS polynomials