FoCM 2014 conference
Workshop B3 - Continuous Optimization
December 16, 18:00 ~ 18:30 - Room A21
A short proof of infeasibility and generating all infeasible semidefinite programs
Gabor Pataki
University of North Carolina at Chapel Hill, USA - gabor@unc.edu
The fundamental Farkas lemma of linear programming allows us to easily verify the infeasibility of an LP. For semidefinite programs (SDPs) the straightforward generalization of Farkas' lemma is not {\em exact}, as it does not always prove infeasibility.
We present a short and exact certificate of infeasibility of SDPs using a standard form reformulation. From the reformulation the infeasibility is easy to read off, and it allows us to systematically generate all infeasible SDPs. We prove that -- loosely speaking -- there are only finitely many representative infeasible SDPs in every dimension. The URL of the paper is http://arxiv.org/abs/1406.7274
I will also recall related earlier work: we call a feasible semidefinite system {\em well behaved} if it has strong duality with its dual for all objective functions. I will present an exact characterization of well behaved systems, which allows to systematically generate all of them.
In particular, we can systematically generate all linear maps under which the image of the semidefinite cone is closed: this is a problem of independent interest in convex geometry. The URL of the latter paper is: http://arxiv.org/abs/1112.1436
Joint work with Minghui Liu (University of North Carolina at Chapel Hill).