Bad semidefinite programs: they all look the same
Gabor Pataki
University of North Carolina,
Chapel Hill
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.