On strata of degenerate polyhedral cones I: Condition and distance to strata
Systems Ay?0 Ay ? 0 with a degenerate cone of solutions are considered ill-posed since finite-precision algorithms are not expected to find points in the cone of solutions. Consequently, common condition numbers for these systems, such as C(A) C ( A ) [J. Renegar. Some perturbation theory for linear programming, Mathematical Programming 65 (1994) 7391] and C(A) C ( A ) [D. Cheung, F. Cucker, A new condition number for linear programming, Mathematical Programming 91 (2001) 163174], which are based on the notion of distance to the nearest ill-posed problem, become infinite on such ill-posed instances. In this paper, we extend these two condition numbers to versions C  ( A ) and C  ( A ) which are always finite. Both condition numbers can be expressed in terms of a distance to a change in the geometry of the cone of solutions. The main result shows that for both of them, the distance corresponds to a notion of best conditioned solution for a canonical complementarity problem associated to the system Ay?0 Ay ? 0 .
condition numbers polyhedral conic systems degeneracy