Tuesday, 15:15 - 15:40 h, Room: H 3008


Gabor Pataki
Bad semidefinite programs: They all look the same


In the duality theory of semidefinite programming (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 "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 NPcoNP
in the real number model of computing.
The main results follow from a fairly general characterization of badly behaved conic
linear systems, and hinge on a previous theorem
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.


Talk 1 of the invited session Tue.3.H 3008
"Combinatorics and geometry of linear optimization II" [...]
Cluster 2
"Combinatorial optimization" [...]


  Payday Loans Florida can help you in trying times, but be sure to know the laws necessary for your loan application. This pill gives a hand to thousands who suffer from erectile dysfunction. People who take Viagra Super Active can forget about their impotence and have a normal intimate life.