Bad semidefinite programs: they all look the same
Duality theory is a central concept in Semidefinite Programming (SDP), just like it is in linear programming, since in optimization algorithms a dual solution serves as a certificate of optimality. However, in SDP, unlike in LP, ``pathological'' phenomena occur: nonattainment of the optimal value, and positive duality gaps between the primal and dual problems.
Motivated by the curious similarity of pathological SDP instances appearing in the literature, we find an exact characterization of semidefinite systems, which are badly behaved from the viewpoint of duality, i.e. show ``all bad SDPs look the same''. We also prove an "excluded minor" type result: all badly behaved semidefinite systems can be reduced (in a well defined sense) to a minimal such system with just one variable, and two by two matrices. More generally, we find characterizations of badly behaved conic linear systems over a general closed convex cone.