ABSTRACT: Slater's condition -- existence of a ``strictly feasible solution'' -- is at the heart of convex optimization. It is enough to look at the basics: without strict feasibility, first-order optimality conditions may be meaningless, the dual problem may yield little information about the primal, and small changes in the data may render the problem infeasible. In consequence, many off-the-shelf numerical methods can perform poorly; primal-dual interior point methods, in particular. 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 has previously been realized. Such new developments suggest a reappraisal. In this talk 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. In particular, we look at three different views: (i) from the ground set of the application; (ii) from the lifted space of semidefinite matrices in the relaxation; (iii) from the image space of the relaxation.
(Work with Dmitriy Drusvyatskiy, University of Washington, Seattle WA.)