Title: The many faces of degeneracy in conic optimization,
Abstract: Slater's condition -- existence of a "strictly feasible solution" -- is a
common assumption in conic optimization. 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. Hence, failure of strict feasibility can
negatively impact off-the-shelf numerical methods, such as 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 more pronounced phenomenon than has previously been realized.
In this text, we describe various reasons for the loss of strict feasibility,
whether due to poor modelling choices or (more interestingly) rich underlying
structure, and discuss ways to cope with it and, in many pronounced cases, how
to use it as an advantage. In large part, we emphasize the facial reduction
preprocessing technique due to its mathematical elegance, geometric
transparency, and computational potential.