# Bad semidefinite programs: they all look the same

Pataki, Gabor

### Abstract

Semidefinite Programming (SDP) is the problem of optimizing a linear objective function of a symmetric matrix variable, with the requirement that the variable also be positive semidefinite.

Duality theory is a central concept in 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.

This research was 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 that -- surprisingly -- ``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. Our characterizations imply that recognizing badly behaved semidefinite systems is in NP and co-NP in the real number model of computing.

The main results are derived from a fairly general characterization of badly behaved conic linear systems, and they hinge on a previous result on the closedness of the linear image of a closed convex cone. We show characterizations of badly behaved second order, and other conic systems as well.

The URL of the short version of the paper is:http://www.optimization-online.org/DB_HTML/2010/11/2809.html

### Details

- ‹ previous
- 17 of 62
- next ›