Title: Bad semidefinite programs: they all look the same
Speaker: Gabor Pataki, University of North Carolina at Chapel Hill
Location: ISyE executive classroom
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.
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, 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.
We prove analogous results for second order conic programs: in fact, the main results are derived from a fairly general result for conic linear programs. While the main tool we use is convex analysis, the results have a combinatorial flavor.
The URL of the short version of the paper is: http://www.optimization-
No comments:
Post a Comment