Condition and Complexity Measures for Infeasibility Certificates of Systems of Linear Inequalities and Their Sensitivity Analysis
In this work we introduce a new condition measure $\xi(A)$ for the linear feasibility problem. This measure is based on the signing structure of the subspaces generated by the matrix $A$ that defines the problem. We consider two other condition numbers $\bar\chi(A)$ and $\sigma(A)$, studied by Vavasis and Ye \ref{} in the setting of interior point algorithms in linear programming. In \ref{tuncel} Tun\c cel studied the connection between $\bar\chi(A)$ and $\sigma(A)$ by exploiting their signing structure, and pointed at the existence of families of condition numbers (as $\xi(A)$)``between'' them. We provide a dual characterization of $\xi(A)$ and use it to study infeasibility detection via a constructive proof of a Helly-type theorem, in the same way that Ho and Tun\c cel \ref{ho-tuncel} do using $\bar\chi(A)$. We also provide characterizations of $\bar\chi(A)$ when different norms are used. By exploiting the signing structure and it connection with oriented matroids, we deal with sensitivity analysis of $\bar\chi_1(A)$, $\sigma(A)$ and $\xi(A)$. We give geometric and algebraic interpretations of perturbations of the matrix $A$ that preserve the continuity of such condition numbers. Finally, generalizations to convex cones and relationship with Renegar's condition measure are provided.