A structural geometrical analysis of weakly infeasible SDPs

Abstract

In this article, we present a geometric theoretical analysis of semidefinite feasibility problems (SDFPs). This is done by decomposing a SDFP into smaller problems, in a way that preserves most feasibility properties of the original problem. With this technique, we develop a detailed analysis of weakly infeasible SDFPs to understand clearly and systematically how weak infeasibility arises in semidefinite programming. In particular, we show that for a weakly infeasible problem over $n\times n$ matrices, at most $n-1$ directions are required to approach the positive semidefinite cone. We also present a discussion on feasibility certificates for SDFPs and related complexity results.

This version contains a shorter and more focused discussion. Proposition 19 and Theorem 23 in the previous version now correspond to Proposition 6 and Theorem 10. We also tried to contextualize some of the results in the BSS model. The first version will stay available at http://www.optimization-online.org/DB_HTML/2013/11/4137.html as well. 14 pages