Some Characterizations and Properties of the "Distance to Ill-Posedness" and the Condition Measure of a Conic Linear System

Abstract

A conic linear system is a system of the form P: find x that solves b- Ax E Cy, E Cx, where Cx and Cy are closed convex cones, and the data for the system is d = (A, b). This system is"well-posed" to the extent that (small) changes in the data (A, b) do not alter the status of the system (the system remains solvable or not). Intuitively, the more well-posed the system is, the easier it should be to solve the system or to demonstrate its infeasibility via a theorem of the alternative. Renegar defined the "distance to ill-posedness," p(d), to be the smallest distance of the data d = (A, b) to other data d = (A, b) for which the system P is "ill=posed," i.e., d = (A, b) is in the intersection of the closure of feasible and infeasible instances d' = (A', b') of P. Renegar also defined the "condition measure" of the data instance d as C(d) Alldll/p(d), and showed that this measure is a natural extension of the familiar condition measure associated with systems of linear equation. This study presents two categories of results related to p(d), the distance to ill-posedness, and C(d), the condition measure of d. The first category of results involves the approximation of p(d) as the optimal value of certain mathematical programs. We present ten different mathematical programs each of whose optimal values provides an approximation of p(d) to within certain constant factors, depending on whether P is feasible or not. The second category of results involves the existence of certain inscribed and intersecting balls involving the feasible region of P or the feasible region of its alternative system, in the spirit of the ellipsoid algorithm. These results roughly state that the feasible region of P (or its alternative system when P is not feasible) will contain a ball of radius r that is itself no more than a distance R from the origin, where the ratio R/r satisfies R/r < O(n C(d)), and such that r > _ ( -i) and R < O(n C(d)), where n is the dimension of the feasible region. Therefore the condition measure C(d) is a relevant tool in proving the existence of an inscribed ball in the feasible region of P that is not too far from the origin and whose radius is not too small.