2015/07/24 by Bruno F. Lourenço, Lourenço, Bruno F., Masakazu Muramatsu +3 · 1 citation
Computer Science · Mathematics · #Advanced Optimization Algorithms Research #Complexity and Algorithms in Graphs #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Variational Analysis #math.OC
paper · pdf · doi:10.48550/arxiv.1507.06843
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
openalex publication_date 2015/07/24 · arxiv created 2015/07/28 · arxiv updated 2015/07/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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× 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.