Speaker: Gabor Pataki

Title: Bad semidefinite programs: they all look the same

Abstract:

SDP's duality theory has been somewhat less well studied than its algorithmic aspects. Strong duality, -- expected in linear programming fails in many cases, and the variety of how things can go wrong is bewildering: one can have nonattainment in either one of the primal and the dual problems, attainment on both sides, but a finite duality gap, etc. The main result we present in this talk is a surprisingly simple, exact, "excluded minor" type characterization of all semidefinite systems that have a badly behaved dual for some objective function.
The characterization is based on some new, fundamental results in convex analysis on the closedness of the linear image of a closed convex cone. In particular, our result is a {\em necessary} condition for the closedness of the linear image -- as opposed to the usual {\em sufficient} conditions, such as the existence of a Slater-point, or polyhedrality. Our conditions are necessary {\em and} sufficient, when the cone belongs to a large class, called {\em nice} cones.
Our closedness criteria lead to exact characterizations for other badly behaved convex programs as well, such as second order cone programs, quadratically constrained convex quadratic programs, and geometric programs - essentially all efficiently solvable, convex optimization problems.