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.