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 ξ(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 ˉχ(A) and σ(A), studied by Vavasis and Ye ??? in the setting of interior point algorithms in linear programming. In ??? Tun\c cel studied the connection between ˉχ(A) and σ(A) by exploiting their signing structure, and pointed at the existence of families of condition numbers (as ξ(A))``between'' them. We provide a dual characterization of ξ(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 ??? do using ˉχ(A). We also provide characterizations of ˉχ(A) when different norms are used. By exploiting the signing structure and it connection with oriented matroids, we deal with sensitivity analysis of ˉχ1(A), σ(A) and ξ(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.