IOE 899 Seminar Presents: Gabor Pataki, University of North Carolina at Chapel Hill - Mar 16, 2011
Mar 16, 2011 | 4-5 PM | 1680 IOE
"Bad semidefinite programs: they all look the same"
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. SDP is vastly more general than LP, with applications ranging from engineering to combinatorial optimization, while it is still efficiently solvable. In SDP, unlike in LP, rather fascinating "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, ie. 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 result for conic linear programs.
Audience-Based Site-Wide Navigation:back to top