Facial Reduction in Cone Optimization with Applications to Matrix Completions

Henry Wolkowicz, University of Waterloo, Waterloo, ON, Canada.

Strict feasibility is at the heart of convex optimization. This is needed for optimality conditions, stability, and algorithmic development. New optimization modelling techniques and convex relaxations for hard nonconvex problems have shown that the loss of strict feasibility is a much more pronounced phenomenon than previously realized. These new developments suggest a reappraisal. We describe the various reasons for the loss of strict feasibility, whether due to poor modelling choices or (more interestingly) rich underlying structure, and describe ways to cope with it and, in particular, "take advantage of it".